Optimization Online


On Doubly Positive Semidefinite Programming Relaxations

Dongdong Ge (dongdong***at***gmail.com)
Yinyu Ye (yyye***at***stanford.edu)

Abstract: Recently, researchers have been interested in studying the semidefinite programming (SDP) relaxation model, where the matrix is both positive semidefinite and entry-wise nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing to the basic SDP relaxation, this doubly-positive SDP model possesses additional O(n2) constraints, which makes the SDP solution complexity substantially higher than that for the basic model with O(n) constraints. In this paper, we prove that the doubly-positive SDP model is equivalent to the basic one with a set of valid quadratic cuts. When QCQP is symmetric and homogeneous (which represents many classical combinatorial and nonconvex optimization problems), the doubly-positive SDP model is equivalent to the basic SDP even without any valid cut. On the other hand, the doubly-positive SDP model could help to tighten the bound up to 36%, but no more.

Keywords: semidefinite programming, Quadratic Programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: Working Paper, August 2010

Download: [PDF]

Entry Submitted: 08/17/2010
Entry Accepted: 08/17/2010
Entry Last Modified: 08/25/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society