Linear, Cone and Semidefinite Programming

Convergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic Programming

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , ,

    Mehrotra and Ozevin computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the barrier decomposition proposed and analyzed in Zhao, and Mehrotra and Ozevin. This paper provides a theoretical foundation for the weighted barrier decomposition algorithm (WBDA). Although the worst case analysis of the WBDA achieves a first-stage iteration complexity bound that is … Read more

    A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs

  • Samuel Burer
  • Jieqiu Chen
    • Categories 0-1 Programming, Global Optimization Theory, Second-Order Cone Programming Tags , , , ,

    Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more

    Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes

  • Miguel F. Anjos
  • Anthony Vannelli
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , , ,

    This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more

    Exploiting Sparsity in SDP Relaxation for Sensor Network Localization

  • Sunyoung Kim
  • Masakazu Kojima
  • Hayato Waki
    • Categories Semi-definite Programming Tags , , ,

    A sensor network localization problem can be formulated as a quadratic optimization problem (QOP). For quadratic optimization problems, semidefinite programming (SDP) relaxation by Lasserre with relaxation order 1 for general polynomial optimization problems (POPs) is known to be equivalent to the sparse SDP relaxation by Waki {¥it et al.} with relaxation order 1, except the … Read more

    Lower Bounds for Measurable Chromatic Numbers

  • Christine Bachoc
  • Fernando Mário de Oliveira Filho
  • Frank Vallentin
  • Gabriele Nebe
    • Categories Semi-definite Programming Tags , , , ,

    The Lov\’asz theta function provides a lower bound for the chromatic number of finite graphs based on the solution of a semidefinite program. In this paper we generalize it so that it gives a lower bound for the measurable chromatic number of distance graphs on compact metric spaces. In particular we consider distance graphs on … Read more

    An Adaptive Linear Approximation Algorithm for Copositive Programs

  • Stefan Bundfuss
  • Mirjam Duer
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We study linear optimization problems over the cone of copositive matrices. These problems appear in nonconvex quadratic and binary optimization, for instance the maximum clique problem and other combinatorial problems can be reformulated as such a problem. We present new polyhedral inner and outer approximations of the copositive cone which we show to be exact … Read more

    A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region

  • Eissa Nematollahi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , ,

    By introducing some redundant Klee-Minty constructions, we have previously shown that the central path may visit every vertex of the Klee-Minty cube having $2^n-2$ “sharp” turns in dimension $n$. In all of the previous constructions, the maximum of the distances of the redundant constraints to the corresponding facets is an exponential number of the dimension … Read more

    Limiting behavior and analyticity of weighted central paths in semidefinite programming

  • Margaréta Halická
  • Mária Trnovská
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    In this paper we analyze the limiting behavior of infeasible weighted central paths in semidefinite programming under the assumption that a strictly complementary solution exists. We show that the paths associated with the “square root” symmetrization of the weighted centrality condition are analytic functions of the barrier parameter $\mu$ even at $\mu=0$ if and only … Read more

    An Information Geometric Approach to Polynomial-time Interior-point Algorithms: Complexity Bound via Curvature Integral

  • Atsumi Ohara
  • Takashi Tsuchiya
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , ,

    In this paper, we study polynomial-time interior-point algorithms in view of information geometry. Information geometry is a differential geometric framework which has been successfully applied to statistics, learning theory, signal processing etc. We consider information geometric structure for conic linear programs introduced by self-concordant barrier functions, and develop a precise iteration-complexity estimate of the polynomial-time … Read more

    Block-diagonal semidefinite programming hierarchies for 0/1 programming

  • N. Gvozdenovic
  • Monique Laurent
  • Frank Vallentin
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Lovasz and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for general 0/1 linear programming problems. In this paper these two constructions are revisited and a new, block-diagonal hierarchy is proposed. It has the advantage of being computationally less costly while being at least as strong as the Lovasz-Schrijver hierarchy. It is applied … Read more