BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Seminar by Prof. Vineet Goyal\, Columbia University
DTSTART:20181114T150000
DTEND:20181114T163000
DTSTAMP:20260501T085706Z
UID:42d1036f73645188f0ab092b1dfb5b923dd53c44df20eb9624cc3ca5
CATEGORIES:Conferences - Seminars
DESCRIPTION:Prof. Vineet Goyal\, Columbia University\n"On the Power of Aff
 ine Policies in Two-stage Adjustable Robust Optimization"\n \nAbstract: \
 nAffine policies are widely used as a solution approach in dynamic optimiz
 ation where computing an optimal adjustable solution is usually intractabl
 e. While the worst case performance of affine policies can be significantl
 y bad compared to the optimal adjustable solution\, the empirical performa
 nce is observed to be near-optimal for a large class of problem instances.
  For instance\, in the two-stage dynamic robust optimization problem with 
 linear covering constraints and uncertain right hand side\, the worst-case
  approximation bound for affine policies is O(√m) that is also tight (se
 e Bertsimas and Goyal [8])\, whereas observed empirical performance is nea
 r-optimal. This work aims to address this stark-contrast between the worst
 -case and the empirical performance of affine policies. We show that affin
 e policies are provably a good approximation for the two-stage adjustable 
 robust optimization problem with high probability on random instances wher
 e the constraint coefficients are generated i.i.d. from a large class of d
 istributions\; thereby\, providing a theoretical justification of the obse
 rved empirical performance. We also consider the performance of affine pol
 icies for an important class of uncertainty sets\, namely the budget of un
 certainty and intersection of budget of uncertainty sets. We show that sur
 prisingly affine policies provide nearly the best possible approximation f
 or this class of uncertainty sets that matches the hardness of approximati
 on\; thereby\, further confirming the power of affine policies. This talk 
 is based is joint work with my student Omar El Housni.\n \n 
LOCATION:ODY 4 03 https://plan.epfl.ch/?room==ODY%204%2003
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR