Optimization Online


Chance-Constrained Linear Matrix Inequalities with Dependent Perturbations: A Safe Tractable Approximation Approach

Sin-Shuen Cheung (sscheung***at***se.cuhk.edu.hk)
Anthony Man-Cho So (manchoso***at***se.cuhk.edu.hk)
Kuncheng Wang (kcwang***at***se.cuhk.edu.hk)

Abstract: The wide applicability of chance-constrained programming, together with advances in convex optimization and probability theory, has created a surge of interest in finding efficient methods for processing chance constraints in recent years. One of the successes is the development of so-called safe tractable approximations of chance-constrained programs, where a chance constraint is replaced by a deterministic and efficiently computable inner approximation. Currently, such an approach applies mainly to chance-constrained linear inequalites, in which the data perturbations are either independent or define a known covariance matrix. However, its applicability to the case of chance-constrained conic inequalities with dependent perturbations--which arises in finance, control and signal processing applications--remains largely unexplored. In this paper, we consider the problem of processing chance-constrained affinely perturbed linear matrix inequalities, in which the perturbations are not necessarily independent, and the only information available about the dependence structure is a list of independence relations. Using large deviation bounds for matrix-valued random variables, we develop safe tractable approximations of those chance constraints. A nice feature of our approximations is that they can be expressed as systems of linear matrix inequalities, thus allowing them to be solved easily and efficiently by off-the-shelf solvers. We also provide a numerical illustration of our constructions through a problem in control theory.

Keywords: Chance-Constrained Programming, Safe Tractable Approximation, Semidefinite Programming

Category 1: Robust Optimization

Citation: Working paper, Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong, January 2011.

Download: [PDF]

Entry Submitted: 01/26/2011
Entry Accepted: 01/26/2011
Entry Last Modified: 01/27/2011

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