  


On Safe Tractable Approximations of Chance Constrained Linear Matrix Inequalities
Aharon BenTal (abentalie.technion.ac.il) 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/2006 Modify/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  