RANDOM CONVEX PROGRAMS

Random convex programs (RCPs) are convex optimization problems subject to a finite number N of random constraints. The optimal objective value J* of an RCP is thus a random variable. We study the probability with which J* is no longer optimal if a further random constraint is added to the problem (violation probability, V*). It turns out that this probability rapidly concentrates near zero as N increases. We first develop a theory for RCPs, leading to explicit bounds on the upper tail probability of V*. Then we extend the setup to the case of RCPs with r a posteriori violated constraints (RCPVs): a paradigm that permits us to improve the optimal objective value while maintaining the violation probability under control. Explicit and nonasymptotic bounds are derived also in this case: the upper tail probability of V* is upper bounded by a multiple of a beta distribution, irrespective of the distribution on the random constraints. All results are derived under no feasibility assumptions on the problem. Further, the relation between RCPVs and chance-constrained problems (CCP) is explored, showing that the optimal objective J* of an RCPV with the generic constraint removal rule provides, with arbitrarily high probability, an upper bound on the optimal objective of a corresponding CCP. Moreover, whenever an optimal constraint removal rule is used in the RCPVs, then appropriate choices of N and r exist such that J* approximates arbitrarily well the objective of the CCP.