nonconvex quadratic programming – Page 3

Semidefinite-Based Branch-and-Bound for Nonconvex Quadratic Programming

Published: 2005/06/27

Global Optimization, Quadratic Programming, Semi-definite Programming Branch-and-Bound, lift-and-project relaxations, nonconcave quadratic maximization, nonconvex quadratic programming, semidefinite programming

This paper presents a branch-and-bound algorithm for nonconvex quadratic programming, which is based on solving semidefinite relaxations at each node of the enumeration tree. The method is motivated by a recent branch-and-cut approach for the box-constrained case that employs linear relaxations of the first-order KKT conditions. We discuss certain limitations of linear relaxations when handling … Read more

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

Published: 2004/05/19, Updated: 2004/12/13

Jeff Linderoth

Global Optimization Theory Branch-and-Bound, convex envelope, global optimization, nonconvex quadratic programming

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 … Read more