On convex relaxations for quadratically constrained quadratic programming

• 成果类型: Article
• 署名作者: Anstreicher, Kurt M.
• 署名单位: University of Iowa
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0602-3
• 发表日期: 2012
• 页码: 233-251
• 关键词: box constraints; bound algorithm; optimization

摘要

We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on is dominated by an alternative methodology based on convexifying the range of the quadratic form for . We next show that the use of BB underestimators as computable estimates of convex lower envelopes is dominated by a relaxation of the convex hull of the quadratic form that imposes semidefiniteness and linear constraints on diagonal terms. Finally, we show that the use of a large class of D.C. (difference of convex) underestimators is dominated by a relaxation that combines semidefiniteness with RLT constraints.