-
作者：Aragon-Artacho, Francisco J.; Perez-Aros, Pedro; Torregrosa-Belen, David
作者单位：Universitat d'Alacant; Universidad de Chile; Universidad de Chile
摘要：In this paper we introduce the Boosted Double-proximal Subgradient Algorithm (BDSA), a novel splitting algorithm designed to address general structured nonsmooth and nonconvex mathematical programs expressed as sums and differences of composite functions. BDSA exploits the combined nature of subgradients from the data and proximal steps, and integrates a linesearch procedure to enhance its performance. While BDSA encompasses existing schemes proposed in the literature, it extends its applicabi...
-
作者：Hoppenot, Pierre; Martin, Mathis; Szigeti, Zoltan
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
-
作者：Aliev, Iskander; Celaya, Marcel; Henk, Martin
作者单位：Cardiff University; Technical University of Berlin
摘要：We obtain new transference bounds that connect the additive integrality gap and sparsity of solutions for integer linear programs. Specifically, we consider the integer programs min{cx:x is an element of P boolean AND Zn}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \{{\varvec{c}}\cdot {\varvec{x}}: {\varvec...
-
作者：Zhang, Richard Y.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider minimizing a twice-differentiable, L-smooth, and mu -strongly convex objective 4 over an n x n positive semidefinite matrix M 0, under the assumption that the minimizer M* has low rank r* << n . Following the Burer-Monteiro approach, we instead minimize the nonconvex objective f (X) = 4 (XXT) over a factor matrix X of size nxr. This substantially reduces the number of variables from O(n2) to as few as O(n) and also enforces positive semidefiniteness for free, but at the cost of giv...
-
作者：van Doornmalen, Jasper; Hojny, Christopher
作者单位：Eindhoven University of Technology
摘要：Handling symmetries in optimization problems is essential for devising efficient solution methods. In this article, we present a general framework that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other, our framework allows to apply different methods simultaneously and thus outperforming their individual effect. Moreover, most existing symmetry handling methods only apply to binary variables. Our framework al...
-
作者：Hu, Yaohua; Hu, Xinlin; Yang, Xiaoqi
作者单位：Shenzhen University; Audencia; Shenzhen University; Hong Kong Polytechnic University
摘要：This paper aims to find an approximate true sparse solution of an underdetermined linear system. For this purpose, we propose two types of iterative thresholding algorithms with the continuation technique and the truncation technique respectively. We introduce a notion of limited shrinkage thresholding operator and apply it, together with the restricted isometry property, to show that the proposed algorithms converge to an approximate true sparse solution within a tolerance relevant to the noi...
-
作者：Upadhyaya, Manu; Banert, Sebastian; Taylor, Adrien B.; Giselsson, Pontus
作者单位：Lund University; Inria; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL
摘要：We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In particular, we consider (i) classes of optimization problems of finite-sum form with (possibly strongly) convex and possibly smooth functional components, (ii) first-order methods that can be written as a linear system on state-space form in feedback interconnection with the subdifferentials of the functional component...
-
作者：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 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 ...
