Oliver Stein
University of Karlsruhe
We present a new numerical solution method for robust optimization problems in the absence of convexity. Its main idea is to adaptively construct convex relaxations of the lower level problem, replace the relaxed lower level problems equivalently by their Karush-Kuhn-Tucker conditions, and solve the resulting mathematical programs with complementarity constraints. In contrast to the commonly used approaches, this approximation produces feasible iterates for the original robust problem.
After a survey of known methods in robust optimization, we show how convex relaxations can be constructed with ideas from the alpha-BB method of global optimization. The necessary upper bounds for functions on box domains can be determined using the techniques of interval arithmetic. We show convergence of stationary points of the approximating problems to a stationary point of the original problem.
Adaptive convexification may not only be applied to robust optimization, but also to other semi-infinite problems like Chebyshev approximation or Design Centering. Numerical examples illustrate the performance of the method.