Semi-definite Programming

Exploiting Aggregate Sparsity in Second Order Cone Relaxations for Quadratic Constrained Quadratic Programming Problems

  • Heejune Sheen
  • Makoto Yamashita
    • Categories Quadratic Programming, Second-Order Cone Programming, Semi-definite Programming Tags , , , ,

    Among many approaches to increase the computational efficiency of semidefinite programming (SDP) relaxation for quadratic constrained quadratic programming problems (QCQPs), exploiting the aggregate sparsity of the data matrices in the SDP by Fukuda et al. (2001) and second-order cone programming (SOCP) relaxation have been popular. In this paper, we exploit the aggregate sparsity of SOCP … Read more

    Calculating Optimistic Likelihoods Using (Geodesically) Convex Optimization

  • Daniel Kuhn
  • Viet Anh Nguyen
  • Soroosh Shafieezadeh-Abadeh
  • Wolfram Wiesemann
  • Man-Chung Yue
    • Categories Generalized Convexity/Monoticity, Semi-definite Programming, Stochastic Programming Tags , , ,

    A fundamental problem arising in many areas of machine learning is the evaluation of the likelihood of a given observation under different nominal distributions. Frequently, these nominal distributions are themselves estimated from data, which makes them susceptible to estimation errors. We thus propose to replace each nominal distribution with an ambiguity set containing all distributions … Read more

    On Polyhedral and Second-Order-Cone Decompositions of Semidefinite Optimization Problems

  • Dimitris Bertsimas
  • Ryan Cory-Wright
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming, Statistics Tags , , ,

    We study a cutting-plane method for semidefinite optimization problems (SDOs), and supply a proof of the method’s convergence, under a boundedness assumption. By relating the method’s rate of convergence to an initial outer approximation’s diameter, we argue that the method performs well when initialized with a second-order-cone approximation, instead of a linear approximation. We invoke … Read more

    On Sum of Squares Representation of Convex Forms and Generalized Cauchy-Schwarz Inequalities

  • Bachir El Khadir
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , ,

    A convex form of degree larger than one is always nonnegative since it vanishes together with its gradient at the origin. In 2007, Parrilo asked if convex forms are always sums of squares. A few years later, Blekherman answered the question in the negative by showing through volume arguments that for high enough number of … Read more

    A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion

  • Stefania Bellavia
  • Jacek Gondzio
  • Margherita Porcelli
    • Categories Nonlinear Systems and Least-Squares, Semi-definite Programming Tags , , ,

    A new relaxed variant of interior point method for low-rank semidefinite programming problems is proposed in this paper. The method is a step outside of the usual interior point framework. In anticipation to converging to a low-rank primal solution, a special nearly low-rank form of all primal iterates is imposed. To accommodate such a (restrictive) … Read more

    A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics

  • Amir Ali Ahmadi
  • Georgina Hall
  • Anirudha Majumdar
    • Categories Basic Sciences Applications, Control Applications, Semi-definite Programming Tags , , , ,

    Historically, scalability has been a major challenge to the successful application of semidefinite programming in fields such as machine learning, control, and robotics. In this paper, we survey recent approaches for addressing this challenge including (i) approaches for exploiting structure (e.g., sparsity and symmetry) in a problem, (ii) approaches that produce low-rank approximate solutions to … Read more

    Error Bounds and Singularity Degree in Semidefinite Programming

  • Stefan Sremac
  • Henry Wolkowicz
  • Hugo J. Woerdeman
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    In semidefinite programming a proposed optimal solution may be quite poor in spite of having sufficiently small residual in the optimality conditions. This issue may be framed in terms of the discrepancy between forward error (the unmeasurable `true error’) and backward error (the measurable violation of optimality conditions). In his seminal work, Sturm provided an … Read more

    A convex relaxation to compute the nearest structured rank deficient matrix

  • Diego Cifuentes
    • Categories Semi-definite Programming Tags , , ,

    Given an affine space of matrices L and a matrix \theta in L, consider the problem of finding the closest rank deficient matrix to \theta on L with respect to the Frobenius norm. This is a nonconvex problem with several applications in estimation problems. We introduce a novel semidefinite programming (SDP) relaxation, and we show … Read more

    Burer-Monteiro guarantees for general semidefinite programs

  • Diego Cifuentes
    • Categories Semi-definite Programming Tags , , ,

    Consider a semidefinite program (SDP) involving an $n\times n$ positive semidefinite matrix $X$. The Burer-Monteiro method consists in solving a nonconvex program in $Y$, where $Y$ is an $n\times p$ matrix such that $X = Y Y^T$. Despite nonconvexity, Boumal et al. showed that the method provably solves generic equality-constrained SDP’s when $p > \sqrt{2m}$, … Read more

    Lower Bounds for the Bandwidth Problem

  • Truden Christian
  • Franz Rendl
  • Renata Sotirov
    • Categories Semi-definite Programming Tags , ,

    The Bandwidth Problem asks for a simultaneous permutation of the rows and columns of the adjacency matrix of a graph such that all nonzero entries are as close as possible to the main diagonal. This work focuses on investigating novel approaches to obtain lower bounds for the bandwidth problem. In particular, we use vertex partitions … Read more