Semi-definite Programming

Preprocessing sparse semidefinite programs via matrix completion

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
    • Categories Semi-definite Programming Tags , , , , ,

    Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more

    Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

  • Sung-Pil Hong
  • Levent Tunçel
    • Categories 0-1 Programming, Semi-definite Programming Tags , , ,

    We present a unifying framework to establish a lower-bound on the number of semidefinite programming based, lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by … Read more

    Solving nonconvex SDP problems of structural optimization with stability control

  • Michal Kočvara
  • Michael Stingl
    • Categories Constrained Nonlinear Optimization, Mechanical Engineering, Semi-definite Programming Tags , , ,

    The goal of this paper is to formulate and solve structural optimization problems with constraints on the global stability of the structure. The stability constraint is based on the linear buckling phenomenon. We formulate the problem as a nonconvex semidefinite programming problem and introduce an algorithm based on the Augmented Lagrangian method combined with the … Read more

    Interior Point and Semidefinite Approaches in Combinatorial Optimization

  • Kartik Krishnan
  • Tamás Terlaky
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

    Interior-point methods (IPMs), originally conceived in the context of linear programming have found a variety of applications in integer programming, and combinatorial optimization. This survey presents an up to date account of IPMs in solving NP-hard combinatorial optimization problems to optimality, and also in developing approximation algorithms for some of them. The surveyed approaches include … Read more

    A New Computational Approach to Density Estimation with Semidefinite Programming

  • Tadayoshi Fushiki
  • Takashi Tsuchiya
  • Shingo Horiuchi
    • Categories Data-Mining, Semi-definite Programming, Statistics Tags , , , ,

    Density estimation is a classical and important problem in statistics. The aim of this paper is to develop a new computational approach to density estimation based on semidefinite programming (SDP), a new technology developed in optimization in the last decade. We express a density as the product of a nonnegative polynomial and a base density … Read more

    A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Graphs and Matroids, Parallel Algorithms, Semi-definite Programming Tags , , , , ,

    A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of … Read more

    Sums of Squares Relaxations of Polynomial Semidefinite Programs

  • Masakazu Kojima
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , , , ,

    A polynomial SDP (semidefinite program) minimizes a polynomial objective function over a feasible region described by a positive semidefinite constraint of a symmetric matrix whose components are multivariate polynomials. Sums of squares relaxations developed for polynomial optimization problems are extended to propose sums of squares relaxations for polynomial SDPs with an additional constraint for the … Read more

    The Reduced Density Matrix Method for Electronic Structure Calculations and the Role of Three-Index Representability Conditions

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

    The variational approach for electronic structure based on the two-body reduced density matrix is studied, incorporating two representability conditions beyond the previously used $P$, $Q$ and $G$ conditions. The additional conditions (called $T1$ and $T2$ here) are implicit in work of R.~M.~Erdahl [Int.\ J.\ Quantum Chem.\ {\bf13}, 697–718 (1978)] and extend the well-known three-index diagonal … Read more

    On Extracting Maximum Stable Sets in Perfect Graphs Using Lovasz’s Theta Function

  • Xiaofei Fan
  • E. Alper Yildirim
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lov{\’a}sz’s theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable set in a … Read more

    Local Minima and Convergence in Low-Rank Semidefinite Programming

  • Samuel Burer
  • Renato D.C. Monteiro
    • Categories Combinatorial Optimization, Semi-definite Programming

    The low-rank semidefinite programming problem (LRSDP_r) is a restriction of the semidefinite programming problem (SDP) in which a bound r is imposed on the rank of X, and it is well known that LRSDP_r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP_r and … Read more