Journal
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
Volume 26, Issue 2, Pages 143-154Publisher
KLUWER ACADEMIC PUBL
DOI: 10.1023/A:1025794313696
Keywords
nonconvex quadratic optimization problem; semidefinite programming relaxation; second order cone programming relaxation; sparsity
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available