Perturbation ananlysis of chance-constrained programs under variation of all constraint data

Abstract

A fairly general shape of chance constraint programs is\[(P) min \{ g(x) | x \in X, \mu (H(x)) \le p \} ,\]where $g : \R^m \to \R$ is a continuous objective function, $X \subseteq \R^m$ is a closed subset of deterministic constraints, and the inequality defines a probabilistic constraint with $H : \R^m \to \atop \to \R^s$ being a multifunction with closed graph, $\mu$ is a probability measure on $\rR^s$ and $p \in (0,1)$ is some probability level. In the simplest case of linear chance constraints, $g$ is linear, $X$ is a polyhedron and $H(x) = \{ z \in \R^s | Ax \ge z\} $, where $A$ is a matrix of order $(s,m)$ and the inequality sign has to be understood component-wise.\\Since the data of optimization problems are typically uncertain or approximated by other data which are easier to handle, the question of stability of solutions arises naturally. Concerning $(P)$, the first idea is to investigate solutions under perturbations of the right hand side $p$ of the inequality. This reflects the modeling degree of freedom when choosing a probability at which the constraint system is supposed to be valid. Furthermore, the probability measure $\mu$ is unknown in general and has to be approximated, for instance, by empirical measures. This motivates to extend the perturbation analysis to $\mu$. Stability of solutions of $(P)$ with respect to $p$ and $\mu$ is well understood now but shall be briefly reviewed in this paper for the sake of being selfcontained. Apart from these two constraint parameters, also approximations of the deterministic constraint $X$ and of the random set mapping $H$ in $(P)$ may be of interest. The aim of this paper is to identify constraint qualifications for stability under partial p erturbations of the single constraint parameters in $(P)$. Due to the increasing complexity of how these parameters influence each other, the resulting constraint qualifications become more and more restrictive when passing from $p$ over $\mu$ to $X$ and $H$. Part of the result relate to convex data in $(P)$ or even in the perturbations of $(P)$. Special emphasis is put on a series of counter-examples highlighting the necessity and limitations of the obtained conditions.