Semi-definite Programming

Ideal formulations for constrained convex optimization problems with indicator variables.

  • Andrés Gómez
  • Simge Küçükyavuz
  • Linchuan Wei
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , ,

    Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give … Read more

    A simplified treatment of Ramana’s exact dual for semidefinite programming

  • Bruno F. Lourenço
  • Gabor Pataki
    • Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    In semidefinite programming the dual may fail to attain its optimal value and there could be a duality gap, i.e., the primal and dual optimal values may differ. In a striking paper, Ramana proposed a polynomial size extended dual that does not have these deficiencies and yields a number of fundamental results in complexity theory. … Read more

    Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step

  • Jalal Fadili
  • Antonio Silveti-Falls
  • Cesare Molinari
    • Categories Convex and Nonsmooth Optimization, Semi-definite Programming, Stochastic Programming

    In this paper we propose and analyze inexact and stochastic versions of the CGALP algorithm developed in the authors’ previous paper, which we denote ICGALP, that allows for errors in the computation of several important quantities. In particular this allows one to compute some gradients, proximal terms, and/or linear minimization oracles in an inexact fashion … Read more

    Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , , ,

    Sparse principal component analysis (PCA) is a popular dimensionality reduction technique for obtaining principal components which are linear combinations of a small subset of the original features. Existing approaches cannot supply certifiably optimal principal components with more than $p=100s$ of variables. By reformulating sparse PCA as a convex mixed-integer semidefinite optimization problem, we design a … Read more

    On the use of Jordan Algebras for improving global convergence of an Augmented Lagrangian method in nonlinear semidefinite programming

  • Roberto Andreani
  • Ellen H. Fukuda
  • Gabriel Haeser
  • Daiana O. Santos
  • Leonardo D. Secchin
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    Jordan Algebras are an important tool for dealing with semidefinite programming and optimization over symmetric cones in general. In this paper, a judicious use of Jordan Algebras in the context of sequential optimality conditions is done in order to generalize the global convergence theory of an Augmented Lagrangian method for nonlinear semidefinite programming. An approximate … Read more

    Parametric analysis of conic linear optimization

  • Guo Jinhai
  • Yan Zizong
  • Li Xiangjun
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    This paper focuses on the parametric analysis of a conic linear optimization problem with respect to the perturbation of the objective function along many fixed directions. We introduce the concept of the primal and dual conic linear inequality representable sets, which is very helpful for converting the correlation of the parametric conic linear optimization problems … Read more

    Disk matrices and the proximal mapping for the numerical radius

  • X.Y. Han
  • Adrian Lewis
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    Optimal matrices for problems involving the matrix numerical radius often have fields of values that are disks, a phenomenon associated with partial smoothness. Such matrices are highly structured: we experiment in particular with the proximal mapping for the radius, which often maps n-by-n random matrix inputs into a particular manifold of disk matrices that has … Read more

    2×2-convexifications for convex quadratic optimization with indicator variables

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

    In this paper, we study the convex quadratic optimization problem with indicator variables. For the bivariate case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the bivariate case as a building block, we derive … Read more

    Shape-Constrained Regression using Sum of Squares Polynomials

  • Mihaela Curmei
  • Georgina Hall
    • Categories Convex Optimization, Global Optimization, Semi-definite Programming Tags , , , , ,

    We consider the problem of fitting a polynomial function to a set of data points, each data point consisting of a feature vector and a response variable. In contrast to standard polynomial regression, we require that the polynomial regressor satisfy shape constraints, such as monotonicity, Lipschitz-continuity, or convexity. We show how to use semidefinite programming … Read more

    Bregman primal–dual first-order method and application to sparse semidefinite programming

  • Xin Jiang
  • Lieven Vandenberghe
    • Categories Semi-definite Programming Tags , , ,

    We present a new variant of the Chambolle–Pock primal–dual method with Bregman distances, analyze its convergence, and apply it to the centering problem in sparse semidefinite programming. The novelty in the method is a line search procedure for selecting suitable step sizes. The line search obviates the need for estimating the norm of the constraint … Read more