Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations

Sunyoung Kim, Masakazu Kojima

Research output: Contribution to journalArticlepeer-review

97 Scopus citations

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.

Original languageEnglish
Pages (from-to)143-154
Number of pages12
JournalComputational Optimization and Applications
Volume26
Issue number2
DOIs
StatePublished - Nov 2003

Keywords

  • Nonconvex quadratic optimization problem
  • Second order cone programming relaxation
  • Semidefinite programming relaxation
  • Sparsity

Fingerprint

Dive into the research topics of 'Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations'. Together they form a unique fingerprint.

Cite this