Semi-definite Programming

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

    Time-Varying Semidefinite Programs

  • Amir Ali Ahmadi
  • Bachir El Khadir
    • Categories Basic Sciences Applications, Infinite Dimensional Optimization, Semi-definite Programming Tags , , , , ,

    We study time-varying semidefinite programs (TV-SDPs), which are semidefinite programs whose data (and solutions) are functions of time. Our focus is on the setting where the data varies polynomially with time. We show that under a strict feasibility assumption, restricting the solutions to also be polynomial functions of time does not change the optimal value … Read more

    Positive semidefinite matrix approximation with a trace constraint

  • Kouhei Harada
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    We propose an efficient algorithm to solve positive a semidefinite matrix approximation problem with a trace constraint. Without constraints, it is well known that positive semidefinite matrix approximation problem can be easily solved by one-time eigendecomposition of a symmetric matrix. In this paper, we confirmed that one-time eigendecomposition is also sufficient even if a trace … Read more

    Convex computation of extremal invariant measures of nonlinear dynamical systems and Markov processes

  • Didier Henrion
  • Milan Korda
  • Igor Mezic
    • Categories Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We propose a convex-optimization-based framework for computation of invariant measures of polynomial dynamical systems and Markov processes, in discrete and con- tinuous time. The set of all invariant measures is characterized as the feasible set of an infinite-dimensional linear program (LP). The objective functional of this LP is then used to single-out a specific measure … Read more

    Semidenite Approximations of Invariant Measures for Polynomial Systems

  • Marcelo Forets
  • Didier Henrion
  • Victor Magron
    • Categories Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , , ,

    We consider the problem of approximating numerically the moments and the supports of measures which are invariant with respect to the dynamics of continuousand discrete-time polynomial systems, under semialgebraic set constraints. First, we address the problem of approximating the density and hence the support of an invariant measure which is absolutely continuous with respect to … Read more

    A multilevel analysis of the Lasserre hierarchy

  • Juan S. Campos
  • Panos Parpas
  • Ruth Misener
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. … Read more

    On positive duality gaps in semidefinite programming

  • Gabor Pataki
    • Categories Convex Optimization, Semi-definite Programming

    We study semidefinite programs (SDPs) with positive duality gaps, i.e., different optimal values in the primal and dual problems. the primal and dual problems differ. These SDPs are considered extremely pathological, they are often unsolvable, and they also serve as models of more general pathological convex programs. We first fully characterize two variable SDPs with … Read more