Ivo Nowak
Locally Exact Lower Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints
Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976)

MSC:

 90C20 Quadratic programming

90C30 Nonlinear programming

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.
Keywords: global optimization, nonconvex quadratic programming, Lagrangian relaxation, locally exact lower bounds, optimality cuts