semidefinite 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

    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

    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

    Noisy Euclidean Distance Matrix Completion with a Single Missing Node

  • Lucas Pettersson
  • Stefan Sremac
  • Henry Wolkowicz
  • Fei Wang
    • Categories Convex Optimization, Semi-definite Programming, Telecommunications Tags , , , , , ,

    We present several solution techniques for the noisy single source localization problem, i.e.,~the Euclidean distance matrix completion problem with a single missing node to locate under noisy data. For the case that the sensor locations are fixed, we show that this problem is implicitly convex, and we provide a purification algorithm along with the SDP … Read more

    On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems

  • Feng Guo
  • Xiaoxia Sun
    • Categories Semi-definite Programming, Semi-infinite Programming Tags , , , , ,

    We consider the semi-infinite system of polynomial inequalities of the form \[ \mathbf{K}:=\{x\in\mathbb{R}^m\mid p(x,y)\ge 0,\ \ \forall y\in S\subseteq\mathbb{R}^n\}, \] where $p(X,Y)$ is a real polynomial in the variables $X$ and the parameters $Y$, the index set $S$ is a basic semialgebraic set in $\mathbb{R}^n$, $-p(X,y)$ is convex in $X$ for every $y\in S$. We … Read more