Loading...
Please wait, while we are loading the content...
Similar Documents
Ambiguous chance constrained programs: algorithms and applications
| Content Provider | Semantic Scholar |
|---|---|
| Author | Iyengar, Garud Erdogan, Emre |
| Copyright Year | 2007 |
| Abstract | 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 ρp 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. |
| Starting Page | 113 |
| Ending Page | 113 |
| Page Count | 1 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.corc.ieor.columbia.edu/theses/emre.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
