Linear, Cone and Semidefinite Programming

Equivalence and Strong Equivalence between Sparsest and Least $\ell_1hBcNorm Nonnegative Solutions of Linear Systems and Their Application

  • Yun-Bin Zhao
    • Categories Applications - Science and Engineering, Convex Optimization, Linear Programming Tags , , , ,

    Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more

    Equivalence and Strong Equivalence between Sparsest and Least l1-Norm Nonnegative Solutions of Linear Systems and Their Application

  • Yun-Bin Zhao
    • Categories Convex Optimization, Global Optimization, Linear Programming Tags , , , ,

    Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more

    A First Course in Linear Optimization, version 3.0

  • Jon Lee
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Other Topics Tags , ,

    This is the “front matter” of a new open-source book on Linear Optimization. The book and associated Matlab/AMPL/Mathematica programs are freely available from: https://sites.google.com/site/jonleewebpage/home/publications/#book CitationJon Lee, “A First Course in Linear Optimization”, Third Edition, Reex Press, 2013-2017.ArticleDownload View PDF

    An inexact block-decomposition method for extra large-scale conic semidefinite programming

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , ,

    In this paper, we present an inexact block-decomposition (BD) first-order method for solving standard form conic semidefinite programming (SDP) which avoids computations of exact projections onto the manifold defined by the affine constraints and, as a result, is able to handle extra large SDP instances. The method is based on a two-block reformulation of the … Read more

    VERTICES OF SPECTRAHEDRA ARISING FROM THE ELLIPTOPE, THE THETA BODY, AND THEIR RELATIVES

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Utilizing dual descriptions of the normal cone of convex optimization problems in conic form, we characterize the vertices of semidefinite representations arising from Lovász theta body, generalizations of the elliptope, and related convex sets. Our results generalize vertex characterizations due to Laurent and Poljak from the 1990’s. Our approach also leads us to nice characterizations … Read more

    Semidefinite programming and eigenvalue bounds for the graph partition problem

  • Renata Sotirov
  • Edwin van Dam
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the total weight of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes … Read more

    A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for some NP-Hard Graph Optimization Problems

  • Elspeth Adams
  • Miguel F. Anjos
  • Franz Rendl
  • Angelika Wiegele
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Semi-definite Programming

    Many important NP-hard combinatorial problems can be efficiently approximated using semidefinite programming relaxations. We propose a new hierarchy of semidefinite relaxations for classes of such problems that based on graphs and for which the projection of the problem onto a subgraph shares the same structure as the original problem. This includes the well-studied max-cut and … Read more

    A structural geometrical analysis of weakly infeasible SDPs

  • Bruno F. Lourenço
  • Masakazu Muramatsu
  • Takashi Tsuchiya
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    In this article, we present a geometric theoretical analysis of semidefinite feasibility problems (SDFPs). We introduce the concept of hyper feasible partitions and sub-hyper feasible directions, and show how they can be used to decompose SDFPs into smaller ones, in a way that preserves most feasibility properties of the original problem. With this technique, we … Read more

    Survivable Network Coding

  • Cédric Bentz
  • Sourour Elloumi
  • Eric Gourdin
  • Thibaut Lefebvre
    • Categories Linear Programming, Network Optimization, Telecommunications

    Given a telecommunication network, modeled by a graph with capacities, we are interested in comparing the behavior and usefulness of two information propagation schemes, namely multicast and network coding, when the aforementioned network is subject to single arc failure. We consider the case with a single source node and a set of terminal nodes. The … Read more

    Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs

  • Immanuel M. Bomze
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , ,

    We study non-convex quadratic minimization problems under (possibly non-convex) quadratic and linear constraints, and characterize both Lagrangian and Semi-Lagrangian dual bounds in terms of conic optimization. While the Lagrangian dual is equivalent to the SDP relaxation (which has been known for quite a while, although the presented form, incorporating explicitly linear constraints, seems to be … Read more