Semi-definite Programming

Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    We study the equivalence among a nonconvex QOP, its CPP and DNN relaxations under the assumption that the aggregated and correlative sparsity of the data matrices of the CPP relaxation is represented by a block-clique graph $G$. By exploiting the correlative sparsity, we decompose the CPP relaxation problem into a clique-tree structured family of smaller … Read more

    Interior Point Method on Semi-definite Linear Complementarity Problems using the Nesterov-Todd (NT) Search Direction: Polynomial Complexity and Local Convergence

  • Chee-Khian Sim
    • Categories Semi-definite Programming

    We consider in this paper an infeasible predictor-corrector primal-dual path following interior point algorithm using the Nesterov-Todd (NT) search direction to solve semi-definite linear complementarity problems. Global convergence and polynomial iteration complexity of the algorithm are established. Two sufficient conditions are also given for superlinear convergence of iterates generated by the algorithm. Preliminary numerical results … Read more

    Exploiting Sparsity for Semi-Algebraic Set Volume Computation

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Matteo Tacchi
  • Tillmann Weisser
    • Categories Convex Optimization, Semi-definite Programming

    We provide a systematic deterministic numerical scheme to approximate the volume (i.e. the Lebesgue measure) of a basic semi-algebraic set whose description follows a sparsity pattern. As in previous works (without sparsity), the underlying strategy is to consider an infinite-dimensional linear program on measures whose optimal value is the volume of the set. This is … Read more

    Rank-one Convexification for Sparse Regression

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , , , , ,

    Sparse regression models are increasingly prevalent due to their ease of interpretability and superior out-of-sample performance. However, the exact model of sparse regression with an L0 constraint restricting the support of the estimators is a challenging non-convex optimization problem. In this paper, we derive new strong convex relaxations for sparse regression. These relaxations are based … Read more

    On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems

  • Feng Guo
  • Xiaoxia Sun
    • Categories Semi-definite Programming, Semi-infinite Programming Tags , , , , ,

    We consider the semi-infinite system of polynomial inequalities of the form \[ \mathbf{K}:=\{x\in\mathbb{R}^m\mid p(x,y)\ge 0,\ \ \forall y\in S\subseteq\mathbb{R}^n\}, \] where $p(X,Y)$ is a real polynomial in the variables $X$ and the parameters $Y$, the index set $S$ is a basic semialgebraic set in $\mathbb{R}^n$, $-p(X,y)$ is convex in $X$ for every $y\in S$. We … Read more

    A dual spectral projected gradient method for log-determinant semidefinite problems

  • Mituhiro Fukuda
  • Sunyoung Kim
  • Takashi Nakagaki
  • Makoto Yamashita
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    We extend the result on the spectral projected gradient method by Birgin et al in 2000 to a log-determinant semidefinite problem (SDP) with linear constraints and propose a spectral projected gradient method for the dual problem. Our method is based on alternate projections on the intersection of two convex sets, which first projects onto the … Read more

    A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis

  • Etienne de Klerk
  • Monique Laurent
    • Categories Constrained Nonlinear Optimization, Global Optimization, Semi-definite Programming

    The generalized problem of moments is a conic linear optimization problem over the convex cone of positive Borel measures with given support. It has a large variety of applications, including global optimization of polynomials and rational functions, options pricing in finance, constructing quadrature schemes for numerical integration, and distributionally robust optimization. A usual solution approach, … Read more

    Exploiting Partial Correlations in Distributionally Robust Optimization

  • Karthyek Murthy
  • Karthik Natarajan
  • Divya Padmanabhan
    • Categories Polyhedra, Robust Optimization, Semi-definite Programming Tags , , ,

    In this paper, we identify partial correlation information structures that allow for simpler reformulations in evaluating the maximum expected value of mixed integer linear programs with random objective coefficients. To this end, assuming only the knowledge of the mean and the covariance matrix entries restricted to block-diagonal patterns, we develop a reduced semidefinite programming formulation, … Read more

    Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting

  • Joaquim Dias Garcia
  • Mario Souto
  • Alvaro Viega
    • Categories Convex Optimization, Optimization Software and Modeling Systems, Semi-definite Programming Tags , , , , ,

    In contrast with many other convex optimization classes, state-of-the-art semidefinite programming solvers are yet unable to efficiently solve large scale instances. This work aims to reduce this scalability gap by proposing a novel proximal algorithm for solving general semidefinite programming problems. The proposed methodology, based on the primal-dual hybrid gradient method, allows the presence of … Read more

    A Branch-and-Cut Algorithm for Solving Mixed-integer Semidefinite Optimization Problems

  • Ken Kobayashi
  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Semi-definite Programming Tags , , ,

    This paper is concerned with a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite constraint is relaxed, and the resultant mixed-integer linear optimization problem is repeatedly solved with valid inequalities for the relaxed constraint. We prove convergence properties of the algorithm. Moreover, to speed up the computation, we … Read more