Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons |
| |
Authors: | Xiaowei Bao Nikolaos V Sahinidis Mohit Tawarmalani |
| |
Institution: | 1.Department of Chemical and Biomolecular Engineering,University of Illinois at Urbana-Champaign,Urbana,USA;2.Department of Chemical Engineering,Carnegie Mellon University,Pittsburgh,USA;3.Krannert School of Management,Purdue University,West Lafayette,USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|