On two-stage convex chance constrained problems

Abstract

In this paper we develop approximation algorithms for two-stage convex chance constrainedproblems. Nemirovski and Shapiro [16] formulated this class of problems and proposed anellipsoid-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 theradius r of the largest Euclidean ball that can be inscribed in the polytope defined by a randomset of linear inequalities generated by the algorithm [16]. Since the polytope determining ris random, computing r is diffiult. Yet, the solution algorithm requires r as an input. Inthis paper we provide some guidance for selecting r. We show that the largest value of r isdetermined by the degree of robust feasibility of the two-stage chance constrained problem –the more robust the problem, the higher one can set the parameter r. Next, we formulate ambiguous two-stage chance constrained problems. In this formulation,the random variables defining the chance constraint are known to have a fixed distribution;however, the decision maker is only able to estimate this distribution to within some error. Weconstruct an algorithm that solves the ambiguous two-stage chance constrained problem whenthe impact function f (x, h) is bi-affine and the extreme points of a certain “dual” polytope areknown explicitly.