Optimization Online


On Safe Tractable Approximations of Chance Constrained Linear Matrix Inequalities

Aharon Ben-Tal (abental***at***ie.technion.ac.il)
Arkadi Nemirovski (nemirovs***at***isye.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/2006
Entry Accepted: 10/08/2006
Entry Last Modified: 12/02/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society