Convex hull of a monomial on a two-variable conic domain

Pietro Belotti (Politecnico di Milano)

Abstract: We consider a monomial function with real exponents, which is of interest in optimization. Specifically, global optimization solvers need tight convex relaxations of sets defined by nonconvex functions to find a valid lower bound. The convex hull of the monomial in two variables on a bounding box is known for some special cases, but unknown in general. We discuss the convex hull of a generic monomial in two variables that, rather than being restricted to a bounding box, is restricted to a two-variable cone with the origin as its vertex. We then look at how to compute the volume of such convex hull, which is also of interest in global optimization: in fact branching operations of branch-and-bound solvers have a great impact in solver efficiency, in particular some branching techniques that aim at minimizing the total resulting volume of the two new subproblems.