Paper Info
Title
Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations
Abstract
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 quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation.
Year
DOI
Venue
2003
10.1023/A:1025794313696
Mathematics in Computer Science
Keywords
Field
DocType
nonconvex quadratic optimization problem,semidefinite programming relaxation,second order cone programming relaxation,sparsity
Diagonal,Second-order cone programming,Mathematical optimization,Quadratically constrained quadratic program,Mathematical analysis,Matrix (mathematics),Positive-definite matrix,Quadratic equation,Quadratic programming,Semidefinite programming,Mathematics
Journal
Volume
Issue
ISSN
26
2
1573-2894
Citations 
PageRank 
References 
24
2.17
2
Authors
2
Name
Order
Citations
PageRank
Sunyoung Kim146138.82
Masakazu Kojima21603222.51