  


On Doubly Positive Semidefinite Programming Relaxations
Dongdong Ge (dongdonggmail.com) Abstract: Recently, researchers have been interested in studying the semidefinite programming (SDP) relaxation model, where the matrix is both positive semidefinite and entrywise nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing to the basic SDP relaxation, this doublypositive 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 doublypositive 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 doublypositive SDP model is equivalent to the basic SDP even without any valid cut. On the other hand, the doublypositive 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 (Semidefinite Programming ) Category 2: Nonlinear Optimization (Quadratic Programming ) Citation: Working Paper, August 2010 Download: [PDF] Entry Submitted: 08/17/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  