Dick den Hertog

Professor
Tilburg University

Abstract:

Robust Optimization is a popular approach to treat uncertain parameters in optimization problems. Finding a computationally tractable formulation for the robust counterpart of an optimization problem is key in this approach. Such tractable formulations have been found for problems in which the uncertain parameters appear in a concave way. However, in practice the uncertain parameters often appear in a convex way. We describe three safe approximations of such hard problems in which perspective functions play a crucial rule.

The first approximation is an extension of the method by Bertsimas and Sim (2006). The core idea is to develop a perspective approximation of each of the constraint functions. Since the approximation is linear in the uncertain parameter, the corresponding robust counterpart can be easily computed.

The second approximation is only for polyhedral uncertainty sets. We reformulate the original convex inequality as a set of linear adaptive robust optimization inequalities, in which the nonlinear constraint function appears in the uncertainty set. Perspective functions again appear if we use linear decision rules. We show that using static decision rules is equivalent with the first approximation. We show the quality of the approximations by several numerical experiments.

The third approximation is for all convex uncertainty sets. We reformulate the original convex inequality as an inequality with bilinear uncertainty. We use a recently developed perspective extension of the well-known Reformulation-Linearization-Technique, and apply this to the inequality with bilinear uncertainty. We show that when applied to polyhedral uncertainty sets, this approach is equivalent to the second approximation. Moreover, we show that if we apply the Reformulation-Perspectification-Technique partially, the third approximation coincides with the first approximation.

Joint work with:

1st and 3rd approximation: Dimitris Bertsimas, Jean Pauphilet, Trevor Zhen

2nd approximation: Aharon Ben-Tal, Ernst Roos, Frans de Ruiter, Trevor Zhen

Bio: Dick den Hertog is professor of Operations Research at Tilburg University and scientific director of the Data Science Center Tilburg. His research interests cover various fields in prescriptive analytics, in particular linear and nonlinear optimization. In recent years his main focus has been on robust optimization. He is also active in applying the theory in real-life applications. In particular, he is interested in applications that contribute to a better society. For many years he has been involved in research for optimal flood protection, which was awarded by the INFORMS Franz Edelman Award in 2013. Currently, he is doing research to develop better optimization models and techniques for cancer treatment, and he is involved in research to optimize the food supply chain for the World Food Programme.  He is chairman of the Dutch Network on the Mathematics of Operations Research, and associate editor of three journals (Management Science, Operations Research, and INFORMS Journal on Optimization).