Linear, Cone and Semidefinite Programming

A comparison of the Sherali-Adams, Lov\’asz-Schrijver and Lasserre relaxations for sh-1$ programming

  • Monique Laurent
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    Sherali and Adams \cite{SA90}, Lov\’asz and Schrijver \cite{LS91} and, recently, Lasserre \cite{Las01b} have proposed lift and project methods for constructing hierarchies of successive linear or semidefinite relaxations of a $0-1$ polytope $P\subseteq \oR^n$ converging to $P$ in $n$ steps. Lasserre’s approach uses results about representations of positive polynomials as sums of squares and the dual … Read more

    On the convergence of the central path in semidefinite optimization

  • Etienne de Klerk
  • Margaréta Halická
  • Cornelis Roos
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    The central path in linear optimization always converges to the analytic center of the optimal set. This result was extended to semidefinite programming by Goldfarb and Scheinberg (SIAM J. Optim. 8: 871-886, 1998). In this paper we show that this latter result is not correct in the absence of strict complementarity. We provide a counterexample, … Read more

    Geometry of Semidefinite Max-Cut Relaxations via Ranks

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

    Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and … Read more

    Improved complexity for maximum volume inscribed ellipsoids

  • Kurt M. Anstreicher
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    Let $\Pcal=\{x | Ax\le b\}$, where $A$ is an $m\times n$ matrix. We assume that $\Pcal$ contains a ball of radius one centered at the origin, and is contained in a ball of radius $R$ centered at the origin. We consider the problem of approximating the maximum volume ellipsoid inscribed in $\Pcal$. Such ellipsoids have … Read more

    An Interior-Point Perspective on Sensitivity Analysis in Semidefinite Programming

  • E. Alper Yildirim
    • Categories Semi-definite Programming Tags , ,

    We study the asymptotic behavior of the interior-point bounds arising from the work of Yildirim and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. For perturbations of the right-hand side vector and the cost matrix, we show that the interior-point bounds evaluated on the central path using the Monteiro-Zhang … Read more

    A Computational Study of a Gradient-Based Log-Barrier Algorithm for a Class of Large-Scale SDPs

  • Samuel Burer
  • Renato D.C. Monteiro
  • Yin Zhang
    • Categories Combinatorial Optimization, Semi-definite Programming, Unconstrained Optimization Tags , , , ,

    The authors of this paper recently introduced a transformation \cite{BuMoZh99-1} that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based … Read more

    New Results on Quadratic Minimization

  • Yinyu Ye
  • Shuzhong Zhang
    • Categories Quadratic Programming, Semi-definite Programming Tags , ,

    In this paper we present several new results on minimizing an indefinite quadratic function under quadratic/linear constraints. The emphasis is placed on the case where the constraints are two quadratic inequalities. This formulation is known as {\em the extended trust region subproblem}\/ and the computational complexity of this problem is still unknown. We consider several … Read more

    A New Second-Order Cone Programming Relaxation for MAX-CUT problems

  • Masakazu Muramatsu
  • Tsunehiro Suzuki
    • Categories Combinatorial Optimization, Global Optimization Applications, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a new relaxation scheme for the MAX-CUT problem using second-order cone programming. We construct relaxation problems to reflect the structure of the original graph. Numerical experiments show that our relaxation approaches give better bounds than those based on the spectral decomposition proposed by Kim and Kojima, and that the efficiency of the branch-and-bound … Read more

    Solving standard quadratic optimization problems via linear, semidefinite and copositive programming

  • Immanuel M. Bomze
  • Etienne de Klerk
    • Categories Combinatorial Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities … Read more

    A Linear Programming Approach to Semidefinite Programming Problems

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Combinatorial Optimization, Linear Programming, Semi-definite Programming Tags , , , , ,

    Until recently, the study of interior point methods has dominated algorithmic research in semidefinite programming (SDP). From a theoretical point of view, these interior point methods offer everything one can hope for; they apply to all SDP’s, exploit second order information and offer polynomial time complexity. Still for practical applications with many constraints $k$, the … Read more