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.
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.