Semi-definite Programming

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

    Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Hayato Waki
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , , , , , ,

    Sequences of generalized Lagrangian duals and their SOS (sums of squares of polynomials) relaxations for a POP (polynomial optimization problem) are introduced. Sparsity of polynomials in the POP is used to reduce the sizes of the Lagrangian duals and their SOS relaxations. It is proved that the optimal values of the Lagrangian duals in the … Read more

    A masked spectral bound for maximum-entropy sampling

  • Kurt M. Anstreicher
  • Jon Lee
    • Categories Nonsmooth Optimization, Semi-definite Programming, Statistics Tags , , ,

    We introduce a new masked spectral bound for the maximum-entropy sampling problem. This bound is a continuous generalization of the very effective spectral partition bound. Optimization of the masked spectral bound requires the minimization of a nonconvex, nondifferentiable function over a semidefiniteness constraint. We describe a nonlinear affine scaling algorithm to approximately minimize the bound. … Read more

    A Semidefinite Programming Approach for the Nearest Correlation Matrix Problem

  • Miguel F. Anjos
  • Henry Wolkowicz
  • Nicholas J. Higham
  • Pawoumodom L. Takouda
    • Categories Finance and Economics, Optimization Software and Modeling Systems, Semi-definite Programming

    The nearest \cm\ problem is to find a positive semidefinite matrix with unit diagonal that is nearest in the Frobenius norm to a given symmetric matrix $A$. This problem can be formulated as an optimization problem with a quadratic objective function and semidefinite programming constraints. Using such a formulation, we derive and test a primal-dual … Read more

    Strengthened Existence and Uniqueness Conditions for Search Directions in Semidefinite Programming

  • Levent Tunçel
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    Primal-dual interior-point (p-d i-p) methods for Semidefinite Programming (SDP) are generally based on solving a system of matrix equations for a Newton type search direction for a symmetrization of the optimality conditions. These search directions followed the derivation of similar p-d i-p methods for linear programming (LP). Among these, a computationally interesting search direction is … Read more

    Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming

  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , ,

    This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X S + SX = 2 \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. … Read more

    Asymptotic behavior of the central path for a special class of degenerate SDP problems

  • João Xavier da Cruz Neto
  • Orizon Pereira Ferreira
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , , ,

    This paper studies the asymptotic behavior of the central path $(X(\nu),S(\nu),y(\nu))$ as $\nu \downarrow 0$ for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose “degenerate diagonal blocks” $X_{\cT}(\nu)$ and $S_{\cT}(\nu)$ of the central path are assumed to satisfy $\max\{ \|X_{\cT}(\nu)\|, \|S_{\cT}(\nu)\| \} … Read more

    Error bounds and limiting behavior of weighted paths associated with the SDP map ^{1/2}SX^{1/2}$

  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , , ,

    This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X^{1/2}S X^{1/2} = \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown … Read more