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

Xiaojin Zheng (), Yutong Pan () and Xueting Cui ()
Additional contact information
Xiaojin Zheng: Tongji University
Yutong Pan: Tongji University
Xueting Cui: Shanghai University of Finance and Economics

Journal of Global Optimization, 2018, vol. 70, issue 4, No 2, 719-735

Abstract: Abstract 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.

Keywords: Binary QCQP; Semidefinite programming; Quadratic convex reformulation; Global optimization (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-017-0591-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:70:y:2018:i:4:d:10.1007_s10898-017-0591-0

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-017-0591-0

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().