Random Convex Programs

Abstract

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.