A Guided Tour of Robust Optimization

Laurent El Ghaoui
Department of Electrical Engineering & Computer Science
University of California at Berkeley

Robust optimization deals with optimization problems in which the data (say, the coefficients in a linear program) are only known within a set, and a decision variable guaranteed to satisfy all the constraints despite data uncertainty is sought. We describe the main results in robust optimization, in particular how second-order cone or semidefinite programming relaxations can be used to obtain robust solutions to uncertain programs. We explore connections between the robust (or worst-case) approach and stochastic descriptions of uncertainty, in which the distribution of the uncertainty is partially known. We then give an overview of applications, ranging from control systems (robust control of uncertain dynamical systems) to machine learning (robust classification, support vector machines, and kernel optimization).