Dual bounds and optimality cuts for all-quadratic programs with convex constraints

A central problem of branch-and-bound methods for global optimization is th at often a lower bound do not match with the optimal value of the correspon ding subproblem even if the diameter of the partition set 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 optimality cuts which cut off a given lo cal minimizer from the feasible set. We propose a branch-and-bound algorith m using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints a re added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic prog ramming problem dual bounds which have under certain conditions a zero dual ity gap.