semidefinite relaxation

On Exact and Inexact RLT and SDP-RLT Relaxations of Quadratic Programs with Box Constraints

  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories Bound-constrained Optimization, Global Optimization, Quadratic Programming Tags , , ,

    Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the RLT (Reformulation-Linearization Technique) relaxation and the SDP-RLT relaxation obtained by adding semidefinite constraints to … Read more

    An SDP Relaxation for the Sparse Integer Least Square Problem

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , ,

    In this paper, we study the polynomial approximability or solvability of sparse integer least square problem (SILS), which is the NP-hard variant of the least square problem, where we only consider sparse {0, ±1}-vectors. We propose an l1-based SDP relaxation to SILS, and introduce a randomized algorithm for SILS based on the SDP relaxation. In … Read more

    Partial Lasserre relaxation for sparse Max-Cut

  • Juan S. Campos
  • Panos Parpas
  • Ruth Misener
    • Categories Semi-definite Programming Tags , , ,

    A common approach to solve or find bounds of polynomial optimization problems like Max-Cut is to use the first level of the Lasserre hierarchy. Higher levels of the Lasserre hierarchy provide tighter bounds, but solving these relaxations is usually computationally intractable. We propose to strengthen the first level relaxation for sparse Max-Cut problems using constraints … Read more

    A Restricted Dual Peaceman-Rachford Splitting Method for QAP

  • Naomi Graham
  • Hao Hu
  • Xinxin Li
  • Henry Wolkowicz
  • Haesol Im
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , ,

    We revisit and strengthen splitting methods for solving doubly nonnegative, DNN, relaxations of the quadratic assignment problem, QAP. We use a modified restricted contractive splitting method, rPRSM, approach. Our strengthened bounds and new dual multiplier estimates improve on the bounds and convergence results in the literature. Citation Department of Combinatorics & Optimization, University of Waterloo, … Read more

    A Strictly Contractive Peaceman-Rachford Splitting Method for the Doubly Nonnegative Relaxation of the Minimum Cut Problem

  • Xinxin Li
  • Ting Kei Pong
  • Hao Sun
  • Henry Wolkowicz
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , , , ,

    The minimum cut problem, MC, and the special case of the vertex separator problem, consists in partitioning the set of nodes of a graph G into k subsets of given sizes in order to minimize the number of edges cut after removing the k-th set. Previous work on this topic uses eigenvalue, semidefinite programming, SDP, … Read more

    Best case exponential running time of a branch-and-bound algorithm using an optimal semidefinite relaxation

  • Florian Jarre
    • Categories Branch and Cut Algorithms, Linear, Cone and Semidefinite Programming Tags , ,

    Chvatal (1980) has given a simple example of a knapsack problem for which a branch-and-bound algorithm using domination and linear relaxations to eliminate subproblems will use an exponential number of steps in the best case. In this short note it is shown that Chvatals result remains true when the LP relaxation is replaced with a … Read more

    Solving Pooling Problems by LP and SOCP Relaxations and Rescheduling Methods

  • Sunyoung Kim
  • Masaki Kimizuka
  • Makoto Yamashita
    • Categories Applications - Science and Engineering, Linear, Cone and Semidefinite Programming Tags , , , , ,

    The pooling problem is an important industrial problem in the class of network flow problems for allocating gas flow in pipeline transportation networks. For P-formulation of the pooling problem with time discretization, we propose second order cone programming (SOCP) and linear programming (LP) relaxations and prove that they obtain the same optimal value as the … Read more

    Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs

  • Samuel Burer
  • Yinyu Ye
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , ,

    We study a class of quadratically constrained quadratic programs (QCQPs), called {\em diagonal QCQPs\/}, which contain no off-diagonal terms $x_j x_k$ for $j \ne k$, and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature … Read more

    Set-Completely-Positive Representations and Cuts for the Max-Cut Polytope and the Unit Modulus Lifting

  • Florian Jarre
  • Ya-Feng Liu
  • Felix Lieder
  • Cheng Lu
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper considers a generalization of the “max-cut-polytope” $\conv\{\ xx^T\mid x\in\real^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of real symmetric $n\times n$-matrices with all-ones-diagonal to a complex “unit modulus lifting” $\conv\{xx\HH\mid x\in\complex^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of … Read more

    Tightness of a new and enhanced semidefinite relaxation for MIMO detection

  • Ya-Feng Liu
  • Cheng Lu
  • Wei-Qiang Zhang
  • Shuzhong Zhang
    • Categories Global Optimization Applications, Semi-definite Programming, Telecommunications Tags , , ,

    In this paper, we consider a fundamental problem in modern digital communications known as multi-input multi-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefinite relaxation (SDR) based algorithms have been proposed to solve the problem in the literature. In this paper, we … Read more