Semi-definite Programming

Semidefinite optimization, a spectral approach

  • M.A. van Bossum
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , , , , , ,

    This thesis is about mathematical optimization. Mathematical optimization involves the construction of methods to solve optimization problems, which can arise from real-life problems in applied science, when they are mathematically modeled. Examples come from electrical design, engineering, control theory, telecommunication, environment, finance, and logistics. This thesis deals especially with semidefinite optimization problems. Semidefinite programming is … Read more

    Implementation and Evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , , ,

    The SDPA (SemiDefinite Programming Algorithm) is a software package for solving general SDPs(SemiDefinite Programs). It is written in C++ with the help of {\it LAPACK} for numerical linear algebra for dense matrix computation. The purpose of this paper is to present a brief description of the latest version of the SDPA and its high performance … Read more

    The Trust Region Subproblem and Semidefinite Programming

  • Charles Fortin
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming, Unconstrained Optimization Tags , , ,

    The trust region subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g. function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it determines the step in trust region algorithms for function minimization. Trust region algorithms are popular for … Read more

    A Simplified/Improved HKM Direction for Certain Classes of Semidefinite Programming

  • Franz Rendl
  • Renata Sotirov
  • Henry Wolkowicz
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

    Semidefinite Programming (SDP) provides strong bounds for many NP-hard combinatorial problems. Arguably the most popular/efficient search direction for solving SDPs using a primal-dual interior point (p-d i-p) framework is the {\em HKM direction}. This direction is a Newton direction found from the linearization of a symmetrized version of the optimality conditions. For many of the … Read more

    Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope

  • Monique Laurent
    • Categories 0-1 Programming, Polyhedra, Semi-definite Programming Tags , , ,

    Hierarchies of semidefinite relaxations for $0/1$ polytopes have been constructed by Lasserre (2001a) and by Lov\’asz and Schrijver (1991), permitting to find the cut polytope of a graph on $n$ nodes in $n$ steps. We show that $\left\lceil {n\over 2} \right\rceil$ iterations are needed for finding the cut polytope of the complete graph $K_n$. Citation … Read more

    An Improved Semidefinite Programming Relaxation for the Satisfiability Problem

  • Miguel F. Anjos
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that … Read more

    Limiting behavior of the central path in semidefinite optimization

  • Etienne de Klerk
  • Margaréta Halická
  • Cornelis Roos
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    It was recently shown that, unlike in linear optimization, the central path in semidefinite optimization (SDO) does not converge to the analytic center of the optimal set in general. In this paper we analyze the limiting behavior of the central path to explain this unexpected phenomenon. This is done by deriving a new necessary and … Read more

    Characterization of the limit point of the central path in semidefinite programming

  • Anders Forsgren
  • Göran Sporre
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    In linear programming, the central path is known to converge to the analytic center of the set of optimal solutions. Recently, it has been shown that this is not necessarily true for linear semidefinite programming in the absence of strict complementarity. The present paper deals with the formulation of a convex problem whose solution defines … Read more

    SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB — User’s Guide

  • Antonis Papachristodoulou
  • Stephen Prajna
  • Pablo A. Parrilo
    • Categories Convex Optimization, Problem Solving Environments, Semi-definite Programming Tags ,

    SOSTOOLS is a free MATLAB toolbox for formulating and solving sum of squares (SOS) optimization programs. It uses a simple notation and a flexible and intuitive high-level user interface to specify the SOS programs. Currently these are solved using SeDuMi, a well-known semidefinite programming solver, while SOSTOOLS handles internally all the necessary reformulations and data … Read more

    Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices

  • Samuel Burer
    • Categories Semi-definite Programming Tags , ,

    We build upon the work of Fukuda et al.\ \cite{FuKoMuNa01} and Nakata et al.\ \cite{NaFuFuKoMu01}, in which the theory of partial positive semidefinite matrices has been applied to the semidefinite programming (SDP) problem as a technique for exploiting sparsity in the data. In contrast to their work, which improves an existing algorithm that is based … Read more