-
作者：Fischer, Frank
作者单位：Johannes Gutenberg University of Mainz
摘要：We develop a fully asynchronous proximal bundle method for solving non-smooth, convex optimization problems. The algorithm can be used as a drop-in replacement for classic bundle methods, i.e., the function must be given by a first-order oracle for computing function values and subgradients. The algorithm allows for an arbitrary number of master problem processes computing new candidate points and oracle processes evaluating functions at those candidate points. These processes share informatio...
-
作者：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
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite Cote d'Azur; Centre National de la Recherche Scientifique (CNRS); 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 ...
-
作者：Dubey, Yatharth; Liu, Siyue
作者单位：Amazon.com; Carnegie Mellon University
摘要：In this note, we study the size of the support of integer solutions to linear equations Ax = b, x is an element of Z(n )where A is an element of Z(mxn), b is an element of Z(n). We give an upper bound on the smallest support size as a function of A, taken as a worst case over all b such that the above system has a solution. This bound is asymptotically tight, and in fact matches the bound given in [1], while the proof presented here is simpler, relying only on linear algebra.
-
作者：Wirth, Elias; Pena, Javier; Pokutta, Sebastian
作者单位：Technical University of Berlin; Carnegie Mellon University
摘要：Recent papers have shown that the Frank-Wolfe algorithm (FW) with open-loop step-sizes exhibits rates of convergence faster than the iconic O(t-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(t<^>{-1})$$\end{document} rate. In particular, when the minimizer of a strongly convex function over a polyto...
-
作者：Wang, Irina; Becker, Cole; Van Parys, Bart; Stellato, Bartolomeo
作者单位：Princeton University; Massachusetts Institute of Technology (MIT)
摘要：Robust optimization is a tractable and expressive technique for decision-making under uncertainty, but it can lead to overly conservative decisions when pessimistic assumptions are made on the uncertain parameters. Wasserstein distributionally robust optimization can reduce conservatism by being data-driven, but it often leads to very large problems with prohibitive solution times. We introduce mean robust optimization, a general framework that combines the best of both worlds by providing a t...
