Linear, Cone and Semidefinite Programming

Logarithmic-Barrier Decomposition Interior-Point Methods for Stochastic Linear Optimization in a Hilbert Space

  • Baha Alzalg
    • Categories Infinite Dimensional Optimization, Linear Programming, Stochastic Programming

    Several logarithmic-barrier interior-point methods are now available for solving two-stage stochastic optimization problems with recourse in the finite-dimensional setting. However, despite the genuine need for studying such methods in general spaces, there are no infinite-dimensional analogs of these methods. Inspired by this evident gap in the literature, in this paper, we propose logarithmic-barrier decomposition-based interior-point … Read more

    Tractable semi-algebraic approximation using Christoffel-Darboux kernel

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Swann Marx
  • Edouard Pauwels
  • Tillmann Weisser
    • Categories Semi-definite Programming Tags , , , ,

    We provide a new method to approximate a (possibly discontinuous) function using Christoffel-Darboux kernels. Our knowledge about the unknown multivariate function is in terms of finitely many moments of the Young measure supported on the graph of the function. Such an input is available when approximating weak (or measure-valued) solution of optimal control problems, entropy … Read more

    An Augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem

  • Ernesto G. Birgin
  • Walter Gómez
  • Gabriel Haeser
  • Leonardo M. Mito
  • Daiana O. Santos
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming Tags , , ,

    In this work we present an Augmented Lagrangian algorithm for nonlinear semidefinite problems (NLSDPs), which is a natural extension of its consolidated counterpart in nonlinear programming. This method works with two levels of constraints; one that is penalized and other that is kept within the subproblems. This is done in order to allow exploiting the … Read more

    CONICOPF: Conic relaxations for AC optimal power flow computations

  • Christian Bingane
  • Miguel F. Anjos
  • Sébastien Le Digabel
    • Categories Semi-definite Programming Tags , , ,

    Computational speed and global optimality are key needs for practical algorithms for the optimal power flow problem. Two convex relaxations offer a favorable trade-off between the standard second-order cone and the standard semidefinite relaxations for large-scale meshed networks in terms of optimality gap and computation time: the tight-and-cheap relaxation (TCR) and the quadratic convex relaxation … Read more

    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