Veranstaltungen
Veranstaltungen der Fakultät für Mathematik
Improved convex relaxations through simultaneous convexification of non-linear functions, als koloor
Termin
16.07.2012, 16:00 - 17:00
Veranstaltungsort
M/E19
Abstract
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.
Vortragende(r)
Dr. Dennis Michaels
Herkunft der/des Vortragenden
ETH Zürich