Semi-definite Programming

Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems

  • Michael J. Todd
  • Kim-Chuan Toh
  • Reha H. Tütüncü
    • Categories Semi-definite Programming Tags , , , ,

    We propose a primal-dual path-following Mehrotra-type predictor-corrector method for solving convex quadratic semidefinite programming (QSDP) problems. For the special case when the quadratic term has the form $\frac{1}{2} X \bul (UXU)$, we compute the search direction at each iteration from the Schur complement equation. We are able to solve the Schur complement equation efficiently via … Read more

    SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Global Optimization, Optimization Software and Modeling Systems, Semi-definite Programming Tags , , , , ,

    SparesPOP is a MATLAB implementation of a sparse semidefinite programming (SDP) relaxation method proposed for polynomial optimization problems (POPs) in the recent paper by Waki et al. The sparse SDP relaxation is based on a hierarchy of LMI relaxations of increasing dimensions by Lasserre, and exploits a sparsity structure of polynomials in POPs. The efficiency … Read more

    Reduction of symmetric semidefinite programs using the regular *-representation

  • Etienne de Klerk
  • Dmitrii V. Pasechnik
  • Alexander Schrijver
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , ,

    We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix *-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending … Read more

    On the solution of large-scale SDP problems by the modified barrier method using iterative solvers

  • Michal Kočvara
  • Michael Stingl
    • Categories Semi-definite Programming Tags , ,

    When solving large-scale semidefinite programming problems by second-order methods, the storage and factorization of the Newton matrix are the limiting factors. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable … Read more

    Solving Maximum-Entropy Sampling Problems Using Factored Masks

  • Samuel Burer
  • Jon Lee
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Semi-definite Programming Tags , , , ,

    We present a practical approach to Anstreicher and Lee’s masked spectral bound for maximum-entropy sampling, and we describe favorable results that we have obtained with a Branch-&-Bound algorithm based on our approach. By representing masks in factored form, we are able to easily satisfy a semidefiniteness constraint. Moreover, this representation allows us to restrict the … Read more

    How Far Can We Go With Primal-Dual Interior Point Methods for SDP?

  • Brian Borchers
  • Joseph Young
    • Categories Semi-definite Programming Tags ,

    Primal–dual interior point methods and the HKM method in particular have been implemented in a number of software packages for semidefinite programming. These methods have performed well in practice on small to medium sized SDP’s. However, primal–dual codes have had some trouble in solving larger problems because of the method’s storage requirements. In this paper … Read more

    Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems

  • Robert M. Freund
  • Fernando Ordóñez
  • Kim-Chuan Toh
    • Categories Semi-definite Programming Tags , ,

    We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the … Read more

    Large-scale semidefinite programs in electronic structure calculation

  • Bastiaan J. Braams
  • Mituhiro Fukuda
  • Michael L. Overton
  • Maho Nakata
  • Jerome K. Percus
  • Makoto Yamashita
  • Zhengji Zhao
    • Categories Basic Sciences Applications, Semi-definite Programming Tags , , , , ,

    Employing the variational approach having the two-body reduced density matrix (RDM) as variables to compute the ground state energies of atomic-molecular systems has been a long time dream in electronic structure theory in chemical physics/physical chemistry. Realization of the RDM approach has benefited greatly from recent developments in semidefinite programming (SDP). We present the actual … Read more

    A PTAS for the minimization of polynomials of fixed degree over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Pablo A. Parrilo
    • Categories Approximation Algorithms, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more

    Strengthened Semidefinite Bounds for Codes

  • Monique Laurent
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We give a hierarchy of semidefinite upper bounds for the maximum size $A(n,d)$ of a binary code of word length $n$ and minimum distance at least $d$. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in $n$; this is based on a result of … Read more