Worst-case violation of sampled convex programs for optimization with uncertainty (Q2429409)

Consider the following robust convex program \[ \min_{x\in \chi }\,\left\langle c,x\right\rangle \;\text{s.t.\;}f\left( x,u\right) \leq 0,\;\forall u\in \mathcal{U}\subset \mathbb{R}^d, \] where \(f\left( x,u\right) \) is a convex function in \(x\in \mathbb{R}^m\), \(\;\mathcal{U}\) denotes the uncertainty set for uncertain parameters \( u\in \mathbb{R}^d\), i.e., the set of all potentially realizable values of these uncertain parameters and \(\chi \) is a convex subset in \(\mathbb{R}^m\). The basic idea of robust optimization is to seek a solution that is guaranteed to perform well in terms of feasibility and near-optimality for all possible realizations of the uncertain input data. This paper is concerned with the probability of violation of the constraints by the randomized solution and also the degree of violation, i.e. the worst-case violation. The authors derive an upper bound of the worst-case violation for the sampled convex programs and consider the relation between the probability of violation and the worst-case violation. Numerical experiments are presented.