Semi-definite Programming

A Filter Algorithm for Nonlinear Semidefinite Programming

  • Walter Gómez
  • Héctor Ramírez
    • Categories Nonlinear Optimization, Semi-definite Programming

    This paper proposes a filter method for solving nonlinear semidefinite programming problems. Our method extends to this setting the filter SQP (sequential quadratic programming) algorithm, recently introduced for solving nonlinear programming problems, obtaining their respective global convergence results. Citation CMM-B-06/10 – 171 Centre for Mathematical Modelling, UMR 2071, Universidad de Chile-CNRS. Casilla 170-3 Santiago 3, … Read more

    A Matrix-lifting Semidefinite Relaxation for the Quadratic Assignment Problem

  • Yichuan Ding
  • Henry Wolkowicz
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Semi-definite Programming Tags ,

    The quadratic assignment problem (\QAP) is arguably one of the hardest of the NP-hard discrete optimization problems. Problems of dimension greater than 20 are considered to be large scale. Current successful solution techniques depend on branch and bound methods. However, it is difficult to get \emph{strong and inexpensive} bounds. In this paper we introduce a … Read more

    Copositive and Semidefinite Relaxations of the Quadratic Assignment Problem

  • Janez Povh
  • Franz Rendl
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Semidefinite relaxations of the quadratic assignment problem (QAP) have recently turned out to provide good approximations to the optimal value of QAP. We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it … Read more

    On the Lovász theta-number of almost regular graphs with application to Erdös–Rényi graphs

  • Etienne de Klerk
  • Renata Sotirov
  • Michael W. Newman
  • Dmitrii V. Pasechnik
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , ,

    We consider k-regular graphs with loops, and study the Lovász theta-numbers and Schrijver theta’-numbers of the graphs that result when the loop edges are removed. We show that the theta-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets. … Read more

    Exploiting symmetries in SDP-relaxations for polynomial optimization

  • Lina Jansson Andrén
  • Jean-Bernard Lasserre
  • Cordian Riener
  • Thorsten Theobald
    • Categories Global Optimization Theory, Semi-definite Programming

    In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semi definite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization … Read more

    Copositivity cuts for improving SDP bounds on the clique number

  • Immanuel M. Bomze
  • Marco Locatelli
  • Florian Frommlet
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , ,

    Adding cuts based on copositive matrices, we propose to improve Lovász’ bound on the clique number and its tightening introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies rapidly increases … Read more

    Semidefinite Programming Based Algorithms for Sensor Network Localization

  • Pratik Biswas
  • Yinyu Ye
  • Tzu-Chen Liang
  • Ta-Chung Wang
    • Categories Applications - Science and Engineering, Multidisciplinary Design Optimization, Semi-definite Programming Tags

    An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite … Read more

    Theory of Semidefinite Programming for Sensor Network Localization

  • Anthony Man-Cho So
  • Yinyu Ye
    • Categories Applications - Science and Engineering, Facility Planning and Design, Semi-definite Programming Tags ,

    We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior–point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we … Read more

    Approximating the Radii of Point Sets

  • Kasturi Varadarajan
  • S Venkatesh
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Data-Mining, Semi-definite Programming Tags ,

    We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers $n, d, k$ where $k \le d$, and a set $P$ of $n$ points in $R^d$. The goal is to compute the {\em outer $k$-radius} of $P$, denoted by $\kflatr(P)$, which is the minimum, over all $(d-k)$-dimensional … Read more

    On the Convergence of the Entropy-Exponential Penalty Trajectories and Generalized Proximal Point Methods in Semidefinite Optimization

  • Orizon Pereira Ferreira
  • Paulo Roberto Oliveira
  • R. C. M. Silva
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    The convergence of primal and dual central paths associated to entropy and exponential functions, respectively, for semidefinite programming problem are studied in this paper. As an application, the proximal point method with the Kullback-Leibler distance applied to semidefinite programming problems is considered, and the convergence of primal and dual sequences is proved. Citation Journal of … Read more