Optimization Online


The Exact Feasibility of Randomized Solutions of Robust Convex Programs

Marco Campi (marco.campi***at***ing.unibs.it)
Simone Garatti (simone.garatti***at***polimi.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
Entry Accepted: 07/19/2007
Entry Last Modified: 10/27/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society