Second order cone programming relaxation of nonconvex quadratic optimization problems

Sunyoung Kim, Masakazu Kojima

Research output: Contribution to journalArticlepeer-review

87 Scopus citations

Abstract

A disadvantage of the SDP (semidefinite programming) relaxation method for quadratic and/or combinatorial optimization problems lies in its expensive computational cost. This paper proposes a SOCP (second-order-cone programming) relaxation method, which strengthens the lift-and-project LP (linear programming) relaxation method by adding convex quadratic valid inequalities for the positive semidefinite cone involved in the SDP relaxation. Numerical experiments show that our SOCP relaxation is a reasonable compromise between the effectiveness of the SDP relaxation and the low computational cost of the lift-and-project LP relaxation.

Original languageEnglish
Pages (from-to)201-224
Number of pages24
JournalOptimization Methods and Software
Volume15
Issue number3-4
StatePublished - 2001

Keywords

  • Global optimization
  • Lift-and-project convex relaxation method
  • Nonconvex quadratic program
  • Primal-dual interior-point method
  • Second-order-cone program

Fingerprint

Dive into the research topics of 'Second order cone programming relaxation of nonconvex quadratic optimization problems'. Together they form a unique fingerprint.

Cite this