Optimization Online


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

Jeff Linderoth (jtl3***at***lehigh.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society