Semi-definite Programming

The Strong Second-Order Sufficient Condition and Constraint Nondegeneracy in Nonlinear Semidefinite Programming and Their Implications

  • Defeng Sun
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , ,

    For a locally optimal solution to the nonlinear semidefinite programming problem, under Robinson’s constraint qualification, the following conditions are proved to be equivalent: the strong second order sufficient condition and constraint nondegeneracy; the nonsingularity of Clarke’s Jacobian of the Karush-Kuhn-Tucker system; the strong regularity of the Karush-Kuhn-Tucker point; and others. CitationTechnical Report, Department of Mathematics, … Read more

    Clustering via Minimum Volume Ellipsoids

  • Romy Shioda
  • Levent Tunçel
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining, Semi-definite Programming

    We propose minimum volume ellipsoids (MVE) clustering as an alternate clustering technique to k-means clustering for Gaussian data points and explore its value and practicality. MVE clustering allocates data points into clusters that minimizes the total volumes of each cluster’s covering ellipsoids. Motivations for this approach include its scale-invariance, its ability to handle asymmetric and … Read more

    An Explicit Semidefinite Characterization of Satisfiability for Tseitin Instances

  • Miguel F. Anjos
    • Categories 0-1 Programming, Basic Sciences Applications, Semi-definite Programming Tags , , , ,

    This paper is concerned with the application of semidefinite programming to the satisfiability problem, and in particular with using semidefinite liftings to efficiently obtain proofs of unsatisfiability. We focus on the Tseitin satisfiability instances which are known to be hard for many proof systems. We present an explicit semidefinite programming problem with dimension linear in … Read more

    Computing the stability number of a graph via linear and semidefinite programming

  • Javier F. Peña
  • Juan Vera
  • Luis F. Zuluaga
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We study certain linear and semidefinite programming lifting approximation schemes for computing the stability number of a graph. Our work is based on, and refines De Klerk and Pasechnik’s approach to approximating the stability number via copositive programming (SIAM J. Optim. 12 (2002), 875–892). We provide a closed-form expression for the values computed by the … Read more

    A NEW BARRIER FOR A CLASS OF SEMIDEFINITE PROBLEMS

  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
    • Categories Semi-definite Programming Tags , , ,

    We introduce a new barrier function to solve a class of Semidefinite Optimization Problems (SOP) with bounded variables. That class is motivated by some (SOP) as the minimization of the sum of the first few eigenvalues of symmetric matrices and graph partitioning problems. We study the primal-dual central path defined by the new barrier and … Read more

    A Semidefinite Optimization Approach for the Single-Row Layout Problem with Unequal Dimensions

  • Miguel F. Anjos
  • Andrew Kennings
  • Anthony Vannelli
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , , ,

    The facility layout problem is concerned with the arrangement of a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. We consider the one-dimensional space allocation problem (ODSAP), also known as the single-row facility layout problem, which consists in finding an optimal linear … Read more

    Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Masakazu Kojima
  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , ,

    The Semidefinite Program (SDP) is a fundamental problem in mathematical programming. It covers a wide range of applications, such as combinatorial optimization, control theory, polynomial optimization, and quantum chemistry. Solving extremely large-scale SDPs which could not be solved before is a significant work to open up a new vista of future applications of SDPs. Our … Read more

    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