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

Sunyoung Kim (skimmath.ewha.ac.kr)
Masakazu Kojima (kojimais.titech.ac.jp)

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 objective quadratic functions and diagonal coefficient matrices of constraint quadratic 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. Some preliminary numerical results are reported.

Keywords: Nonconvex quadratic optimization problem, semidefinite programming relaxation, second order cone programming relaxation, sparsity

Category 1: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

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

Citation: Computational Optimization and Applications Vol.26 (2) 143-154 (2003).

Download:

Entry Submitted: 04/23/2002
Entry Accepted: 04/23/2002
Entry Last Modified: 04/29/2004

Modify/Update this entry