-
作者：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...
-
作者：Lindner, Niels; Masing, Berenike
作者单位：Free University of Berlin; Zuse Institute Berlin
摘要：The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are ...
-
作者：Zhang, Penghe; Xiu, Naihua; Qi, Houduo
作者单位：Hong Kong Polytechnic University; Beijing Jiaotong University; Hong Kong Polytechnic University; Hong Kong Polytechnic University
摘要：Indicator functions of taking values of zero or one are essential to numerous applications in machine learning and statistics. The corresponding primal optimization model has been researched in several recent works. However, its dual problem is a more challenging topic that has not been well addressed. One possible reason is that the Fenchel conjugate of any indicator function is finite only at the origin. This work aims to explore the dual optimization for the sum of a strongly convex functio...
-
作者：Lefebvre, Henri; Malaguti, Enrico; Monaci, Michele
作者单位：Universitat Trier; University of Bologna
摘要：Adjustable Robust Optimization (ARO) is a paradigm for facing uncertainty in a decision problem, in case some recourse actions are allowed after the actual value of all input parameters is revealed. While several approaches have been introduced for the linear case, little is known regarding exact methods for the convex case. In this work, we introduce a new general framework for attacking a wide class of ARO problems involving convex functions in the recourse problem. We first recall a semi-in...
-
作者：Gutekunst, Samuel C.; Jin, Billy; Williamson, David P.
作者单位：Bucknell University; Cornell University; Purdue University System; Purdue University
摘要：The symmetric circulant TSP is a special case of the traveling salesman problem in which edge costs are symmetric and obey circulant symmetry. Despite the substantial symmetry of the input, remarkably little is known about the symmetric circulant TSP, and the complexity of the problem has been an often-cited open question. Considerable effort has been made to understand the case in which only edges of two lengths are allowed to have finite cost: the two-stripe symmetric circulant TSP. In this ...
-
作者：Muehlebach, Michael; Jordan, Michael I.
作者单位：Max Planck Society; University of California System; University of California Berkeley
摘要：We exploit analogies between first-order algorithms for constrained optimization and non-smooth dynamical systems to design a new class of accelerated first-order algorithms for constrained optimization. Unlike Frank-Wolfe or projected gradients, these algorithms avoid optimization over the entire feasible set at each iteration. We prove convergence to stationary points even in a nonconvex setting and we derive accelerated rates for the convex setting both in continuous time, as well as in dis...
-
作者：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...
