A Simplicial Branch-and-Bound Algorithm for Solving Quadratically Constrained Quadratic Programs

Jeff Linderoth (jtl3lehigh.edu)

Abstract: 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.

Keywords: Nonconvex Quadratic Programming, Global Optimization, Convex Envelope, Branch-and-Bound

Category 1: Global Optimization (Theory )

Citation: Technical Report, Industrial and Systems Engineering Department, Lehigh University. May, 2004

Download: [Postscript]

Entry Submitted: 05/19/2004
Entry Accepted: 05/26/2004
Entry Last Modified: 12/13/2004

Modify/Update this entry