semidefinite programming

An exact duality theory for semidefinite programming based on sums of squares

  • Igor Klep
  • Markus Schweighofer
    • Categories Semi-definite Programming Tags , , , , , , , ,

    Farkas’ lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality … Read more

    An efficient semidefinite programming relaxation for the graph partition problem

  • Renata Sotirov
    • Categories Semi-definite Programming Tags , , , ,

    We derive a new semidefinite programming relaxation for the general graph partition problem (GPP). Our relaxation is based on matrix lifting with matrix variable having order equal to the number of vertices of the graph. We show that this relaxation is equivalent to the Frieze-Jerrum relaxation [A. Frieze and M. Jerrum. Improved approximation algorithms for … Read more

    How to generate weakly infeasible semidefinite programs via Lasserre’s relaxations for polynomial optimization

  • Hayato Waki
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    Examples of weakly infeasible semidefinite programs are useful to test whether semidefinite solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre’s semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible semidefinite programs. Such examples could be used to test … Read more

    On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets

  • Gabriele Eichfelder
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    In the paper we prove that any nonconvex quadratic problem over some set $K\subset \mathbb{R}^n$ with additional linear and binary constraints can be rewritten as linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and … Read more

    On semidefinite programming bounds for graph bandwidth

  • Etienne de Klerk
  • Marianna Eisenberg-Nagy
  • Renata Sotirov
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, … Read more

    Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper, we consider block-decomposition first-order methods for solving large-scale conic semidefinite programming problems. Several ingredients are introduced to speed-up the method in its pure form such as: an aggressive choice of stepsize for performing the extragradient step; use of scaled inner products in the primal and dual spaces; dynamic update of the scaled … Read more

    A Computational Study and Survey of Methods for the Single-Row Facility Layout Problem

  • Philipp Hungerländer
  • Franz Rendl
    • Categories Facility Planning and Design, Semi-definite Programming, VLSI layout Tags , , ,

    The single row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange … Read more

    High accuracy solution of large scale semidefinite programs

  • Thomas Davi
  • Florian Jarre
    • Categories Semi-definite Programming Tags , ,

    We present a first order approach for solving semidefinite programs. Goal of this approach is to compute a solution of the SDP up to high accuracy in spite of using only partial second order information. We propose a hybrid approach that uses an accelerated projection method to generate an approximate solution and then switches to … Read more

    Solving large scale problems over the doubly nonnegative cone

  • Thomas Davi
  • Florian Jarre
    • Categories Semi-definite Programming Tags , , , ,

    The recent approach of solving large scale semidefinite programs with a first order method by minimizing an augmented primal-dual function is extended to doubly nonnegative programs. Regularity of the augmented primal-dual function is established under the condition of uniqueness and strict complementarity. The application to the doubly nonnegative cone is motivated by the fact that … Read more

    Level methods uniformly optimal for composite and structured nonsmooth convex optimization

  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    The main goal of this paper is to develop uniformly optimal first-order methods for large-scale convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. To this end, we provide a substantial generalization … Read more