- On Safe Tractable Approximations of Chance Constrained Linear Matrix Inequalities Aharon Ben-Tal (abentalie.technion.ac.il) Arkadi Nemirovski (nemirovsisye.gatech.edu) Abstract: 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. Keywords: chance constraints, linear matrix inequalities, measure concentration Category 1: Robust Optimization Category 2: Stochastic Programming Category 3: Linear, Cone and Semidefinite Programming Citation: Research Report # 1/2006, October 2006, Minerva Optimization Center, Technion - Israel Institute of Technology, Technion City, Haifa 32000, Israel Download: [PDF]Entry Submitted: 10/08/2006Entry Accepted: 10/08/2006Entry Last Modified: 12/02/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.