Linear, Cone and Semidefinite Programming

First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method

  • Ambros Gleixner
  • Thorsten Koch
  • Nils-Christian Kempke
  • Daniel Rehfeldt
  • Svenja Uslu
    • Categories Linear Programming

    In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving … Read more

    Adjustable Robust Optimization Reformulations of Two-Stage Worst-case Regret Minimization Problems

  • Erick Delage
  • Mehran Poursoltani
    • Categories Applications - OR and Management Sciences, Linear Programming, Robust Optimization Tags , , ,

    This paper explores the idea that two-stage worst-case regret minimization problems with either objective or right-hand side uncertainty can be reformulated as two-stage robust optimization problems and can therefore benefit from the solution schemes and theoretical knowledge that have been developed in the last decade for this class of problems. In particular, we identify conditions … Read more

    A Newton-bracketing method for a simple conic optimization problem

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    For the Lagrangian-DNN relaxation of quadratic optimization problems (QOPs), we propose a Newton-bracketing method to improve the performance of the bisection-projection method implemented in BBCPOP [to appear in ACM Tran. Softw., 2019]. The relaxation problem is converted into the problem of finding the largest zero $y^*$ of a continuously differentiable (except at $y^*$) convex function … Read more

    A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization.

  • Erling D. Andersen
  • Joachim Dahl
    • Categories Linear, Cone and Semidefinite Programming Tags ,

    A new primal-dual interior-point algorithm applicable to nonsymmetric conic optimization is proposed. It is a generalization of the famous algorithm suggested by Nesterov and Todd for the symmetric conic case, and uses primal-dual scalings for nonsymmetric cones proposed by Tuncel. We specialize Tuncel’s primal-dual scalings for the important case of 3 dimensional exponential-cones, resulting in … Read more

    Improved convergence analysis of Lasserre’s measure-based upper bounds for polynomial minimization on compact sets

  • Monique Laurent
  • Lucas Slot
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming

    We consider the problem of computing the minimum value of a polynomial f over a compact set K⊆R^n, which can be reformulated as finding a probability measure ν on K minimizing the expected value of f over K. Lasserre showed that it suffices to consider such measures of the form ν=qμ, where q is a … Read more

    Equivalences among the chi measure, Hoffman constant, and Renegar’s distance to ill-posedness

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Linear Programming, Polyhedra Tags , , , ,

    We show the equivalence among the following three condition measures of a full column rank matrix $A$: the chi measure, the signed Hoffman constant, and the signed distance to ill-posedness. The latter two measures are constructed via suitable collections of matrices obtained by flipping the signs of some rows of $A$. Our results provide a … Read more

    Consensus-Based Dantzig-Wolfe Decomposition

  • Shabbir Ahmed
  • Mohamed El Tonbari
    • Categories Linear Programming Tags , ,

    Dantzig-Wolfe decomposition (DWD) is a classical algorithm for solving large-scale linear programs whose constraint matrix involves a set of independent blocks coupled with a set of linking rows. The algorithm decomposes such a model into a master problem and a set of independent subproblems that can be solved in a distributed manner. In a typical … Read more

    Detection and Transformation of Second-Order Cone Programming Problems in a General-Purpose Algebraic Modeling Language

  • Jared Erickson
  • Robert Fourer
    • Categories Modeling Languages and Systems, Second-Order Cone Programming Tags , ,

    Diverse forms of nonlinear optimization problems can be recast to the special form of second-order cone problems (SOCPs), permitting a wider variety of highly effective solvers to be applied. Popular solvers assume, however, that the necessary transformations to required canonical forms have already been identified and carried out. We describe a general approach to the … Read more

    Polyhedral approximations of the semidefinite cone and their application

  • Akihiro Tanaka
  • Yuzhu Wang
  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming

    We develop techniques to construct a series of sparse polyhedral approximations of the semidefinite cone. Motivated by the semidefinite (SD) bases proposed by Tanaka and Yoshise (2018), we propose a simple expansion of SD bases so as to keep the sparsity of the matrices composing it. We prove that the polyhedral approximation using our expanded … Read more

    Stability Analysis for a Class of Sparse Optimization Problems

  • J.L. Xu
  • Yun-Bin Zhao
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Linear Programming

    The sparse optimization problems arise in many areas of science and engineering, such as compressed sensing, image processing, statistical and machine learning. The $\ell_{0}$-minimization problem is one of such optimization problems, which is typically used to deal with signal recovery. The $\ell_{1}$-minimization method is one of the plausible approaches for solving the $\ell_{0}$-minimization problems, and … Read more