Semi-definite Programming

Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices based on Semidefinite Programming

  • Hans D Mittelmann
  • Jiming Peng
    • Categories Applications - OR and Management Sciences, Semi-definite Programming Tags , , ,

    Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes … Read more

    Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion

  • Dimitris Bertsimas
  • Xuan Vinh Doan
  • Karthik Natarajan
  • Chung-Piaw Teo
    • Categories Semi-definite Programming, Stochastic Programming

    In this paper, we propose a semidefinite optimization (SDP) based model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of the second-stage random variables is assumed to be chosen from a set of multivariate distributions with known mean and second moment matrix. For the minimax stochastic problem with … Read more

    A Newton-CG Augmented Lagrangian Method for Semidefinite Programming

  • Defeng Sun
  • Kim-Chuan Toh
  • Xinyuan Zhao
    • Categories Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive … Read more

    Parallel implementation of a semidefinite programming solver based on CSDP on a distributed memory cluster

  • Etienne de Klerk
  • Ivan D. Ivanov
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    In this paper we present the algorithmic framework and practical aspects of implementing a parallel version of a primal-dual semidefinite programming solver on a distributed memory computer cluster. Our implementation is based on the CSDP solver and uses a message passing interface (MPI), and the ScaLAPACK library. A new feature is implemented to deal with … 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

    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

    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