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.
Citation
Working paper, Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong, January 2011.