Groupe d’études et de recherche en analyse des décisions

Convex relaxations in Branch and Bound global optimization methods: quadrilinear terms

Sonia Cafieri LIX, École Polytechnique, France

The most widely employed exact method for the global solution of mathematical programming problems involving nonlinear nonconvex terms is the spatial Branch and Bound (sBB) algorithm. Central to the sBB algorithm is the concept of convex relaxation of the original nonconvex problem, whose solution provides a bound on the optimal value of the objective function for every node in the search-space tree. In this presentation, we focus in particular on quadrilinear terms, that occur often in the mathematical programming formulation of known problems.. We present four different ways to compute a convex relaxation of a quadrilinear monomial on a box, and we computationally and mathematically analyze these relaxations in order to estabilish which is the tightest. We also show an application to some known problems, namely the Molecular Distance Geometry Problem and the Hartree-Fock Problem.