Linear, Cone and Semidefinite Programming

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

    A semidefinite programming hierarchy for packing problems in discrete geometry

  • David de Laat
  • Frank Vallentin
    • Categories Infinite Dimensional Optimization, Semi-definite Programming Tags , , ,

    Packing problems in discrete geometry can be modeled as finding independent sets in infinite graphs where one is interested in independent sets which are as large as possible. For finite graphs one popular way to compute upper bounds for the maximal size of an independent set is to use Lasserre’s semidefinite programming hierarchy. We generalize … Read more

    A Two-Variable Approach to the Two-Trust-Region Subproblem

  • Samuel Burer
  • Boshi Yang
    • Categories Quadratic Programming, Semi-definite Programming Tags , ,

    The trust-region subproblem minimizes a general quadratic function over an ellipsoid and can be solved in polynomial time using a semidefinite-programming (SDP) relaxation. Intersecting the feasible set with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing algorithms do not use SDP. In this paper, … Read more

    An inexact proximal path-following algorithm for constrained convex minimization

  • Volkan Cevher
  • Quoc Tran-Dinh
  • Anastasios Kyrillidis
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    Many scientific and engineering applications feature large-scale non-smooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the non-smooth objective is equipped with a tractable proximity operator and that the convex constraints afford a self-concordant barrier. We provide a new joint treatment … Read more

    A First-Order Algorithm for the A-Optimal Experimental Design Problem: A Mathematical Programming Approach

  • Selin Damla Ahipasaoglu
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , ,

    We develop and analyse a first-order algorithm for the A-optimal experimental design problem. The problem is first presented as a special case of a parametric family of optimal design problems for which duality results and optimality conditions are given. Then, two first-order (Frank-Wolfe type) algorithms are presented, accompanied by a detailed time-complexity analysis of the … Read more

    Fast implementation for semidefinite programs with positive matrix completion

  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Parallel Algorithms, Semi-definite Programming Tags , , ,

    Solving semidefinite programs (SDP) in a short time is the key to managing various mathematical optimization problems in practical time. The matrix-completion primal-dual interior-point method (MC-PDIPM) extracts a structural sparsity of input SDP by factorizing the variable matrices, and it shrinks the computation time. In this paper, we propose a new factorization based on the … Read more

    On the irreducibility, Lyapunov rank, and automorphisms of speical Bishop-Phelps cones

  • M. Seetharama Gowda
  • David Trott
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , ,

    Motivated by optimization considerations, we consider special Bishop-Phelps cones in R^n which are of the form {(t,x): t \geq ||x||} for some norm on R^(n-1). We show that for n bigger than 2, such cones are always irreducible. De fining the Lyapunov rank of a proper cone K as the dimension of the Lie algebra of … Read more