semidefinite relaxation

Approximation algorithms for trilinear optimization with nonconvex constraints and its extensions

  • Yuning Yang
  • Qingzhi Yang
    • Categories Semi-definite Programming Tags , , , ,

    In this paper, we study trilinear optimization problems with nonconvex constraints under some assumptions. We first consider the semidefinite relaxation (SDR) of the original problem. Then motivated by So \cite{So2010}, we reduce the problem to that of determining the $L_2$-diameters of certain convex bodies, which can be approximately solved in deterministic polynomial-time. After the relaxed … Read more

    Comparing SOS and SDP relaxations of sensor network localization

  • João Gouveia
  • Ting Kei Pong
    • Categories Semi-definite Programming Tags , , ,

    We investigate the relationships between various sum of squares (SOS) and semidefinite programming (SDP) relaxations for the sensor network localization problem. In particular, we show that Biswas and Ye’s SDP relaxation is equivalent to the degree one SOS relaxation of Kim et al. We also show that Nie’s sparse-SOS relaxation is stronger than the edge-based … Read more

    Building a completely positive factorization

  • Immanuel M. Bomze
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    Using a bordering approach, and building upon an already known factorization of a principal block, we establish sufficient conditions under which we can extend this factorization to the full matrix. Simulations show that the approach is promising also in higher dimensions. Citation Preprint, Univ.of Vienna (2017), submitted Article Download View Building a completely positive factorization

    SFSDP: a Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems

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

    SFSDP is a Matlab package for solving a sensor network localization problem. These types of problems arise in monitoring and controlling applications using wireless sensor networks. SFSDP implements the semidefinite programming (SDP) relaxation proposed in Kim et al. [2009] for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) … Read more

    Relating max-cut problems and binary linear feasibility problems

  • Florian Jarre
    • Categories Approximation Algorithms, Semi-definite Programming Tags , ,

    This paper explores generalizations of the Goemans-Williamson randomization technique. It establishes a simple equivalence of binary linear feasibility problems and max-cut problems and presents an analysis of the semidefinite max-cut relaxation for the case of a single linear equation. Numerical examples for feasible random binary problems indicate that the randomization technique is efficient when the … 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

    Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints

  • Anthony Man-Cho So
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    In this paper we consider approximation algorithms for a class of quadratic optimization problems that contain orthogonality constraints, i.e. constraints of the form $X^TX=I$, where $X \in {\mathbb R}^{m \times n}$ is the optimization variable. Such class of problems, which we denote by (QP-OC), is quite general and captures several well–studied problems in the literature … Read more

    Relaxing the Optimality Conditions of Box QP

  • Samuel Burer
  • Jieqiu Chen
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , ,

    We present semidefinite relaxations of nonconvex, box-constrained quadratic programming, which incorporate the first- and second-order necessary optimality conditions. We compare these relaxations with a basic semidefinite relaxation due to Shor, particularly in the context of branch-and-bound to determine a global optimal solution, where it is shown empirically that the new relaxations are significantly stronger. We … Read more

    Iterative Minimization Schemes for Solving the Single Source Localization Problem

  • Amir Beck
  • Zahar Chikishev
  • Marc Teboulle
    • Categories Applications - Science and Engineering, Global Optimization Theory, Unconstrained Optimization Tags , , , , , ,

    We consider the problem of locating a single radiating source from several noisy measurements using a maximum likelihood (ML) criteria. The resulting optimization problem is nonconvex and nonsmooth and thus finding its global solution is in principal a hard task. Exploiting the special structure of the objective function, we introduce and analyze two iterative schemes … 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