In the paper, we consider the chance constrained version $$ \Prob\{A_0[x]+\sum_{i=1}^d\zeta_i A_i[x]\succeq0\}\geq1-\epsilon, $$ of an affinely perturbed Linear Matrix Inequality constraint; here $A_i[x]$ are symmetric matrices affinely depending on the decision vector $x$, and $\zeta_1,…,\zeta_d$ are independent of each other random perturbations with light tail distributions (e.g., bounded or Gaussian). Constraints of this type, playing the central role in Chance Constrained Linear/Conic Quadratic/Semidefinite Programming, typically are computationally intractable, which makes natural to look for their tractable approximations. The goal of this paper is to develop such an approximation. Our approximation is based on measure concentration results and is given by an explicit system of LMIs and thus is computationally tractable; it is also safe, meaning that a feasible solution of the approximation is feasible for the chance constraint as well.
Citation
Research Report # 1/2006, October 2006, Minerva Optimization Center, Technion - Israel Institute of Technology, Technion City, Haifa 32000, Israel