Linear, Cone and Semidefinite Programming

SPECTRA – a Maple library for solving linear matrix inequalities in exact arithmetic

  • Didier Henrion
  • Simone Naldi
  • Mohab Safey El Din
    • Categories Semi-definite Programming Tags , , , ,

    This document briefly describes our freely distributed Maple library {\sc spectra}, for Semidefinite Programming solved Exactly with Computational Tools of Real Algebra. It solves linear matrix inequalities in exact arithmetic and it is targeted to small-size, possibly degenerate problems for which symbolic infeasibility or feasibility certificates are required. Article Download View SPECTRA – a Maple … Read more

    A Primal-Dual Homotopy Algorithm for l_1-Minimization with l_inf-Constraints

  • Christoph Brauer
  • Dirk A. Lorenz
  • Andreas M. Tillmann
    • Categories Convex Optimization, Linear Programming Tags , , , ,

    In this paper we propose a primal-dual homotopy method for $\ell_1$-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show that there exists a piecewise linear solution path with finitely many break points for the primal problem … Read more

    A Complete Characterization of Disjunctive Conic Cuts for Mixed 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 disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more

    Moment methods in energy minimization: New bounds for Riesz minimal energy problems

  • David de Laat
    • Categories Convex Optimization, Semi-definite Programming, Semi-infinite Programming Tags , , , , , ,

    We use moment methods to construct a converging hierarchy of optimization problems to lower bound the ground state energy of interacting particle systems. We approximate the infinite dimensional optimization problems in this hierarchy by block diagonal semidefinite programs. For this we develop the necessary harmonic analysis for spaces consisting of subsets of another space, and … Read more

    Optimized choice of parameters in interior-point methods for linear programming

  • Aurelio Ribeiro Leite Oliveira
  • Luiz-Rafael Santos
  • Clovis Perin
  • Fernando Villas-Bôas
    • Categories Linear Programming, Quadratic Programming Tags , ,

    In this work, we propose a predictor-corrector interior point method for linear programming in a primal-dual context, where the next iterate is chosen by the minimization of a polynomial merit function of three variables: the first is the steplength, the second defines the central path and the third models the weight of a corrector direction. … Read more

    Can linear superiorization be useful for linear optimization problems?

  • Yair Censor
    • Categories Constrained Nonlinear Optimization, Linear Programming, Problem Solving Environments Tags , , , , , , , , ,

    Linear superiorization considers linear programming problems but instead of attempting to solve them with linear optimization methods it employs perturbation resilient feasibility-seeking algorithms and steers them toward reduced (not necessarily minimal) target function values. The two questions that we set out to explore experimentally are (i) Does linear superiorization provide a feasible point whose linear … Read more

    Linear superiorization for infeasible linear programming

  • Yair Censor
  • Yehuda Zur
    • Categories Constrained Nonlinear Optimization, Linear Programming

    Linear superiorization (abbreviated: LinSup) considers linear programming (LP) problems wherein the constraints as well as the objective function are linear. It allows to steer the iterates of a feasibility-seeking iterative process toward feasible points that have lower (not necessarily minimal) values of the objective function than points that would have been reached by the same … Read more

    Ambiguous Chance-Constrained Binary Programs under Mean-Covariance Information

  • Ruiwei Jiang
  • Siqian Shen
  • Yiling Zhang
    • Categories 0-1 Programming, Second-Order Cone Programming, Stochastic Programming

    We consider chance-constrained binary programs, where each row of the inequalities that involve uncertainty needs to be satis ed probabilistically. Only the information of the mean and covariance matrix is available, and we solve distributionally robust chance-constrained binary programs (DCBP). Using two different ambiguity sets, we equivalently reformulate the DCBPs as 0-1 second-order cone (SOC) programs. … Read more

    Positive and Z-operators on closed convex cones

  • Michael Orlitzky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Let K be a closed convex cone with dual K-star in a finite-dimensional real Hilbert space V. A positive operator on K is a linear operator L on V such that L(K) is a subset of K. Positive operators generalize the nonnegative matrices and are essential to the Perron-Frobenius theory. We say that L is … Read more

    Max-Norm Optimization for Robust Matrix Recovery

  • Ethan Fang
  • Kim-Chuan Toh
  • Han Liu
  • Wen-Xin Zhou
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , ,

    This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform … Read more