Mathematics of Operations Research

最新文章

• Solving Strong-Substitutes Product-Mix Auctions AI翻译
  作者：Baldwin, Elizabeth; Goldberg, Paul W.; Klemperer, Paul; Lock, Edwin
  作者单位：University of Oxford; University of Oxford
  摘要：This paper develops algorithms to solve strong-substitutes product-mix auctions: it finds competitive equilibrium prices and quantities for agents who use this auction's bidding language to truthfully express their strong-substitutes preferences over an arbitrary number of goods, each of which is available in multiple discrete units. Our use of the bidding language and the information it provides contrasts with existing algorithms that rely on access to a valuation or demand oracle. We compute...
• Conditional Uniformity and Hawkes Processes AI翻译
  作者：Daw, Andrew
  作者单位：University of Southern California
  摘要：Classic results show that the Hawkes self-exciting point process can be viewed as a collection of temporal clusters, in which exogenously generated initial events give rise to endogenously driven descendant events. This perspective provides the distribution of a cluster's size through a natural connection to branching processes, but this is irrespective of time. Insight into the chronology of a Hawkes process cluster has been much more elusive. Here, we employ this cluster perspective and a no...
• Fast Convex Optimization via Time Scale and Averaging of the Steepest Descent AI翻译
  作者：Attouch, Hedy; Bot, Radu Ioan; Nguyen, Dang-Khoa
  作者单位：Universite de Montpellier; Centre National de la Recherche Scientifique (CNRS); University of Vienna; Vietnam National University Ho Chi Minh City (VNUHCM) System
  摘要：In a Hilbert setting, we develop a gradient-based dynamic approach for fast solving convex optimization problems. By applying time scaling, averaging, and perturbation techniques to the continuous steepest descent (SD), we obtain high-resolution ordinary differential equations of the Nesterov and Ravine methods. These dynamics involve asymptotically vanishing viscous damping and Hessian-driven damping (either in explicit or implicit form). Mathematical analysis does not require developing a Ly...
• Asymptotic Consistency for Nonconvex Risk-Averse Stochastic Optimization with Infinite-Dimensional Decision Spaces AI翻译
  作者：Milz, Johannes; Surowiec, Thomas M.
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：Optimal values and solutions of empirical approximations of stochastic optimization problems can be viewed as statistical estimators of their true values. From this perspective, it is important to understand the asymptotic behavior of these estimators as the sample size goes to infinity. This area of study has a long tradition in stochastic programming. However, the literature is lacking consistency analysis for problems in which the decision variables are taken from an infinite-dimensional sp...
• Tight Bounds for Secretary Matching in General Graphs AI翻译
  作者：Ezra, Tomer; Feldman, Michal; Gravin, Nikolai; Tang, Zhihao (Gavin)
  作者单位：Harvard University; Tel Aviv University; Microsoft; MICROSOFT ISRAEL; Shanghai University of Finance & Economics
  摘要：Online algorithms for secretary matching in bipartite weighted graphs have been studied extensively in recent years. We generalize this study to secretary matching in general weighted graphs. In our model, vertices arrive online in a uniformly random order; upon the arrival of a vertex v , the weights of edges from v to all previously arriving vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. We provide a tight 5/12-competitive algorithm...
• A Fast Temporal Decomposition Procedure for Long- AI翻译
  作者：Na, Sen; Anitescu, Mihai; Kolar, Mladen
  作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; United States Department of Energy (DOE); Argonne National Laboratory; University of Chicago
  摘要：We propose a fast temporal decomposition procedure for solving long -horizon nonlinear dynamic programs. The core of the procedure is sequential quadratic programming (SQP) that utilizes a differentiable exact augmented Lagrangian as the merit function. Within each SQP iteration, we approximately solve the Newton system using an overlapping temporal decomposition strategy. We show that the approximate search direction is still a descent direction of the augmented Lagrangian provided the overla...
• Convergence Analysis of Accelerated Stochastic Gradient Descent Under the Growth Condition AI翻译
  作者：Chen, You-Lin; Na, Sen; Kolar, Mladen
  作者单位：University of Chicago; University of California System; University of California Berkeley; University of Chicago
  摘要：We study the convergence of accelerated stochastic gradient descent (SGD) for strongly convex objectives under the growth condition, which states that the variance of stochastic gradient is bounded by a multiplicative part that grows with the full gradient and a constant additive part. Through the lens of the growth condition, we investigate four widely used accelerated methods: Nesterov's accelerated method (NAM), robust momentum method (RMM), accelerated dual averaging method (DAM+), and imp...
• Quantitative Convergence for Displacement Monotone Mean Field Games with Controlled Volatility AI翻译
  作者：Jackson, Joe; Tangpib, Ludovic
  作者单位：University of Chicago; Princeton University
  摘要：We study the convergence problem for mean field games with common noise and controlled volatility. We adopt the strategy recently put forth by Laurie re and the second author, using the maximum principle to recast the convergence problem as a question of forward-backward propagation of chaos (i.e., (conditional) propagation of chaos for systems of particles evolving forward and backward in time). Our main results show that displacement monotonicity can be used to obtain this propagation of c...
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness AI翻译
  作者：Amanatidis, Georgios; Birmpas, Georgios; Fusco, Federico; Lazos, Philip; Leonardi, Stefano; Reiffenhauser, Rebecca
  作者单位：University of Essex; University of Liverpool; Sapienza University Rome; University of Amsterdam
  摘要：We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers, and therefore, a mechanism in our setting is an algorithm that takes as input the reported- rather than the true-values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspon...
• Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints AI翻译
  作者：Hinder, Oliver; Ye, Yinyu
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Stanford University
  摘要：Interior point methods (IPMs) that handle nonconvex constraints such as IPOPT, KNITRO and LOQO have had enormous practical success. We consider IPMs in the setting where the objective and constraints are thrice differentiable, and have Lipschitz first and second derivatives on the feasible region. We provide an IPM that, starting from a strictly feasible point, finds a mu-approximate Fritz John point by solving O(mu-7=4) trustregion subproblems. For IPMs that handle nonlinear constraints, this...