Semi-definite Programming

Monotonicity of L”{o}wner Operators and Its Applications to Symmetric Cone Complementarity Problems

  • Lingchen Kong
  • Levent Tunçel
  • Naihua Xiu
    • Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity, Semi-definite Programming Tags , , , ,

    This paper focuses on monotone L\”{o}wner operators in Euclidean Jordan algebras and their applications to the symmetric cone complementarity problem (SCCP). We prove necessary and sufficient conditions for locally Lipschitz L\”{o}wner operators to be monotone, strictly monotone and strongly monotone. We also study the relationship between monotonicity and operator-monotonicity of L\”{o}wner operators. As a by-product … Read more

    On the Closedness of the Linear Image of a Closed Convex Cone

  • Gabor Pataki
    • Categories Convex Optimization, Second-Order Cone Programming, Semi-definite Programming

    When is the linear image of a closed convex cone closed? We present very simple, and intuitive necessary conditions, which 1) unify, and generalize seemingly disparate, classical sufficient conditions: polyhedrality of the cone, and “Slater” type conditions; 2) are necessary and sufficient, when the dual cone belongs to a class, that we call nice cones. … Read more

    Convex sets with semidefinite representation

  • Jean-Bernard Lasserre
    • Categories Convex Optimization, Global Optimization, Semi-definite Programming

    We provide a sufficient condition on a class of compact basic semialgebraic sets K for their convex hull to have a lifted semidefinite representation (SDr). This lifted SDr is explicitly expressed in terms of the polynomials that define K. Examples are provided. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we … Read more

    A PARALLEL interior point decomposition algorithm for block-angular semidefinite programs

  • Kartik Krishnan Sivaramakrishnan
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the {\em matrix completion} scheme of Fukuda et al. \cite{fukuda_et_al} to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase … Read more

    A Unified Theorem on SDP Rank Reduction

  • Anthony Man-Cho So
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags ,

    We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices. Specifically, let $A_1,\ldots,A_m \in \R^{n\times n}$ be symmetric, positive semidefinite matrices, and let $b_1,\ldots,b_m \ge 0$. We show that if there exists a symmetric, positive semidefinite matrix $X$ to the system $A_i \bullet X … Read more

    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. Citation CMM-B-06/10 – 171 Centre for Mathematical Modelling, UMR 2071, Universidad de Chile-CNRS. Casilla 170-3 Santiago 3, … 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 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

    Exploiting symmetries in SDP-relaxations for polynomial optimization

  • Lina Jansson Andrén
  • Jean-Bernard Lasserre
  • Cordian Riener
  • Thorsten Theobald
    • Categories Global Optimization Theory, Semi-definite Programming

    In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semi definite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization … Read more