Linear, Cone and Semidefinite Programming

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

    On semidefinite programming relaxations of the traveling salesman problem

  • Etienne de Klerk
  • Renata Sotirov
  • Dmitrii V. Pasechnik
    • Categories Combinatorial Optimization, Semi-definite Programming Tags ,

    We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP), obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in the paper: [D. Cvetkovic, M. Cangalovic and V. Kovacevic-Vucic. Semidefinite Programming Methods for the Symmetric Traveling Salesman … Read more

    Multi-Standard Quadratic Optimization Problems

  • Immanuel M. Bomze
  • Werner Schachinger
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming

    A Standard Quadratic Optimization Problem (StQP) consists of maximizing a (possibly indefinite) quadratic form over the standard simplex. Likewise, in a multi-StQP we have to maximize a (possibly indefinite) quadratic form over the cartesian product of several standard simplices (of possibly different dimensions). Two converging monotone interior point methods are established. Further, we prove an … Read more