Random Convex Programs - Part 1

Random convex programs (RCPs) are convex optimization problems subject to a finite number of constraints (scenarios) that are extracted according to some probability distribution. The optimal objective value of an RCP and its associated optimal solution (when it exists), are random variables: RCP theory is mainly concerned with providing probabilistic assessments on the objective and on the probability of constraint violation for the RCP solution. In a two-parts contribution, we give a self-contained overview of RCP theory by both re-deriving and extending known results via new proofs, and by providing novel advancements. In this first-part paper we introduce the basic concepts and derive an explicit and tight upper bound on the objective and constraint violation probability of RCPs. This novel derivation allows for a much wider applicability with respect to existing results, since it requires no hypothesis of existence of the solution. The companion paper is then concerned with RCPs with a-posteriori violated constraints (RCPVs), exploring in particular their connections with chance constrained problems.