Semi-definite Programming

On the weak second-order optimality condition for nonlinear semidefinite and second-order cone programming

  • Ellen H. Fukuda
  • Gabriel Haeser
  • Leonardo M. Mito
    • Categories Linear, Cone and Semidefinite Programming, Second-Order Cone Programming, Semi-definite Programming Tags , ,

    Second-order necessary optimality conditions for nonlinear conic programming problems that depend on a single Lagrange multiplier are usually built under nondegeneracy and strict complementarity. In this paper we establish a condition of such type for two classes of nonlinear conic problems, namely semidefinite and second-order cone programming, assuming Robinson’s constraint qualification and a generalized form … Read more

    Necessary and sufficient conditions for rank-one generated cones

  • C.J. Argue
  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Quadratic Programming, Semi-definite Programming

    A closed convex conic subset $\cS$ of the positive semidefinite (PSD) cone is rank-one generated (ROG) if all of its extreme rays are generated by rank-one matrices. The ROG property of $\cS$ is closely related to the exactness of SDP relaxations of nonconvex quadratically constrained quadratic programs (QCQPs) related to $\cS$. We consider the case … Read more

    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