Mathematics of Operations Research

最新文章

• Convexification of Bilinear Terms over Network Polytopes AI翻译
  作者：Khademnia, Erfan; Davarnia, Danial
  作者单位：Iowa State University
  摘要：It is well-known that the McCormick relaxation for the bilinear constraint z = xy gives the convex hull over the box domains for x and y . In network applications where the domain of bilinear variables is described by a network polytope, the McCormick relaxation, also referred to as linearization, fails to provide the convex hull and often leads to poor dual bounds. We study the convex hull of the set containing bilinear constraints z i , j = xiyj i y j where xi i represents the arc -flow vari...
• Alternating and Parallel Proximal Gradient Methods for Nonsmooth, Nonconvex Minimax: A Unified Convergence Analysis AI翻译
  作者：Cohen, Eyal; Teboulle, Marc
  作者单位：Tel Aviv University
  摘要：There is growing interest in nonconvex minimax problems that is driven by an abundance of applications. Our focus is on nonsmooth, nonconvex-strongly concave minimax, thus departing from the more common weakly convex and smooth models assumed in the recent literature. We present proximal gradient schemes with either parallel or alternating steps. We show that both methods can be analyzed through a single scheme within a unified analysis that relies on expanding a general convergence mechanism ...
• On the Smoothed Complexity of Combinatorial Local Search AI翻译
  作者：Giannakopoulos, Yiannis; Melissourgos, Themistoklis; Grosz, Alexander
  作者单位：University of Glasgow; Technical University of Munich; University of Essex
  摘要：We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a variety of problems within the complexity class PLS (Polynomial Local Search) can be cast within this model. This abstraction enables identifying key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. Our black-box tool provides concrete bounds on the expected maximum number of steps needed until local search reac...
• Optimality Conditions at Infinity in Semialgebraic Vector Optimization AI翻译
  作者：Jiao, Liguo; Lee, Jae Hyoung; Pham, Tien-Son
  作者单位：Northeast Normal University - China; Pukyong National University; Dalat University
  摘要：We are interested in optimality conditions for semialgebraic vector optimization problems with a situation in which generalized (weakly) nondominated points do exist but are not attained as image points of (weakly) efficient solutions. To this end, cones associated with unbounded semialgebraic sets at infinity are introduced and studied. Then, optimality conditions at infinity in terms of the Newton polyhedra of the objective mappings and of the cones associated with the constraint sets at inf...
• Can Learning Be Explained by Local Optimality in Robust Low-Rank Matrix Recovery? AI翻译
  作者：Ma, Jianhao; Fattahi, Salar
  作者单位：University of Michigan System; University of Michigan
  摘要：We explore the local landscape of low-rank matrix recovery, focusing on reconstructing a d1 x d2 matrix X* with rank r from m linear measurements, some potentially noisy. When the noise is distributed according to an outlier model, minimizing a nonsmooth & ell;1-loss with a simple subgradient method can often perfectly recover the ground truth matrix X*. Given this, a natural question is what optimization property (if any) enables such learning behavior. The most plausible answer is that the g...
• Scarf's Algorithm and Stable Marriages AI翻译
  作者：Faenza, Yuri; He, Chengyue; Sethuraman, Jay
  作者单位：Columbia University
  摘要：Scarf's algorithm gives a pivoting procedure to find a special vertex-a dominating vertex-in a down-monotone polytope. This paper studies the behavior of Scarf's algorithm when employed to find stable matchings in bipartite graphs. First, it proves that Scarf's algorithm can be implemented to run in polynomial time, showing the first positive result on its runtime in significant settings. Second, it shows an infinite family of instances where, no matter the pivoting rule and runtime, Scarf's a...
• The Core of Housing Markets from an Agent's Perspective: Is It Worth Sprucing up Your Home? AI翻译
  作者：Schlotter, Ildiko; Biro, Peter; Fleinera, Tamas
  作者单位：HUN-REN; HUN-REN Centre for Economic & Regional Studies; Budapest University of Technology & Economics; Corvinus University Budapest
  摘要：We study housing markets as introduced by Shapley and Scarf. We investigate the computational complexity of various questions regarding the situation of an agent a in a housing market H: we show that it is NP-hard to find an allocation in the core of H in which (i) a receives a certain house, (ii) a does not receive a certain house, or (iii) a receives a house other than a's own. We prove that the core of housing markets respects improvement in the following sense: given an allocation in the c...
• Corruption-Robust Exploration in Episodic Reinforcement Learning AI翻译
  作者：Lykouris, Thodoris; Simchowitz, Max; Slivkins, Aleksandrs; Sun, Wen
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Cornell University
  摘要：We initiate the study of episodic reinforcement learning (RL) under adversarial corruptions in both the rewards and the transition probabilities of the underlying system, extending recent results for the special case of multiarmed bandits. We provide a framework that modifies the aggressive exploration enjoyed by existing reinforcement learning approaches based on optimism in the face of uncertainty by complementing them with principles from action elimination. Importantly, our framework circu...
• Optimal Error Bounds in the Absence of Constraint Qualifications with Applications to p-Cones and Beyond AI翻译
  作者：Lindstrom, Scott B.; Lourenco, Bruno F.; Pong, Ting Kei
  作者单位：Curtin University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; Hong Kong Polytechnic University
  摘要：We prove tight Holderian lderian error bounds for all p -cones. Surprisingly, the exponents differ in several ways from those that have been previously conjectured. Moreover, they illuminate p -cones as a curious example of a class of objects that possess properties in three dimensions that they do not in four or more. Using our error bounds, we analyse least squares problems with p -norm regularization, where our results enable us to compute the corresponding Kurdyka-& Lstrok;ojasiewicz expon...
• Learning and Balancing Unknown Loads in Large-Scale Systems AI翻译
  作者：Goldsztajn, Diego; Borst, Sem C.; van Leeuwaarden, Johan S. H.
  作者单位：Eindhoven University of Technology; Inria; Tilburg University
  摘要：Consider a system of identical server pools where tasks with exponentially distributed service times arrive as a time-inhomogeneous Poisson process. An admission threshold is used in an inner control loop to assign incoming tasks to server pools, while in an outer control loop, a learning scheme adjusts this threshold over time to keep it aligned with the unknown offered load of the system. In a many-server regime, we prove that the learning scheme reaches an equilibrium along intervals of tim...