Linear, Cone and Semidefinite Programming

Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization

  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Semi-definite Programming

    Building on the blueprint from Goemans and Williamson (1995) for the Max-Cut problem, we construct a polynomial-time approximation algorithm for orthogonally constrained quadratic optimization problems. First, we derive a semidefinite relaxation and propose a randomized rounding algorithm to generate feasible solutions from the relaxation. Second, we derive purely multiplicative approximation guarantees for our algorithm. When … Read more

    High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming

  • Zikai Xiong
    • Categories Linear Programming Tags , , ,

    The restarted primal-dual hybrid gradient method (rPDHG) is a first-order method that has recently received significant attention for its computational effectiveness in solving linear program (LP) problems. Despite its impressive practical performance, the theoretical iteration bounds for rPDHG can be exponentially poor. To shrink this gap between theory and practice, we show that rPDHG achieves … Read more

    Proximity results in convex mixed-integer programming

  • Burak Kocuk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Cone Programming Tags , , , ,

    We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of … Read more

    Faces of homogeneous cones and applications to homogeneous chordality

  • João Gouveia
  • Masaru Ito
  • Bruno F. Lourenço
    • Categories Cone Programming, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    A convex cone K is said to be homogeneous if its group of automorphisms acts transitively on its relative interior. Important examples of homogeneous cones include symmetric cones and cones of positive semidefinite (PSD) matrices that follow a sparsity pattern given by a homogeneous chordal graph. Our goal in this paper is to elucidate the … Read more

    On parametric formulations for the Asymmetric Traveling Salesman Problem

  • Gustavo Angulo
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra

    The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ), Desrochers-Laporte (DL) and Single Commodity Flow (SCF) formulations. We argue that the choice of some parameters of these formulations is arbitrary and, therefore, there are families of formulations … Read more

    Enhancing Top Efficiency by Minimizing Second-Best Scores: A Novel Perspective on Super Efficiency Models in DEA

  • Tomonari Kitahara
  • Takashi Tsuchiya
    • Categories Applications - OR and Management Sciences, Linear, Cone and Semidefinite Programming, Optimization in Data Science Tags , ,

    In this paper, we reveal a new characterization of the super-efficiency model for Data Envelopment Analysis (DEA). In DEA, the efficiency of each decision making unit (DMU) is measured by the ratio the weighted sum of outputs divided by the weighted sum of inputs.In order to measure efficiency of a DMU, ${\rm DMU}_j$, say, in CCR … Read more

    When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?

  • Wenzhi Gao
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , ,

    The primal-dual interior point method (IPM) is widely regarded as the most efficient IPM variant for linear optimization. In this paper, we demonstrate that the improved stability of the pure primal IPM can allow speedups relative to a primal-dual solver, particularly as the IPM approaches convergence.  The stability of the primal scaling matrix makes it … Read more

    Jordan and isometric cone automorphisms in Euclidean Jordan algebras

  • Michael Orlitzky
    • Categories Cone Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Every symmetric cone K arises as the cone of squares in a Euclidean Jordan algebra V. As V is a real inner-product space, we may denote by Isom(V) its group of isometries. The groups JAut(V) of its Jordan-algebra automorphisms and Aut(K) of the linear cone automorphisms are then related. For certain inner products, JAut(V) = … Read more

    Sparse Polynomial Matrix Optimization

  • Jie Wang
  • Feng Guo
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , ,

    A polynomial matrix inequality is a statement that a symmetric polynomial matrix is positive semidefinite over a given constraint set. Polynomial matrix optimization concerns minimizing the smallest eigenvalue of a symmetric polynomial matrix subject to a tuple of polynomial matrix inequalities. This work explores the use of sparsity methods in reducing the complexity of sum-of-squares … Read more

    Generator Subadditive Functions for Mixed-Integer Programs

  • Gustavo Angulo
  • Burak Kocuk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Integer Programming Tags , , , ,

    For equality-constrained linear mixed-integer programs (MIP) defined by rational data, it is known that the subadditive dual is a strong dual and that there exists an optimal solution of a particular form, termed generator subadditive function. Motivated by these results, we explore the connection between Lagrangian duality, subadditive duality and generator subadditive functions for general … Read more