Explicit reformulations of robust optimization problens with general uncertainty sets

Abstract. We consider a rather general class of mathematical programming problems with data uncertainty, where the uncertainty set is represented by a system of convex inequalities. We prove that the robust counterparts of this class of problems can be equivalently reformulated as finite and explicit optimization problems. Moreover, we develop simplified reformulations for problems with uncertainty sets defined by convex homogeneous functions. Our results provide a unified treatment of many situations that have been investigated in the literature, and are applicable to a wider range of problems and more complicated uncertainty sets than those considered before. The analysis in this paper makes it possible to use existing continuous optimization algorithms to solve more complicated robust optimization problems. The analysis also shows how the structure of the resulting reformu-lation of the robust counterpart depends both on the structure of the original nominal optimization problem and on the structure of the uncertainty set. Key words. Robust optimization, data uncertainty, mathematical programming, homogeneous functions, convex analysis AMS subject classifications. 90C30, 90C15, 90C34, 90C25, 90C05