Mathematics of Operations Research

最新文章

• Reducing Bias in Event Time Simulations via Measure Changes AI翻译
  作者：Giesecke, Kay; Shkolnik, Alexander
  作者单位：Stanford University; University of California System; University of California Santa Barbara
  摘要：Stochastic point process models of event timing are common in many areas, including finance, insurance, and reliability. Monte Carlo simulation is often used to perform computations for these models. The standard sampling algorithm, which is based on a time-change argument, is widely applicable but generates biased simulation estimators. This article develops and analyzes a change of probability measure that can reduce or even eliminate the bias without restricting the scope of the algorithm. ...
• Linear and Utilitarian Choice Functions: Revisiting Myerson's Theorem AI翻译
  作者：Benjamin, Bachi; Shiran, Rachmilevitch
  作者单位：University of Haifa
  摘要：Myerson proved that every linear and weakly Paretian choice function is utilitarian. We revisit his model and result for the two-person case and supplement it with an only if direction. That is, we characterize the class of linear and weakly Paretian two-person choice functions. It turns out that these are the utilitarian functions with an egalitarian tie-breaking.
• Second-Order Optimality Conditions for Nonconvex Set-Constrained Optimization Problems AI翻译
  作者：Gfrerer, Helmut; Ye, Jane J.; Zhou, Jinchuan
  作者单位：Johannes Kepler University Linz; University of Victoria; Shandong University of Technology
  摘要：In this paper, we study second-order optimality conditions for nonconvex setconstrained optimization problems. For a convex set-constrained optimization problem, it is well known that second-order optimality conditions involve the support function of the second-order tangent set. In this paper, we propose two approaches for establishing second-order optimality conditions for the nonconvex case. In the first approach, we extend the concept of the support function so that it is applicable to gen...
• Complexity Analysis of a Sampling-Based Interior Point Method for Convex Optimization AI翻译
  作者：Badenbroek, Riley; de Klerk, Etienne
  作者单位：Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam; Tilburg University
  摘要：We develop a short-step interior point method to optimize a linear function over a convex body assuming that one only knows a membership oracle for this body. The approach is based a sketch of a universal interior point method using the so-called entropic barrier. It is well known that the gradient and Hessian of the entropic barrier can be approximated by sampling from Boltzmann-Gibbs distributions and the entropic barrier was shown to be self-concordant. The analysis of our algorithm uses pr...
• Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems AI翻译
  作者：Ghuge, Rohan; Nagarajan, Viswanath
  作者单位：University of Michigan System; University of Michigan
  摘要：We consider the following general network design problem. The input is an asymmetric metric (V, c), root r is an element of V, monotone submodular function f: 2(V) -> R+, and budget B. The goal is to find an r-rooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasi-polynomial time O(log k/log log k)-approximation algorithm for this problem, in which k <= |V| is the number of vertices in an optimal solution. As a consequence, we obtain an O(log (2)k/log lo...
• Finite State Mean Field Games with Wright-Fisher Common Noise as Limits of N-Player Weighted Games AI翻译
  作者：Bayraktar, Erhan; Cecchin, Alekos; Cohen, Asaf; Delarue, Francois
  作者单位：University of Michigan System; University of Michigan; Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; Universite Cote d'Azur; Centre National de la Recherche Scientifique (CNRS)
  摘要：Forcing finite state mean field games by a relevant form of common noise is a subtle issue, which has been addressed only recently. Among others, one possible way is to subject the simplex valued dynamics of an equilibrium by a so-called Wright-Fisher noise, very much in the spirit of stochastic models in population genetics. A key feature is that such a random forcing preserves the structure of the simplex, which is nothing but, in this setting, the probability space over the state space of t...
• Heavy-Traffic Insensitive Bounds for Weighted Proportionally Fair Bandwidth Sharing Policies AI翻译
  作者：Wang, Weina; Maguluri, Siva Theja; Srikant, R.; Ying, Lei
  作者单位：Carnegie Mellon University; University System of Georgia; Georgia Institute of Technology; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University of Michigan System; University of Michigan
  摘要：We consider a connection-level model proposed by Massoulie ' and Roberts for bandwidth sharing among file transfer flows in a communication network. We study weighted proportionally fair sharing policies and establish explicit-form bounds on the weighted sum of the expected numbers of flows on different routes in heavy traffic. The bounds are linear in the number of critically loaded links in the network, and they hold for a class of phase-type file-size distributions; that is, the bounds are ...
• Efficient Allocations in Double Auction Markets AI翻译
  作者：Pennanen, Teemu
  作者单位：University of London; King's College London
  摘要：This paper proposes a simple descriptive model of discrete-time double auction markets for divisible assets. As in the classical models of exchange economies, we consider a finite set of agents described by their initial endowments and preferences. Instead of the classical Walrasian-type market models, however, we assume that all trades take place in a centralized double auction where the agents communicate through sealed limit orders for buying and selling. We find that, under nonstrategic bi...
• A New Augmented Lagrangian Method for MPCCs-Theoretical and Numerical Comparison with Existing Augmented Lagrangian Methods AI翻译
  作者：Guo, Lei; Deng, Zhibin
  作者单位：East China University of Science & Technology; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
  摘要：We propose a new augmented Lagrangian (AL) method for solving the mathematical program with complementarity constraints (MPCC), where the complementarity constraints are left out of the AL function and treated directly. Two observations motivate us to propose this method: The AL subproblems are closer to the original problem in terms of the constraint structure; and the AL subproblems can be solved efficiently by a nonmonotone projected gradient method, in which we have closed-form solutions a...
• Accelerated Stochastic Algorithms for Convex-Concave Saddle-Point Problems AI翻译
  作者：Zhao, Renbo
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We develop stochastic first-order primal-dual algorithms to solve a class of convex-concave saddle-point problems. When the saddle function is strongly convex in the primal variable, we develop the first stochastic restart scheme for this problem. When the gradient noises obey sub-Gaussian distributions, the oracle complexity of our restart scheme is strictly better than any of the existing methods, even in the deterministic case. Furthermore, for each problem parameter of interest, whenever t...