Locally Exact Lower Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints

Abstract

A central problem of branch-and-bound methods for global optimization is that lower bounds are often not exact even if the diameter of the subdivided regions shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present locally exact lower bounds and optimality cuts based on Lagrangian relaxation. If all global minimizers fulfill a certain second order optimality condition it can be shown that locally exact lower bounds or optimality cuts lead to finite termination of a branch-and-bound algorithm. Since there exist efficient methods for computing Lagrangian relaxation bounds of all-quadratic optimization problems exploiting problem structure our approach should be applicable to large scale structured optimization problems.