Semi-definite Programming

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

    D.C. Versus Copositive Bounds for Standard QP

  • Kurt M. Anstreicher
  • Samuel Burer
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , ,

    The standard quadratic program (QPS) is $\min_{x\in\Delta} x’Qx$, where $\Delta\subset\Re^n$ is the simplex $\Delta=\{ x\ge 0 : \sum_{i=1}^n x_i=1 \}$. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One … Read more

    Global optimization of rational functions: a semidefinite programming approach

  • Etienne de Klerk
  • Dorina Jibetean
    • Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , ,

    We consider the problem of global minimization of rational functions on $\LR^n$ (unconstrained case), and on an open, connected, semi-algebraic subset of $\LR^n$, or the (partial) closure of such a set (constrained case). We show that in the univariate case ($n=1$), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced … Read more

    The Lax conjecture is true

  • Adrian Lewis
  • Pablo A. Parrilo
  • M.V. Ramana
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    In 1958 Lax conjectured that hyperbolic polynomials in three variables are determinants of linear combinations of three symmetric matrices. This conjecture is equivalent to a recent observation of Helton and Vinnikov. Citation Department of Mathematics, Simon Fraser University, Canada Article Download View The Lax conjecture is true

    The mathematics of eigenvalue optimization

  • Adrian Lewis
    • Categories Control Applications, Nonsmooth Optimization, Semi-definite Programming Tags , , , , , , , , , , , , , , , ,

    Optimization problems involving the eigenvalues of symmetric and nonsymmetric matrices present a fascinating mathematical challenge. Such problems arise often in theory and practice, particularly in engineering design, and are amenable to a rich blend of classical mathematical techniques and contemporary optimization theory. This essay presents a personal choice of some central mathematical ideas, outlined for … Read more

    Detecting Infeasibility in Infeasible-Interior-Point Methods for Optimization

  • Michael J. Todd
    • Categories Linear Programming, Second-Order Cone Programming, Semi-definite Programming Tags , ,

    We study interior-point methods for optimization problems in the case of infeasibility or unboundedness. While many such methods are designed to search for optimal solutions even when they do not exist, we show that they can be viewed as implicitly searching for well-defined optimal solutions to related problems whose optimal solutions give certificates of infeasibility … Read more

    Solving large scale semidefinite programsvia an iterative solver onthe augmented systems

  • Kim-Chuan Toh
    • Categories Semi-definite Programming Tags , , , , , ,

    The search directions in an interior-point method for large scale semidefinite programming (SDP) can be computed by applying a Krylov iterative method to either the Schur complement equation (SCE) or the augmented equation. Both methods suffer from slow convergence as interior-point iterates approach optimality. Numerical experiments have shown that diagonally preconditioned conjugate residual method on … Read more

    First- and Second-Order Methods for Semidefinite Programming

  • Renato D.C. Monteiro
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , , , , , ,

    In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have … Read more

    Semidefinite programming and integer programming

  • Monique Laurent
  • Franz Rendl
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We survey how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems. Citation Preliminary version appeared as Report PNA-R0210, CWI, Amsterdam, April 2002. To appear as Chapter in the Handbook on Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel, eds., Elsevier Publishers. Article Download View Semidefinite programming and integer … Read more