-
作者：Cole, Richard; Hertrich, Christoph; Tao, Yixin; Vegh, Laszlo A.
作者单位：New York University; Shanghai University of Finance & Economics; University of Bonn; University of London; London School Economics & Political Science; Corvinus University Budapest
摘要：Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. From a theoretical perspective, linear convergence rates have been established for first order LP algorithms, despite the fact that the underlying formulations are not strongly convex. However, the convergence rate typically depends on the Hoffman constant of a large matrix that contains the constraint matrix, as w...
-
作者：Kong, Siyu; Lewis, A. S.
作者单位：Cornell University
摘要：Goldstein's 1977 idealized iteration for minimizing a Lipschitz objective fixes a distance - the step size - and relies on a certain approximate subgradient. That Goldstein subgradient is the shortest convex combination of objective subgradients at points within that distance of the current iterate. A recent implementable Goldstein-style algorithm allows a remarkable complexity analysis (Zhang et al. 2020), and a more sophisticated variant (Davis and Jiang, 2022) leverages typical objective ge...
-
作者：Gupta, Anupam; Hu, Jinqiao; Kehne, Gregory; Levin, Roie
作者单位：New York University; University of Warwick; Washington University (WUSTL); Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：We study online contention resolution schemes (OCRSes) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-ok(1))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1-o_k(1))$$\end{document}-selectable ...
-
作者：De Loera, Jesus A.; Marsters, Brittney; Xu, Luze; Zhang, Shixuan
作者单位：University of California System; University of California Davis; Texas A&M University System; Texas A&M University College Station
摘要：We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set with the help of a group action. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbe...
-
作者：Cartis, Coralia; Zhu, Wenqi
作者单位：University of Oxford
摘要：High-order tensor methods for solving both convex and nonconvex optimization problems have recently generated significant research interest, due in part to the natural way in which higher derivatives can be incorporated into adaptive regularization frameworks, leading to algorithms with optimal global rates of convergence and local rates that are faster than Newton's method. On each iteration, to find the next solution approximation, these methods require the unconstrained local minimization o...
-
作者：Dussault, Jean-Pierre; Frappier, Mathieu; Gilbert, Jean Charles
作者单位：University of Sherbrooke; University of Sherbrooke
摘要：The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system. If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth ...
-
作者：Huang, Kun; Pu, Shi; Nedic, Angelia
作者单位：The Chinese University of Hong Kong, Shenzhen; Arizona State University; Arizona State University-Tempe
摘要：In this paper, we introduce an accelerated distributed stochastic gradient method with momentum for solving the distributed optimization problem, where a group of n agents collaboratively minimize the average of the local objective functions over a connected network. The method, termed Distributed Stochastic Momentum Tracking (DSMT), is a single-loop algorithm that utilizes the momentum tracking technique as well as the Loopless Chebyshev Acceleration (LCA) method. We show that DSMT can asympt...
-
作者：Faenza, Yuri; Stein, Cliff; Wan, Jia
作者单位：Columbia University; Massachusetts Institute of Technology (MIT)
摘要：Gale and Shapley's stability criterion enjoys a rich mathematical structure, which propelled its application in various settings. Although immensely popular, the approach by Gale and Shapley cannot encompass all the different features that arise in applications, motivating the search for alternative solution concepts. We investigate alternatives that rely on the concept of internal stability, a notion introduced for abstract games by von Neumann and Morgenstern and motivated by the need of fin...
-
作者：Morton, David P.; Dowson, Oscar; Pagnoncelli, Bernardo K.
作者单位：Northwestern University; SKEMA Business School; Universite Cote d'Azur
摘要：We study a class of multi-stage stochastic programs, which incorporate modeling features from Markov decision processes (MDPs). This class includes structured MDPs with continuous action and state spaces. We extend policy graphs to include decision-dependent uncertainty for one-step transition probabilities as well as a limited form of statistical learning. We focus on the expressiveness of our modeling approach, illustrating ideas with a series of examples of increasing complexity. As a solut...
-
作者：Van Dyk, Madison; Klause, Kim; Koenemann, Jochen; Megow, Nicole
作者单位：University of Bremen; University of Waterloo
摘要：Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes in typical hub-and-spoke fashion. In practice, such consolidation requires parcel sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that it is NP-hard to determine whether a feasible sort...
