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

• 成果类型: Article
• 署名作者: Linderoth, J
• 署名单位: Lehigh University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0582-7
• 发表日期: 2005
• 页码: 251-282
• 关键词: global optimization; 2nd-order cone; relaxation

摘要

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.