Linear, Cone and Semidefinite Programming

A relaxed-certificate facial reduction algorithm based on subspace intersection

  • Henrik A. Friberg
    • Categories Linear, Cone and Semidefinite Programming, Second-Order Cone Programming Tags , , ,

    A “facial reduction”-like regularization algorithm is established for conic optimization problems by relaxing requirements on the reduction certificates. It requires only a linear number of reduction certificates from a constant time-solvable auxiliary problem, but is challenged by representational issues of the exposed reductions. A condition for representability is presented, analyzed for Cartesian product cones, and … Read more

    Exact SDP Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems

  • Naoki Ito
  • Sunyoung Kim
  • Shinsaku Sakaue
  • Akiko Takeda
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , , ,

    For binary polynomial optimization problems (POPs) of degree $d$ with $n$ variables, we prove that the $\lceil(n+d-1)/2\rceil$th semidefinite (SDP) relaxation in Lasserre’s hierarchy of the SDP relaxations provides the exact optimal value. If binary POPs involve only even-degree monomials, we show that it can be further reduced to $\lceil(n+d-2)/2\rceil$. This bound on the relaxation order … Read more

    The min-cut and vertex separator problem

  • Franz Rendl
  • Renata Sotirov
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We consider graph three-partitions with the objective of minimizing the number of edges between the first two partition sets while keeping the size of the third block small. We review most of the existing relaxations for this min-cut problem and focus on a new class of semidefinite relaxations, based on matrices of order $2n$ which … Read more

    Quadratic Programs with Hollows

  • Kurt M. Anstreicher
  • Samuel Burer
  • Boshi Yang
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    Let $\F$ be a quadratically constrained, possibly nonconvex, bounded set, and let $\E_1, \ldots, \E_l$ denote ellipsoids contained in $\F$ with non-intersecting interiors. We prove that minimizing an arbitrary quadratic $q(\cdot)$ over $\G := \F \setminus \cup_{k=1}^\ell \myint(\E_k)$ is no more difficult than minimizing $q(\cdot)$ over $\F$ in the following sense: if a given semidefinite-programming … Read more

    LP-based Tractable Subcones of the Semidefinite Plus Nonnegative Cone

  • Akihiro Tanaka
  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    The authors in a previous paper devised certain subcones of the semidefinite plus nonnegative cone and showed that satisfaction of the requirements for membership of those subcones can be detected by solving linear optimization problems (LPs) with $O(n)$ variables and $O(n^2)$ constraints. They also devised LP-based algorithms for testing copositivity using the subcones. In this … Read more

    Accelerated First-Order Methods for Hyperbolic Programming

  • James Renegar
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags ,

    A framework is developed for applying accelerated methods to general hyperbolic programming, including linear, second-order cone, and semidefinite programming as special cases. The approach replaces a hyperbolic program with a convex optimization problem whose smooth objective function is explicit, and for which the only constraints are linear equations (one more linear equation than for the … Read more

    Semi-infinite programming using high-degree polynomial interpolants and semidefinite programming

  • Dávid Papp
    • Categories Semi-definite Programming, Semi-infinite Programming, Statistics Tags , , , ,

    In a common formulation of semi-infinite programs, the infinite constraint set is a requirement that a function parametrized by the decision variables is nonnegative over an interval. If this function is sufficiently closely approximable by a polynomial or a rational function, then the semi-infinite program can be reformulated as an equivalent semidefinite program. Solving this … Read more

    ADMM for the SDP relaxation of the QAP

  • Danilo Oliveira
  • Henry Wolkowicz
  • Yangyang Xu
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The semidefinite programming (SDP) relaxation has proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem (QAP), arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the … Read more

    The use of squared slack variables in nonlinear second-order cone programming

  • Ellen H. Fukuda
  • Masao Fukushima
    • Categories Nonlinear Optimization, Second-Order Cone Programming Tags , , ,

    In traditional nonlinear programming, the technique of converting a problem with inequality constraints into a problem containing only equality constraints, by the addition of squared slack variables, is well-known. Unfortunately, it is considered to be an avoided technique in the optimization community, since the advantages usually do not compensate for the disadvantages, like the increase … Read more

    Optimization over Structured Subsets of Positive Semidefinite Matrices via Column Generation

  • Amir Ali Ahmadi
  • Sanjeeb Dash
  • Georgina Hall
    • Categories Approximation Algorithms, Linear, Cone and Semidefinite Programming, Nonlinear Optimization

    We develop algorithms for inner approximating the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation … Read more