-
作者：Byrka, Jaroslaw; Grandoni, Fabrizio; Traub, Vera
作者单位：University of Wroclaw; Universita della Svizzera Italiana; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The Steiner Forest problem is an important generalization of the Steiner Tree problem. We are given an undirected graph with nonnegative edge costs and a collection of pairs of vertices. The task is to compute a cheapest forest with the property that the elements of each pair belong to the same connected component of the forest. For a long time the best known approximation factor for Steiner Forest was 2, which is achieved by the classical primal-dual algorithm. Only very recently, the approxi...
-
作者：Battistoni, F.; Daniilidis, A.; De Bernardi, C. A.; Miglierina, E.
作者单位：Catholic University of the Sacred Heart; Technische Universitat Wien
摘要：The notion of regular pair (A, B) for two nonempty closed convex subsets A and B of a Hilbert space H\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {H}$$\end{document} was introduced by Borwein and Bauschke in 1993 to ensure convergence (in norm) of the alternating projection method to some point of the b...
-
作者：Nobel, Christian; Steiner, Raphael
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The (monotone) diameter of a polytope is a fundamental parameter with important connections to the efficiency of the simplex method. Despite the central role played by this parameter in discrete and linear optimization, determining the precise complexity of computing the diameter of an input polytope remains a long-standing open problem. In 1994 Frieze and Teng (Comput. Complex. 4(3), 207-219 (1994)) proved the first cornerstone result in this direction by establishing that computing the diame...
-
作者：Liu, Peijing; Atamturk, Alper; Gomez, Andres; Kucukyavuz, Simge
作者单位：University of Southern California; University of California System; University of California Berkeley; Northwestern University
摘要：In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising as part of an extended formulation and exploiting the supermodularity of a set function defined on its extreme points. Ou...
-
作者：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...
-
作者：Lessard, Laurent; Udell, Madeleine
作者单位：Northeastern University; Stanford University
摘要：When are two algorithms the same? How can we be sure a recently proposed algorithm is novel, and not a minor variation on an existing method? In this paper, we present a framework for reasoning about equivalence between a broad class of iterative algorithms, with a focus on algorithms designed for convex optimization. We propose several notions of what it means for two algorithms to be equivalent, and provide computationally tractable means to detect equivalence. Our main definition, oracle eq...
-
作者：Hommelsheim, Felix; Megow, Nicole; Muluk, Komal; Peis, Britta
作者单位：University of Bremen; University of Cologne; RWTH Aachen University; Dortmund University of Technology
摘要：We propose a model for recoverable robust optimization with commitment. Given a combinatorial optimization problem and uncertainty about elements that may fail, we ask for a robust solution that, after the failing elements are revealed, can be augmented in a limited way. However, we commit to preserve the non-failing elements of the initial solution. We settle the computational complexity of such a robust counterpart of various classical polynomial-time solvable combinatorial optimization prob...
-
作者：Maia, Leandro Farias; Gutman, David H.; Monteiro, Renato D. C.; Silva, Gilson N.
作者单位：Oregon State University; Texas A&M University System; Texas A&M University College Station; University System of Georgia; Georgia Institute of Technology; Universidade Federal do Piaui
摘要：This paper develops an adaptive proximal alternating direction method of multipliers (ADMM) for solving linearly constrained, composite optimization problems under the assumption that the smooth component of the objective is weakly convex, while the non-smooth component is a convex block-separable function with compact domain. The proposed method is adaptive to all problem parameters, including smoothness and weak convexity constants, and allows each of its block proximal subproblems to be ine...
