-
作者：Gupta, Neelima; Dabas, Rajni; Garg, Naveen
作者单位：University of Delhi; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi
摘要：We consider the capacitated facility location problem with outliers when facility costs are uniform. Our main result is the first constant factor approximation for this problem. We give a local search algorithm that requires only 2 operations and is a 6.373 +& varepsilon;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{documen...
-
作者：Bolte, Jerome; Le, Tam; Moulines, Eric; Pauwels, Edouard
作者单位：Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics; Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Inria; Institut National Polytechnique de Grenoble; Institut Polytechnique de Paris; Ecole Polytechnique; Mohamed bin Zayed University of Artificial Intelligence MBZUAI; Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：Motivated by the extensive application of approximate gradients in machine learning and optimization, we investigate inexact subgradient methods subject to persistent additive errors. Within a nonconvex semialgebraic framework, assuming boundedness or coercivity, we establish that the method yields iterates that eventually fluctuate near the critical set at a proximity characterized by an O(& varepsilon;rho)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{ams...
-
作者：McRae, Andrew D.
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We show that solutions to the popular convex matrix LASSO problem (nuclear-norm-penalized linear least-squares) have low rank under similar assumptions as required by classical low-rank matrix sensing error bounds. Although the purpose of the nuclear norm penalty is to promote low solution rank, a proof has not yet (to our knowledge) been provided outside very specific circumstances. Furthermore, we show that this result has significant theoretical consequences for nonconvex rank-constrained o...
-
作者：Uchoa, Eduardo; Sadykov, Ruslan
作者单位：Universidade Federal Fluminense
摘要：This article probes the origins of the Column Generation technique. It begins with Kantorovich's classic 1939 work, correcting widespread misconceptions about his contributions to the Cutting Stock Problem. It then brings to light Kantorovich and Zalgaller's lesser-known 1951 book, which is revealed to contain a complete Column Generation algorithm. The article also places these contributions in the context of the turbulent USSR's political and ideological environment, essential for a deeper u...
-
作者：Ranjan, Vinit; Stellato, Bartolomeo
作者单位：Princeton University
摘要：We introduce a numerical framework to verify the finite step convergence of first-order methods for parametric convex quadratic optimization. We formulate the verification problem as a mathematical optimization problem where we maximize a performance metric (e.g., fixed-point residual at the last iteration) subject to constraints representing proximal algorithm steps (e.g., linear system solutions, projections, or gradient steps). Our framework is highly modular because we encode a wide range ...
-
作者：Diouane, Youssef; Fomeni, Franklin Djeumou; Hertz, Alain; Orban, Dominique; Paquette, Courtney
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal; McGill University
-
作者：Kiessling, David; Leyffer, Sven; Vanaret, Charlie
作者单位：KU Leuven; United States Department of Energy (DOE); Argonne National Laboratory; Zuse Institute Berlin
摘要：We consider nonlinearly constrained optimization problems and discuss a generic double-loop framework consisting of basic algorithmic ingredients that unifies a broad range of nonlinear optimization solvers. This framework has been implemented in the open-source solver Uno, a Swiss Army knife-like C++ optimization framework that unifies many nonlinearly constrained nonconvex optimization solvers. We illustrate the framework with a sequential quadratic programming (SQP) algorithm that maintains...
-
作者：Doikov, Nikita
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study the composite convex optimization problems with a quasi-self-concordant smooth component. This problem class naturally interpolates between classic self-concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball optimization oracle. In this paper, we show that for minimizing quasi-self-concordant functions we can use instead the basic Newton ...
-
作者：Nie, Jiawang; Qu, Zheng; Tang, Xindong; Zhang, Linghao
作者单位：University of California System; University of California San Diego; Hong Kong Polytechnic University; Hong Kong Baptist University
摘要：This paper studies the sparse Moment-SOS hierarchy of relaxations for solving sparse polynomial optimization problems. We show that this sparse hierarchy is tight if and only if the objective can be written as a sum of sparse nonnegative polynomials, each of which belongs to the sum of the ideal and quadratic module generated by the corresponding sparse constraints. Based on this characterization, we give several sufficient conditions for the sparse Moment-SOS hierarchy to be tight. In particu...
-
作者：Jin, Billy; Klein, Nathan; Williamson, David P.
作者单位：Purdue University System; Purdue University; Boston University; Cornell University
摘要：One of the most famous conjectures in combinatorial optimization is the four-thirds conjecture, which states that the integrality gap of the Subtour LP relaxation of the TSP is equal to 43\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{4}{3}$$\end{document}. For 40 years, the best known upper bound was 1.5, d...
