Accession Number:

ADA478336

Title:

On Two-Stage Convex Chance Constrained Problems

Descriptive Note:

Technical rept.

Corporate Author:

COLUMBIA UNIV NEW YORK DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2005-11-03

Pagination or Media Count:

26.0

Abstract:

In this paper we develop approximation algorithms for two-stage convex chance constrained problems. Nemirovski and Shapiro 18 formulated this class of problems 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 18. Since the polytope determining r is random, computing r is difficult. Yet, the solution algorithm requires r as an input. In this paper we provide some guidance for selecting r. We show that the largest value of r is determined 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. We construct an algorithm that solves the ambiguous two-stage chance constrained problem when the impact function f x, h is bi-affine and the extreme points of a certain dual polytope are known explicitly.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE