-
作者：Mulansky, Bernd; Potschka, Andreas
作者单位：TU Clausthal
摘要：We derive a mixed integer nonlinear programming formulation for the problem of finding a convex polygon with n vertices that is small (diameter at most one) and has maximum perimeter provided a stated conjecture is true. The formulation is based on a geometric construction using centrally symmetric polygons (zonogons). The resulting zonogons can be characterized by equivalence classes (under the action of the dihedral group) of 2n-vectors with entries either plus or minus one and a self-dualit...
-
作者：Gabl, Markus; Anstreicher, Kurt M.
作者单位：Helmholtz Association; Karlsruhe Institute of Technology; University of Iowa
摘要：We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with cutting planes and conic constraints. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a variety of different nonconvex quadratic problems.
-
作者：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 V-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 st...
-
作者：Mulansky, Bernd; Potschka, Andreas
作者单位：TU Clausthal
-
作者：Laude, Emanuel; Patrinos, Panagiotis
作者单位：KU Leuven
摘要：This paper studies a novel algorithm for nonconvex composite minimization which can be interpreted in terms of dual space nonlinear preconditioning for the classical proximal gradient method. The proposed scheme can be applied to additive composite minimization problems whose smooth part exhibits an anisotropic descent inequality relative to a reference function. It is proved that the anisotropic descent property is closed under pointwise average if the Bregman distance generated by the conjug...
-
作者：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...
-
作者：Husic, Edin; Koh, Zhuan Khye; Loho, Georg; Vegh, Laszlo A.
作者单位：Universita della Svizzera Italiana; University of Twente; University of London; London School Economics & Political Science
摘要：A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is at least 1-1/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepa...
-
作者：Basu, Amitabh; Jiang, Hongyi; Kerger, Phillip; Molinaro, Marco
作者单位：Johns Hopkins University; Cornell University; Microsoft; Pontificia Universidade Catolica do Rio de Janeiro
摘要：We investigate the information complexity of mixed-integer convex optimization under different types of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. This is derived as a corollary of a more fundamental transfer result that shows how lower bounds on information complexity of continuous convex optimization ...
-
作者：Jang, Uijeong; Gupta, Shuvomoy Das; Ryu, Ernest K.
作者单位：University of California System; University of California Los Angeles; Rice University
摘要：The accelerated composite optimization method FISTA (Beck, Teboulle 2009) is suboptimal by a constant factor, and we present a new method OptISTA that improves FISTA by a constant factor of 2. The performance estimation problem (PEP) has recently been introduced as a new computer-assisted paradigm for designing optimal first-order methods. In this work, we present a double-function stepsize-optimization PEP methodology that poses the optimization over fixed-step first-order methods for composi...
-
作者：Buchheim, Christoph; Merkert, Maximilian
作者单位：Dortmund University of Technology; Braunschweig University of Technology
摘要：Many discrete optimal control problems feature combinatorial constraints on the possible switching patterns, a common example being minimum dwell-time constraints. After discretizing to a finite time grid, it is sometimes possible to give a description of the convex hull of feasible (finite-dimensional) binary controls via flow-based extended formulations. For example, this is the case if the feasible set can be characterized via finite-state automata. In this work, we aim to transfer such des...
