Linear, Cone and Semidefinite Programming

On Safe Tractable Approximations of Chance Constrained Linear Matrix Inequalities

  • Aharon Ben-Tal
  • Arkadi Nemirovski
    • Categories Linear, Cone and Semidefinite Programming, Robust Optimization, Stochastic Programming Tags , ,

    In the paper, we consider the chance constrained version $$ \Prob\{A_0[x]+\sum_{i=1}^d\zeta_i A_i[x]\succeq0\}\geq1-\epsilon, $$ of an affinely perturbed Linear Matrix Inequality constraint; here $A_i[x]$ are symmetric matrices affinely depending on the decision vector $x$, and $\zeta_1,…,\zeta_d$ are independent of each other random perturbations with light tail distributions (e.g., bounded or Gaussian). Constraints of this type, playing … Read more

    On the Lovász theta-number of almost regular graphs with application to Erdös–Rényi graphs

  • Etienne de Klerk
  • Renata Sotirov
  • Michael W. Newman
  • Dmitrii V. Pasechnik
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , ,

    We consider k-regular graphs with loops, and study the Lovász theta-numbers and Schrijver theta’-numbers of the graphs that result when the loop edges are removed. We show that the theta-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets. … Read more

    The complexity of optimizing over a simplex, hypercube or sphere: a short survey

  • Etienne de Klerk
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere. These relatively simple optimization problems have many applications. We review known approximation results as well as negative (inapproximability) results from the recent literature. CitationCentER Discussion paper 2006-85 Tilburg University THe NetherlandsArticleDownload View PDF

    Primal-dual affine scaling interior point methods for linear complementarity problems

  • Florian A. Potra
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , , ,

    A first order affine scaling method and two $m$th order affine scaling methods for solving monotone linear complementarity problems (LCP) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has $O(nL^2(\log nL^2)(\log\log nL^2))$ iteration complexity. If the LCP admits a strict complementary solution then both … Read more

    Exploiting symmetries in SDP-relaxations for polynomial optimization

  • Lina Jansson Andrén
  • Jean-Bernard Lasserre
  • Cordian Riener
  • Thorsten Theobald
    • Categories Global Optimization Theory, Semi-definite Programming

    In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semi definite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization … Read more

    Correlative sparsity in primal-dual interior-point methods for LP, SDP and SOCP

  • Sunyoung Kim
  • Masakazu Kojima
  • Kazuhiro Kobayashi
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient … Read more

    A Warm-Start Approach for Large-Scale Stochastic Linear Programs

  • Marco Colombo
  • Jacek Gondzio
  • Andreas Grothey
    • Categories Linear Programming, Stochastic Programming Tags , ,

    We describe a method of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree … Read more

    On Handling Free Variables in Interior-Point Methods for Conic Linear Optimization

  • Miguel F. Anjos
  • Samuel Burer
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We revisit a regularization technique of Meszaros for handling free variables within interior-point methods for conic linear optimization. We propose a simple computational strategy, supported by a global convergence analysis, for handling the regularization. Using test problems from benchmark suites and recent applications, we demonstrate that the modern code SDPT3 modified to incorporate the proposed … Read more

    Central path curvature and iteration-complexity for redundant Klee-Minty cubes

  • Antoine Deza
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We consider a family of linear optimization problems over the n-dimensional Klee-Minty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n-2 … Read more

    New upper bounds for kissing numbers from semidefinite programming

  • Christine Bachoc
  • Frank Vallentin
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases n = 3, 4, 8, … Read more