Linear, Cone and Semidefinite Programming

A Filter Algorithm for Nonlinear Semidefinite Programming

  • Walter Gómez
  • Héctor Ramírez
    • Categories Nonlinear Optimization, Semi-definite Programming

    This paper proposes a filter method for solving nonlinear semidefinite programming problems. Our method extends to this setting the filter SQP (sequential quadratic programming) algorithm, recently introduced for solving nonlinear programming problems, obtaining their respective global convergence results. CitationCMM-B-06/10 – 171 Centre for Mathematical Modelling, UMR 2071, Universidad de Chile-CNRS. Casilla 170-3 Santiago 3, Chile … Read more

    Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps

  • Christine Bachoc
  • Frank Vallentin
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we apply the semidefinite programming approach developed by the authors to obtain new upper bounds for codes in spherical caps. We compute new upper bounds for the one-sided kissing number in several dimensions where we in particular get a new tight bound in dimension 8. Furthermore we show how to use the … Read more

    A Matrix-lifting Semidefinite Relaxation for the Quadratic Assignment Problem

  • Yichuan Ding
  • Henry Wolkowicz
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Semi-definite Programming Tags ,

    The quadratic assignment problem (\QAP) is arguably one of the hardest of the NP-hard discrete optimization problems. Problems of dimension greater than 20 are considered to be large scale. Current successful solution techniques depend on branch and bound methods. However, it is difficult to get \emph{strong and inexpensive} bounds. In this paper we introduce a … Read more

    Copositive and Semidefinite Relaxations of the Quadratic Assignment Problem

  • Janez Povh
  • Franz Rendl
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Semidefinite relaxations of the quadratic assignment problem (QAP) have recently turned out to provide good approximations to the optimal value of QAP. We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it … Read more

    On the Copositive Representation of Binary and Continuous Nonconvex Quadratic Programs

  • Samuel Burer
    • Categories Global Optimization, Integer Programming, Linear, Cone and Semidefinite Programming

    We establish that any nonconvex quadratic program having a mix of binary and continuous variables over a bounded feasible set can be represented as a linear program over the dual of the cone of copositive matrices. This result can be viewed as an extension of earlier separate results, which have established the copositive representation of … Read more

    A Simpler and Tighter Redundant Klee-Minty Construction

  • Eissa Nematollahi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , ,

    By introducing redundant Klee-Minty examples, we have previously shown that the central path can be bent along the edges of the Klee-Minty cubes, thus having $2^n-2$ sharp turns in dimension $n$. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler … Read more

    On the Second-Order Feasibility Cone: Primal-Dual Representation and Efficient Projection

  • Alexandre Belloni
  • Robert M. Freund
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We study the second-order feasibility cone F = { y : \| My \| \le g^Ty } for given data (M,g). We construct a new representation for this cone and its dual based on the spectral decomposition of the matrix M^TM – gg^T. This representation is used to efficiently solve the problem of projecting an … Read more

    An Efficient Re-scaled Perceptron Algorithm for Conic Systems

  • Alexandre Belloni
  • Robert M. Freund
  • Santosh Vempala
    • Categories Linear, Cone and Semidefinite Programming

    The classical perceptron algorithm is an elementary row-action/relaxation algorithm for solving a homogeneous linear inequality system Ax > 0. A natural condition measure associated with this algorithm is the Euclidean width t of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/t^2, see Rosenblatt 1962. Dunagan and … Read more

    On Safe Tractable Approximations of Chance Constrained Linear Matrix Inequalities

  • Aharon Ben-Tal
  • Arkadi Nemirovski
    • Categories Linear, Cone and Semidefinite Programming, Robust Optimization, Stochastic Programming Tags , ,

    In the paper, we consider the chance constrained version $$ \Prob\{A_0[x]+\sum_{i=1}^d\zeta_i A_i[x]\succeq0\}\geq1-\epsilon, $$ of an affinely perturbed Linear Matrix Inequality constraint; here $A_i[x]$ are symmetric matrices affinely depending on the decision vector $x$, and $\zeta_1,…,\zeta_d$ are independent of each other random perturbations with light tail distributions (e.g., bounded or Gaussian). Constraints of this type, playing … Read more

    On the Lovász theta-number of almost regular graphs with application to Erdös–Rényi graphs

  • Etienne de Klerk
  • Renata Sotirov
  • Michael W. Newman
  • Dmitrii V. Pasechnik
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , ,

    We consider k-regular graphs with loops, and study the Lovász theta-numbers and Schrijver theta’-numbers of the graphs that result when the loop edges are removed. We show that the theta-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets. … Read more