Semi-definite Programming

On metric regularity for weakly almost piecewise smooth functions and some applications in nonlinear semidefinite programming

  • Peter Fusek
    • Categories Semi-definite Programming Tags , , ,

    The one-to-one relation between the points fulfilling the KKT conditions of an optimization problem and the zeros of the corresponding Kojima function is well-known. In the present paper we study the interplay between metric regularity and strong regularity of this a priori nonsmooth function in the context of semidefinite programming. Having in mind the topological … Read more

    A Primal-Dual Regularized Interior-Point Method for Semidefinite Programming

  • Ahad Dehghani
  • Jean-Louis Goffin
  • Dominique Orban
    • Categories Semi-definite Programming Tags , , , , ,

    Interior-point methods in semidefinite programming (SDP) require the solution of a sequence of linear systems which are used to derive the search directions. Safeguards are typically required in order to handle rank-deficient Jacobians and free variables. We generalize the primal-dual regularization of \cite{friedlander-orban-2012} to SDP and show that it is possible to recover an optimal … Read more

    On bounding the bandwidth of graphs with symmetry

  • Renata Sotirov
  • Edwin van Dam
    • Categories Semi-definite Programming Tags , , , , ,

    We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the minimum cut problem. Our new semide finite programming relaxation of the minimum cut problem is obtained by strengthening the well-known semide nite programming relaxation for the quadratic assignment problem by fixing two vertices in the … Read more

    A symmetric reduction of the NT direction

  • Chantal Hergenroeder
  • Florian Jarre
    • Categories Semi-definite Programming

    A stable symmetrization of the linear systems arising in interior-point methods for solving linear programs is introduced. A comparison of the condition numbers of the resulting interior-point linear systems with other commonly used approaches indicates that the new approach may be best suitable for an iterative solution. It is shown that there is a natural … Read more

    Parallel Implementation of Successive Sparse SDP Relaxations for Large-scale Euclidean Distance Geometry Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , ,

    The Euclidean distance geometry problem (EDGP) includes locating sensors in a sensor network and constructing a molecular configuration using given distances in the two or three-dimensional Euclidean space. When the locations of some nodes, called anchors, are given, the problem can be dealt with many existing methods. An anchor-free problem in the three-dimensional space, however, … Read more

    A Semidefinite Approach to the $ Cover Problem

  • João Gouveia
  • James Pfeiffer
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , ,

    We apply theta body relaxations to the $K_i$ cover problem and use this to show polynomial time solvability for certain classes of graphs. In particular, we give an effective relaxation where all $K_i$-$p$-hole facets are valid, addressing an open question of Conforti et al \cite{conforti}. For the triangle free problem, we show for $K_n$ that … Read more

    Complexity of Ten Decision Problems in Continuous Time Dynamical Systems

  • Amir Ali Ahmadi
  • Anirudha Majumdar
  • Russ Tedrake
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags ,

    We show that for continuous time dynamical systems described by polynomial differential equations of modest degree (typically equal to three), the following decision problems which arise in numerous areas of systems and control theory cannot have a polynomial time (or even pseudo-polynomial time) algorithm unless P=NP: local attractivity of an equilibrium point, stability of an … Read more

    Hybrid LP/SDP Bounding Procedure

  • Fabio Furini
  • Emiliano Traversi
    • Categories Quadratic Programming, Semi-definite Programming Tags , , , ,

    The principal idea of this paper is to exploit Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers when tackling Binary Quadratic Problems (BQP). SDP relaxation is well-known to provide strong bounds for BQP in practice. However, the method is not typically implemented in many state-of-the-art MINLP solvers based … Read more

    Quadratic combinatorial optimization using separable underestimators

  • Christoph Buchheim
  • Emiliano Traversi
    • Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming Tags , ,

    Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a … Read more

    The Spectral Bundle Method with Second-Order Information

  • Christoph Helmberg
  • Michael L. Overton
  • Franz Rendl
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    The spectral bundle method was introduced by Helmberg and Rendl to solve a class of eigenvalue optimization problems that is equivalent to the class of semidefinite programs with the constant trace property. We investigate the feasibility and effectiveness of including full or partial second-order information in the spectral bundle method, building on work of Overton … Read more