Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons

• 成果类型: Article; Proceedings Paper
• 署名作者: Bao, Xiaowei; Sahinidis, Nikolaos V.; Tawarmalani, Mohit
• 署名单位: Carnegie Mellon University; University of Illinois System; University of Illinois Urbana-Champaign; Purdue University System; Purdue University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0462-2
• 发表日期: 2011
• 页码: 129-157
• 关键词: global optimization approach; bound algorithm; nonconvex; discrete; layout; sdp; cut

摘要

At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be formulated as semidefinite programs (SDPs). The primary purpose of this paper is to present a systematic comparison of SDP relaxations for QCQP. Using theoretical analysis, it is shown that the recently developed doubly nonnegative relaxation is equivalent to the Shor relaxation, when the latter is enhanced with a partial first-order relaxation-linearization technique. These two relaxations are shown to theoretically dominate six other SDP relaxations. A computational comparison reveals that the two dominant relaxations require three orders of magnitude more computational time than the weaker relaxations, while providing relaxation gaps averaging 3% as opposed to gaps of up to 19% for weaker relaxations, on 700 randomly generated problems with up to 60 variables. An SDP relaxation derived from Lagrangian relaxation, after the addition of redundant nonlinear constraints to the primal, achieves gaps averaging 13% in a few CPU seconds.