Linear, Cone and Semidefinite Programming

SDPT3 – a MATLAB software package for semidefinite-quadratic-linear programming, version 3.0

  • Michael J. Todd
  • Kim-Chuan Toh
  • Reha H. Tütüncü
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , ,

    This software package is a MATLAB implementation of infeasible path-following algorithms for solving conic programming problems whose constraint cone is a product of semidefinite cones, second-order cones, and/or nonnegative orthants. It employs a predictor-corrector primal-dual path-following method, with either the HKM or the NT search direction. The basic code is written in Matlab, but key … Read more

    Semi-infinite linear programming approaches to semidefinite programming problems

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Convex and Nonsmooth Optimization, Infinite Dimensional Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Interior point methods, the traditional methods for the $SDP$, are fairly limited in the sizes of problems they can handle. This paper deals with an $LP$ approach to overcome some of these shortcomings. We begin with a semi-infinite linear programming formulation of the $SDP$ and discuss the issue of its discretization in some detail. We … Read more

    On the Primal-Dual Geometry of Level Sets in Linear and Conic Optimization

  • Robert M. Freund
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    For a conic optimization problem: minimize cx subject to Ax=b, x \in C, we present a geometric relationship between the maximum norms of the level sets of the primal and the inscribed sizes of the level sets of the dual (or the other way around). CitationMIT Operations Research Center Working PaperArticleDownload View PDF

    On the Riemannian Geometry Defined by Self-Concordant Barriers and Interior-Point Methods

  • Yurii Nesterov
  • Michael J. Todd
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We consider the Riemannian geometry defined on a convex set by the Hessian of a self-concordant barrier function, and its associated geodesic curves. These provide guidance for the construction of efficient interior-point methods for optimizing a linear function over the intersection of the set with an affine manifold. We show that algorithms that follow the … Read more

    Polynomial interior point cutting plane methods

  • John E. Mitchell
    • Categories Cutting Plane Approaches, Linear Programming, Nonsmooth Optimization Tags , , ,

    Polynomial cutting plane methods based on the logarithmic barrier function and on the volumetric center are surveyed. These algorithms construct a linear programming relaxation of the feasible region, find an appropriate approximate center of the region, and call a separation oracle at this approximate center to determine whether additional constraints should be added to the … Read more

    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