-
作者：Jin, Billy; Klein, Nathan; Williamson, David P.
作者单位：Purdue University System; Purdue University; Boston University; Cornell University
摘要：A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the Held-Karp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality; that is, the cost of an optimal tour is at most 4/3 times the value of the value of the corresponding linear program. There is a variety of evidence in support of the conjecture (see, for instance, Goe...
-
作者：Kazachkov, Aleksandr M.; Balas, Egon
作者单位：State University System of Florida; University of Florida; Carnegie Mellon University
摘要：Disjunctive cutting planes can tighten a relaxation of a mixed-integer linear program. Traditionally, such cuts are obtained by solving a higher-dimensional linear program, whose additional variables cause the procedure to be computationally prohibitive. Adopting a nu-polyhedral perspective is a practical alternative that enables the separation of disjunctive cuts via a linear program with only as many variables as the original problem. The drawback is that the classical approach of monoidal s...
-
作者：Averkov, Gennadiy; Scheiderer, Claus
作者单位：Brandenburg University of Technology Cottbus; University of Konstanz
摘要：Consider the closed convex hull K of a monomial curve given parametrically as (tm1, horizontal ellipsis ,tmn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(t<^>{m_1},\ldots ,t<^>{m_n})$$\end{document}, with the parameter t varying in an interval I. We show, using constructive arguments, that K admits a lifted sem...
-
作者：Lou, Mengqi; Verchand, Kabir Aladin; Pananjady, Ashwin
作者单位：University System of Georgia; Georgia Institute of Technology; University of Southern California; University System of Georgia; Georgia Institute of Technology
摘要：Motivated by the desire to understand stochastic algorithms for nonconvex optimization that are robust to their hyperparameter choices, we analyze a mini-batched prox-linear iterative algorithm for the canonical problem of recovering an unknown rank-1 matrix from rank-1 Gaussian measurements corrupted by noise. We derive a deterministic recursion that predicts the error of this method and show, using a non-asymptotic framework, that this prediction is accurate for any batch-size and a large ra...
-
作者：Dubois-Taine, Benjamin; d'Aspremont, Alexandre
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS)
摘要：We consider separable nonconvex optimization problems under affine constraints. For these problems, the Shapley-Folkman theorem provides an upper bound on the duality gap as a function of the nonconvexity of the objective functions, but does not provide a systematic way to construct primal solutions satisfying that bound. In this work, we develop a two-stage approach to do so. The first stage approximates the optimal dual value with a large set of primal feasible solutions. In the second stage...
-
作者：Khanh, Pham Duy; Mordukhovich, Boris S.; Tran, Dat Ba
作者单位：Wayne State University
摘要：This paper addresses the study of nonconvex derivative-free optimization problems, where only information of either smooth objective functions or their noisy approximations is available. General derivative-free methods are proposed for minimizing differentiable (not necessarily convex) functions with globally Lipschitz continuous gradients, where the accuracy of approximate gradients is interacting with stepsizes and exact gradient values. Analysis in the noiseless case guarantees convergence ...
-
作者：Csendes, Tibor; Toth, Boglarka G.; Locatelli, Marco
作者单位：Szeged University; University of Parma
-
作者：Li, Jiajin; Zhu, Linglingzhi; So, Anthony Man-Cho
作者单位：University of British Columbia; University System of Georgia; Georgia Institute of Technology; Chinese University of Hong Kong
摘要：Nonconvex-nonconcave minimax optimization has gained widespread interest over the last decade. However, most existing works focus on variants of gradient descent-ascent (GDA) algorithms, which are only applicable to smooth nonconvex-concave settings. To address this limitation, we propose a novel algorithm named smoothed proximal linear descent-ascent (smoothed PLDA), which can effectively handle a broad range of structured nonsmooth nonconvex-nonconcave minimax problems. Specifically, we cons...
-
作者：Weninger, Noah; Fukasawa, Ricardo
作者单位：University of Waterloo
摘要：We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. We present a combinatorial branch-and-bound algorithm which outperforms the current stat...
-
作者：Ouyang, Wenqing; Milzarek, Andre
作者单位：Shenzhen Research Institute of Big Data; Shenzhen Institute of Artificial Intelligence & Robotics for Society; The Chinese University of Hong Kong, Shenzhen
摘要：We propose a novel trust region method for solving a class of nonsmooth, nonconvex composite-type optimization problems. The approach embeds inexact semismooth Newton steps for finding zeros of a normal map-based stationarity measure for the problem in a trust region framework. Based on a new merit function and acceptance mechanism, global convergence and transition to fast local q-superlinear convergence are established under standard conditions. In addition, we verify that the proposed trust...
