The Exact Feasibility of Randomized Solutions of Robust Convex Programs

Marco Campi(marco.campiing.unibs.it)
Simone Garatti(simone.garattipolimi.it)

Abstract: Robust optimization programs are hard to solve even when the constraints are convex. In previous contributions, it has been shown that approximately robust solutions (i.e. solutions feasible for all constraints but a small fraction of them) to convex programs can be obtained at low computational cost through constraints randomization. In this paper, we establish new feasibility results for randomized algorithms. Specifically, the exact feasibility for the class of the so-called fully-supported problems is obtained. It turns out that all fully-supported problems shares the same feasibility properties, revealing a deep kinship among problems of this class. It is further proven that the feasibility of the randomized solutions for all other convex programs can be bounded based on the feasibility for the prototype class of fully-supported problems. The feasibility result of this paper outperforms previous bounds, and is not improvable because it is exact for fully-supported problems.

Keywords: robust optimization, randomized methods, convex optimization, semi-infinite programming

Category 1: Robust Optimization

Category 2: Infinite Dimensional Optimization (Semi-infinite Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: preprint July 19, 2007 Dept. of Electrical Engineering University of Brescia via Branze 38 25123 Brescia Italy

Download: [PDF]

Entry Submitted: 07/19/2007
Entry Accepted: 07/19/2007
Entry Last Modified: 07/19/2007

Modify/Update this entry