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

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

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

Equivalences and Differences in Conic Relaxations of Combinatorial Quadratic Optimization Problems

Various conic relaxations of quadratic optimization problems in nonnega- tive variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combi- natorial optimization problems can be expressed in several ways, each … Read more

ADMM for the SDP relaxation of the QAP

The semidefinite programming (SDP) relaxation has proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem (QAP), arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the … Read more

Simplified semidefinite and completely positive relaxations

This paper is concerned with completely positive and semidefinite relaxations of quadratic programs with linear constraints and binary variables as presented by Burer. It observes that all constraints of the relaxation associated with linear constraints of the original problem can be accumulated in a single linear constraint without changing the feasible set of either the … Read more

A Penalized Quadratic Convex Reformulation Method for Random Quadratic Unconstrained Binary Optimization

The Quadratic Convex Reformulation (QCR) method is used to solve quadratic unconstrained binary optimization problems. In this method, the semidefinite relaxation is used to reformulate it to a convex binary quadratic program which is solved using mixed integer quadratic programming solvers. We extend this method to random quadratic unconstrained binary optimization problems. We develop a … Read more

Hybrid LP/SDP Bounding Procedure

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

An extension of the elimination method for a sparse SOS polynomial

We propose a method to reduce the sizes of SDP relaxation problems for a given polynomial optimization problem (POP). This method is an extension of the elimination method for a sparse SOS polynomial in [Kojima et al., Mathematical Programming] and exploits sparsity of polynomials involved in a given POP. In addition, we show that this … Read more

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

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

Approximation algorithms for trilinear optimization with nonconvex constraints and its extensions

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