The Exact Feasibility of Randomized Solutions of Robust Convex Programs
Marco Campi (marco.campiing.unibs.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: M.C. Campi, S. Garatti. "The exact feasibility of randomized solutions of uncertain convex programs". SIAM Journal on Optimization 19(3):1211-1230, 2008.
Entry Submitted: 07/19/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|