Linear, Cone and Semidefinite Programming

Interior point methods for sufficient LCP in a wide neighborhood of the central path with optimal iteration complexity

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

    Three interior point methods are proposed for sufficient horizontal linear complementarity problems (HLCP): a large update path following algorithm, a first order corrector-predictor method, and a second order corrector-predictor method. All algorithms produce sequences of iterates in the wide neighborhood of the central path introduced by Ai and Zhang. The algorithms do not depend on … Read more

    Data-driven Chance Constrained Stochastic Program

  • Yongpei Guan
  • Ruiwei Jiang
    • Categories Semi-definite Programming, Semi-infinite Programming, Stochastic Programming

    Chance constrained programming is an effective and convenient approach to control risk in decision making under uncertainty. However, due to unknown probability distributions of random parameters, the solution obtained from a chance constrained optimization problem can be biased. In practice, instead of knowing the true distribution of a random parameter, only a series of historical … Read more

    Deriving robust counterparts of nonlinear uncertain inequalities

  • Aharon Ben-Tal
  • Dick den Hertog
  • Jean-Philippe Vial
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , , ,

    In this paper we provide a systematic way to construct the robust counterpart of a nonlinear uncertain inequality that is concave in the uncertain parameters. We use convex analysis (support functions, conjugate functions, Fenchel duality) and conic duality in order to convert the robust counterpart into an explicit and computationally tractable set of constraints. It … Read more

    On the cp-rank and minimal cp factorizations of a completely positive matrix

  • Immanuel M. Bomze
  • Florian Jarre
  • Werner Schachinger
  • Naomi Shaked-Monderer
    • Categories Linear, Cone and Semidefinite Programming Tags ,

    We show that the maximal cp-rank of $n\times n$ completely positive matrices is attained at a positive-definite matrix on the boundary of the cone of $n\times n$ completely positive matrices, thus answering a long standing question. We also show that the maximal cp-rank of $5\times 5$ matrices equals six, which proves the famous Drew-Johnson-Loewy conjecture … Read more

    The Nonnegative $ Norm Minimization under Generalized hBcmatrix Measurement

  • Lingchen Kong
  • Ziyan Luo
  • Linxia Qin
  • Naihua Xiu
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper, we consider the $l_0$ norm minimization problem with linear equation and nonnegativity constraints. By introducing the concept of generalized $Z$-matrix for a rectangular matrix, we show that this $l_0$ norm minimization with such a kind of measurement matrices and nonnegative observations can be exactly solved via the corresponding $l_p$ ($0

    A new warmstarting strategy for the primal-dual column generation method

  • Jacek Gondzio
  • Pablo Gonzalez-Brevis
    • Categories Cutting Plane Approaches, Linear Programming Tags , , , ,

    This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after … Read more

    Upper bounds for packings of spheres of several radii

  • David de Laat
  • Fernando Mário de Oliveira Filho
  • Frank Vallentin
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    We give theorems that can be used to upper bound the densities of packings of different spherical caps in the unit sphere and of translates of different convex bodies in Euclidean space. These theorems extend the linear programming bounds for packings of spherical caps and of convex bodies through the use of semidefinite programming. We … Read more

    Factoring nonnegative matrices with linear programs

  • Victor Bittorf
  • Christopher Re
  • Benjamin Recht
  • Joel Tropp
    • Categories Data-Mining, Linear Programming Tags , , , , ,

    This paper describes a new approach for computing nonnegative matrix factorizations (NMFs) with linear programming. The key idea is a data-driven model for the factorization, in which the most salient features in the data are used to express the remaining features. More precisely, given a data matrix X, the algorithm identifies a matrix C that … Read more

    A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization

  • Pietro Belotti
  • Julio C. Góez
  • Imre Pólik
  • Ted K. Ralphs
  • Tamás Terlaky
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , ,

    We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction … Read more

    Moment approximations for set-semidefinite polynomials

  • Peter J.C. Dickinson
  • Janez Povh
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    The set of polynomials which are nonnegative over a subset of the nonnegative orthant (we call them set semidefinite) have many uses in optimization. A common example of this type of set is the set of copositive matrices, where effectively we are considering nonnegativity over the entire nonnegative orthant and we limit the polynomials to … Read more