| Chance constrained problems are optimization problems where one or more constraints ensure that the probability of one or more events occurring is less than a prescribed threshold. Although it is typically assumed that the distribution defining the chance constraints are known perfectly; in practice this assumption is unwarranted. We study chance constrained problems where the underlying distributions are not completely specified and are assumed to belong to an uncertainty set Q . We call such problems "ambiguous chance constrained problems." We focus primarily on the special case where the uncertainty set Q of the distributions is of the form Q=Q:rp Q,Q0 ≤b , where rhop denotes the Prohorov metric.; We study single and two stage ambiguous chance constrained programs. The single stage ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according to the central measure Q0 . We show that the robust sampled problem is a good approximation for the ambiguous chance constrained problem with a high probability. This result is established using the Strassen-Dudley Representation Theorem. We also show that the robust sampled problem can be solved efficiently both in theory and in practice.; Nemirovski and Shapiro [61] formulated two-stage convex chance constrained programs and proposed an ellipsoid-like iterative algorithm for the special case where the impact function f(x, h) is bi-affine. We show that this algorithm extends to bi-convex f(x, h ) in a fairly straightforward fashion. The complexity of the solution algorithm as well as the quality of its output are functions of the radius r of the largest Euclidean ball that can be inscribed in the polytope defined by a random set of linear inequalities generated by the algorithm [61]. In this dissertation we provide some guidance for selecting r. We develop an approximation algorithm to two-stage ambiguous chance constrained programs when the impact function f(x, h) is bi-affine and the extreme points of a certain "dual" polytope are known explicitly. |
