M/E19

A challenging task in global optimization is to construct tight convex relaxations that provide reasonably globally valid bounds on a mixed-integer nonlinear program (MINLP). For a general MINLP, convex relaxations are usually obtained by replacing each non-linearity by convex under- and concave overestimators. The mathematical object studied to derive such estimators is given by the convex hull of the graph of the function over the relevant domain. To derive improved relaxations, we consider a finite set of given functions as a vector-valued function and study the convex hull of its graph. We establish a link between such a convex hull object and the convex hulls of the graphs of a certain family of real-valued functions. This link can be used to define improved relaxations. We especially focus on small sets of well-structured univariate functions. Moreover, we consider some classes of (real-valued) functions for which a simultaneous convexification with the set of multi-linear monomials leads to an explicit description for the tightest convex underestimating function. The extended formulation is based on the idea of the RLT-appraoch introduced by Sherali and Adams. Numerical examples are presented demonstrating the impact of the concepts.

Dr. Dennis Michaels

ETH Zürich