TY - ELEC
AU - El Housni, Omar
PY - 2019
TI - On the Optimality of Affine Policies for Budgeted Uncertainty Sets
LA - eng
M3 - Moving Image
AB - We study the performance of affine policies for two-stage adjustable robust optimization problem under a budget of uncertainty set. This important class of uncertainty sets provides the flexibility to adjust the level of conservatism in terms of probabilistic bounds on constraint violations. The two-stage adjustable robust optimization problem is hard to approximate within a factor better than $\Omega( \frac{\log n}{\log \log n})$ for budget of uncertainty sets where $n$ is the number of decision variables. We show that surprisingly affine policies provide the optimal approximation for this class of uncertainty sets that matches the hardness of approximation; thereby, further confirming the power of affine policies. We also present strong theoretical guarantees for affine policies when the uncertainty set is given by intersection of budget constraints. Furthermore, our analysis gives a significantly faster algorithm to compute near-optimal affine policies. This is joint work with Vineet Goyal.
N2 - We study the performance of affine policies for two-stage adjustable robust optimization problem under a budget of uncertainty set. This important class of uncertainty sets provides the flexibility to adjust the level of conservatism in terms of probabilistic bounds on constraint violations. The two-stage adjustable robust optimization problem is hard to approximate within a factor better than $\Omega( \frac{\log n}{\log \log n})$ for budget of uncertainty sets where $n$ is the number of decision variables. We show that surprisingly affine policies provide the optimal approximation for this class of uncertainty sets that matches the hardness of approximation; thereby, further confirming the power of affine policies. We also present strong theoretical guarantees for affine policies when the uncertainty set is given by intersection of budget constraints. Furthermore, our analysis gives a significantly faster algorithm to compute near-optimal affine policies. This is joint work with Vineet Goyal.
UR - https://open.library.ubc.ca/collections/48630/items/1.0379833
ER - End of Reference