A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs

被引：126

作者：

Linderoth, J ^{[1
]}

机构：

[1] Lehigh Univ, Dept Ind & Syst Engn, Bethlehem, PA 18015 USA

来源：

MATHEMATICAL PROGRAMMING | 2005年 / 103卷 / 02期

关键词：

nonconvex quadratic programming; global optimization; convex envelope; branch-and-bound;

D O I：

10.1007/s10107-005-0582-7

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be second-order cone representable. The usefulness of these new relaxations is demonstrated both theoretically and computationally.

引用

页码：251 / 282

页数：32