Random Convex Programs - Part 2

In the companion paper we introduced a theory for random convex programs (RCPs), deriving tight upper bounds for the probability of optimal objective and constraint violation. In the present paper, we extend the basic setup to the case of RCPs with a-posteriori violated constraints (RCPVs): a paradigm that permits to improve the optimal objective value while maintaining the probability of objective violation under control. Explicit and non-asymptotic bounds are derived for this case, and the relation between RCPVs and chance-constrained problems is highlighted, under no feasibility assumption. In particular, the optimal objective of an RCPV with generic constraint removal rule provides, with arbitrarily high probability, an efficiently computable upper bound on the optimal objective of a corresponding chance-constrained problem. Further, the optimal objective of an RCPVs with optimal constraint removal rule can approximate to arbitrary level the optimal objective of the chance-constrained problem.