Semi-definite Programming

Computational Enhancements in Low-Rank Semidefinite Programming

  • Samuel Burer
  • Changhui Choi
    • Categories Semi-definite Programming

    We discuss computational enhancements for the low-rank semidefinite programming algorithm, including the extension to block semidefinite programs, an exact linesearch procedure, and a dynamic rank reduction scheme. A truncated Newton method is also introduced, and several preconditioning strategies are proposed. Numerical experiments illustrating these enhancements are provided. Citation Manuscript, Department of Mangagement Sciences, University of … Read more

    A direct formulation for sparse PCA using semidefinite programming

  • Alexandre d'Aspremont
  • Laurent El Ghaoui
  • Michael I. Jordan
  • G. R. G. Lanckriet
    • Categories Finance and Economics, Semi-definite Programming, Statistics Tags , ,

    We examine the problem of approximating, in the Frobenius-norm sense, a positive, semidefinite symmetric matrix by a rank-one matrix, with an upper bound on the cardinality of its eigenvector. The problem arises in the decomposition of a covariance matrix into sparse factors, and has wide applications ranging from biology to finance. We use a modification … Read more

    Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

  • Y.Q. Bai
  • Cornelis Roos
  • G. Q. Wang
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J.Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximity for linear optimization (LO) problems. They have also extended the approach for LO to SDO. In … Read more

    A semidefinite programming based polyhedral cut and price algorithm for the maxcut problem

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Branch and Cut Algorithms, Semi-definite Programming Tags , , ,

    We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the … Read more

    SDP vs. LP relaxations for the moment approach in some performance evaluation problems

  • Jean-Bernard Lasserre
  • Thomas Prieto-Rumeau
    • Categories Applications - OR and Management Sciences, Finance and Economics, Semi-definite Programming

    Given a Markov process we are interested in the numerical computation of the moments of the exit time from a bounded domain. We use a moment approach which, together with appropriate semidefinite positivity moment conditions, yields a sequence of semidefinite programs (or SDP relaxations), depending on the number of moments considered, that provide a sequence … Read more

    An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones

  • Masakazu Kojima
  • Masakazu Muramatsu
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , , , , ,

    This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let ${\cal E}$ and ${\cal E}_+$ be a finite dimensional real vector space and a symmetric cone embedded in ${\cal E}$; examples of $\calE$ and $\calE_+$ include a pair of the … Read more

    Semidefinite descriptions of cones defining spectral mask constraints

  • Leonid Faybusovich
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , ,

    We discuss in detail an additive structure of cones of trigonometric polynomials nonnegative on the union of finite number of pairwise disjoint segments of the unit circle. We derive new descriptions of these cones in terms of semidefinite constraints. We explain the results of M. Krein and A. Nudelman providing a description of dual cones … Read more

    A new notion of weighted centers for semidefinite programming

  • Chek Beng Chua
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    The notion of weighted centers is essential in V-space interior-point algorithms for linear programming. Although there were some successes in generalizing this notion to semidefinite programming via weighted center equations, we still do not have a generalization that preserves two important properties — 1) each choice of weights uniquely determines a pair of primal-dual weighted … Read more

    Semidefinite Approximations for Global Unconstrained Polynomial Optimization

  • Dorina Jibetean
  • Monique Laurent
    • Categories Global Optimization Theory, Semi-definite Programming, Unconstrained Optimization Tags ,

    We consider here the problem of minimizing a polynomial function on $\oR^n$. The problem is known to be hard even for degree $4$. Therefore approximation algorithms are of interest. Lasserre \cite{lasserre:2001} and Parrilo \cite{Pa02a} have proposed approximating the minimum of the original problem using a hierarchy of lower bounds obtained via semidefinite programming relaxations. We … Read more

    Preprocessing sparse semidefinite programs via matrix completion

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
    • Categories Semi-definite Programming Tags , , , , ,

    Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more