Linear, Cone and Semidefinite Programming

Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    We study the equivalence among a nonconvex QOP, its CPP and DNN relaxations under the assumption that the aggregated and correlative sparsity of the data matrices of the CPP relaxation is represented by a block-clique graph $G$. By exploiting the correlative sparsity, we decompose the CPP relaxation problem into a clique-tree structured family of smaller … Read more

    Recovery of a mixture of Gaussians by sum-of-norms clustering

  • Tao Jiang
  • Stephen A. Vavasis
  • Chen Wen Zhai
    • Categories Second-Order Cone Programming, Statistics

    Sum-of-norms clustering is a method for assigning $n$ points in $\R^d$ to $K$ clusters, $1\le K\le n$, using convex optimization. Recently, Panahi et al.\ proved that sum-of-norms clustering is guaranteed to recover a mixture of Gaussians under the restriction that the number of samples is not too large. The purpose of this note is to … Read more

    Interior Point Method on Semi-definite Linear Complementarity Problems using the Nesterov-Todd (NT) Search Direction: Polynomial Complexity and Local Convergence

  • Chee-Khian Sim
    • Categories Semi-definite Programming

    We consider in this paper an infeasible predictor-corrector primal-dual path following interior point algorithm using the Nesterov-Todd (NT) search direction to solve semi-definite linear complementarity problems. Global convergence and polynomial iteration complexity of the algorithm are established. Two sufficient conditions are also given for superlinear convergence of iterates generated by the algorithm. Preliminary numerical results … Read more

    Exploiting Sparsity for Semi-Algebraic Set Volume Computation

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Matteo Tacchi
  • Tillmann Weisser
    • Categories Convex Optimization, Semi-definite Programming

    We provide a systematic deterministic numerical scheme to approximate the volume (i.e. the Lebesgue measure) of a basic semi-algebraic set whose description follows a sparsity pattern. As in previous works (without sparsity), the underlying strategy is to consider an infinite-dimensional linear program on measures whose optimal value is the volume of the set. This is … Read more

    Rank-one Convexification for Sparse Regression

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , , , , ,

    Sparse regression models are increasingly prevalent due to their ease of interpretability and superior out-of-sample performance. However, the exact model of sparse regression with an L0 constraint restricting the support of the estimators is a challenging non-convex optimization problem. In this paper, we derive new strong convex relaxations for sparse regression. These relaxations are based … Read more

    Towards an efficient Augmented Lagrangian method for convex quadratic programming

  • Luís Felipe Bueno
  • Gabriel Haeser
  • Luiz-Rafael Santos
    • Categories Constrained Nonlinear Optimization, Linear Programming, Quadratic Programming Tags , , , ,

    Interior point methods have attracted most of the attention in the recent decades for solving large scale convex quadratic programming problems. In this paper we take a different route as we present an augmented Lagrangian method for convex quadratic programming based on recent developments for nonlinear programming. In our approach, box constraints are penalized while … Read more

    Convexification of polynomial optimization problems by means of monomial patterns

  • Gennadiy Averkov
  • Benjamin Peters
  • Sebastian Sager
    • Categories Bound-constrained Optimization, Global Optimization Theory, Linear, Cone and Semidefinite Programming

    Convexification is a core technique in global polynomial optimization. Currently, two different approaches compete in practice and in the literature. First, general approaches rooted in nonlinear programming. They are comparitively cheap from a computational point of view, but typically do not provide good (tight) relaxations with respect to bounds for the original problem. Second, approaches … Read more

    A Geometrical Analysis of a Class of Nonconvex Conic Programs for Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We present a geometrical analysis on the completely positive programming reformulation of quadratic optimization problems and its extension to polynomial optimization problems with a class of geometrically defined nonconvex conic programs and their covexification. The class of nonconvex conic programs is described with a linear objective function in a linear space $V$, and the constraint … 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

    The convex hull of a quadratic constraint over a polytope

  • Santanu S. Dey
  • Asteroide Santana
    • Categories Global Optimization Theory, Quadratic Programming, Second-Order Cone Programming

    A quadratically constrained quadratic program (QCQP) is an optimization problem in which the objective function is a quadratic function and the feasible region is defined by quadratic constraints. Solving non-convex QCQP to global optimality is a well-known NP-hard problem and a traditional approach is to use convex relaxations and branch-and-bound algorithms. This paper makes a … Read more