Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S.~Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of objective quadratic functions and diagonal coefficient matrices … Read more

Semidefinite relaxations for Max-Cut

We compare several semidefinite relaxations for the cut polytope obtained by applying the lift and project methods of Lov\’asz and Schrijver and of Lasserre. We show that the tightest relaxation is obtained when aplying the Lasserre construction to the node formulation of the max-cut problem. This relaxation $Q_t(G)$ can be defined as the projection on … Read more

A comparison of the Sherali-Adams, Lov\’asz-Schrijver and Lasserre relaxations for sh-1$ programming

Sherali and Adams \cite{SA90}, Lov\’asz and Schrijver \cite{LS91} and, recently, Lasserre \cite{Las01b} have proposed lift and project methods for constructing hierarchies of successive linear or semidefinite relaxations of a $0-1$ polytope $P\subseteq \oR^n$ converging to $P$ in $n$ steps. Lasserre’s approach uses results about representations of positive polynomials as sums of squares and the dual … Read more

A Computational Study of a Gradient-Based Log-Barrier Algorithm for a Class of Large-Scale SDPs

The authors of this paper recently introduced a transformation \cite{BuMoZh99-1} that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based … Read more

Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lov\’asz-Schrijver Lift-and-Project Procedure

We study how the lift-and-project method introduced by Lov\’az and Schrijver \cite{LS91} applies to the cut polytope. We show that the cut polytope of a graph can be found in $k$ iterations if there exist $k$ edges whose contraction produces a graph with no $K_5$-minor. Therefore, for a graph with $n\ge 4$ nodes, $n-4$ iterations … Read more