-
作者：Chudak, FA; Roughgarden, T; Williamson, DP
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Berkeley; International Business Machines (IBM); IBM USA
摘要：Garg [10] gives two approximation algorithms for the minimum-cost tree spanning k vertices in an undirected graph. Recently Jain and Vazirani [15] discovered primal-dual approximation algorithms for the metric uncapacitated facility location and k-median problems. In this paper we show how Garg's algorithms can be explained simply with ideas introduced by Jain and Vazirani, in particular via a Lagrangean relaxation technique together with the primal-dual method for approximation algorithms. We...
-
作者：Ulbrich, M; Ulbrich, S; Vicente, LN
作者单位：University of Hamburg; University of Munich; Universidade de Coimbra; Rice University; Rice University
摘要：In this paper, the filter technique of Fletcher and Leyffer (1997) is used to globalize the primal-dual interior-point algorithm for nonlinear programming, avoiding the use of merit functions and the updating of penalty parameters. The new algorithm decomposes the primal-dual step obtained from the perturbed first-order necessary conditions into a normal and a tangential step, whose sizes are controlled by a trust-region type parameter. Each entry in the filter is a pair of coordinates: one re...
-
作者：Bot, Radu I.; Chenchene, Enis; Csetnek, E. Robert; Hulett, David A.
作者单位：University of Vienna
摘要：We analyze fast diagonal methods for simple bilevel programs. Guided by the analysis of the corresponding continuous-time dynamics, under a mild general assumption we provide convergence rates for the inner residual and upper bounds for the outer residual along an ergodic sequence. As the key point of our work, under geometric assumptions for the inner function-namely, a weaker condition attributed to Attouch and Czarnecki and a stronger H & ouml;lderian error bound-we provide a unified conver...
-
作者：Yu, Xian; Basciftci, Beste
作者单位：University System of Ohio; Ohio State University; University of Iowa
摘要：We consider a two-stage distributionally robust optimization (DRO) model with multimodal uncertainty, where both the mode probabilities and uncertainty distributions could be affected by the first-stage decisions. To address this setting, we propose a generic framework by introducing a phi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69...
-
作者：Goodwin, Ariel; Lewis, Adrian S.; Lopez-Acedo, Genaro; Nicolae, Adriana
作者单位：Cornell University; Cornell University; Babes Bolyai University from Cluj
摘要：As a foundation for optimization, convexity is useful beyond the classical settings of Euclidean and Hilbert space. The broader arena of nonpositively curved metric spaces, which includes manifolds like hyperbolic space, as well as metric trees and more general CAT(0) cubical complexes, supports primal tools like proximal operations for geodesically convex functions. However, the lack of linear structure in such spaces complicates dual constructions like subgradients. To address this hurdle, w...
-
作者：Chen, Cheng; Chen, Ruitao; Li, Tianyou; Ao, Ruicheng; Wen, Zaiwen
作者单位：Peking University; Peking University; Peking University; Peking University
摘要：Binary optimization has a wide range of applications in combinatorial optimization problems such as MaxCut, MIMO detection, and MaxSAT. However, these problems are typically NP-hard due to the binary constraints. We develop a novel probabilistic model to sample the binary solution according to a parameterized policy distribution. Specifically, minimizing the Kullback-Leibler divergence between the parameterized policy distribution and the Gibbs distributions of the function value leads to a st...
-
作者：Nagy, Marianna E.; Illes, Tibor; Nesterov, Yurii; Rigo, Petra Renata
作者单位：Corvinus University Budapest
摘要：We revisit the main principles for constructing polynomial-time primal-dual interior-point algorithms (IPAs). We investigate the weighted Linear Complementarity Problem (WLCP), by extending the framework of Parabolic Target Space (PTS), proposed by Nesterov (2008) for primal-dual Linear Programming (LP) Problems. This approach has several advantages. The proposed method based on the PTS approach starts from an arbitrary strictly feasible primal-dual pair and follows a single central path towar...
-
作者：Lu, Haihao; Yang, Jinwen
作者单位：Massachusetts Institute of Technology (MIT); University of Chicago
摘要：Convex quadratic programming (QP) is an important class of optimization problem with wide applications in practice. The classic QP solvers are based on either simplex or barrier method, both of which suffer from the scalability issue because their computational bottleneck is solving linear equations. In this paper, we design and analyze a first-order method for QP, called restarted accelerated primal-dual hybrid gradient (rAPDHG), whose computational bottleneck is matrix-vector multiplication....
-
作者：Blauth, Jannis; Klein, Nathan; Nagele, Martin
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Boston University
摘要：Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solution is then measured by adding the length of the tour and the sum of all penalties of vertices that are not visited. We present a polynomial-time approximation algorithm with an approximation guarantee slightly below 1.6, where the guarantee is with respect to the natural linear programming relaxation of the problem. T...
-
作者：Bolte, Jerome; Le, Quoc-Tung; Pauwels, Edouard; Vaiter, Samuel
作者单位：Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics; Centre National de la Recherche Scientifique (CNRS); Universite Cote d'Azur; Universite Cote d'Azur
摘要：We first show a simple but striking result in bilevel optimization: unconstrained C infinity\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C<^>\infty $$\end{document} smooth bilevel programming is as hard as general extended-real-valued lower semicontinuous minimization. We then proceed to a worst-case analysis of...
