Details

Autor(en) / Beteiligte

• Zheng, Xiaojin
• Pan, Yutong
• Cui, Xueting

Titel

Quadratic convex reformulation for nonconvex binary quadratically constrained quadratic programming via surrogate constraint

Ist Teil von

• Journal of global optimization, 2018-04, Vol.70 (4), p.719-735

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2018

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We investigate in this paper nonconvex binary quadratically constrained quadratic programming (QCQP) which arises in various real-life fields. We propose a novel approach of getting quadratic convex reformulation (QCR) for this class of optimization problem. Our approach employs quadratic surrogate functions and convexifies all the quadratic inequality constraints to construct QCR. The price of this approach is the introduction of an extra quadratic inequality. The “best” QCR among the proposed family, in terms that the bound of the corresponding continuous relaxation is best, can be found via solving a semidefinite programming problem. Furthermore, we prove that the bound obtained by continuous relaxation of our best QCR is as tight as Lagrangian bound of binary QCQP. Computational experiment is also conducted to illustrate the solution efficiency improvement of our best QCR when applied in off-the-shell software.