  


On the Optimality of Affine Policies for Budgeted Uncertainty Sets
Omar El Housni(oe2148columbia.edu) Abstract: In this paper, we study the performance of affine policies for twostage adjustable robust optimization problem with uncertain right hand side belonging to a budgeted uncertainty set. This is an important class of uncertainty sets widely used in practice where we can specify a budget on the adversarial deviations of the uncertain parameters from the nominal values to adjust the level of conservatism. The twostage adjustable robust optimization problem is hard to approximate within a factor better than $\Omega( \frac{\log n}{\log \log n})$ even for budget of uncertainty sets where $n$ is the number of decision variables. Affine policies, where the secondstage decisions are constrained to be an affine function of the uncertain parameters, provide a tractable approximation for the problem and exhibit good empirical performance. We show that affine policies give an $O( \frac{\log n}{\log \log n})$approximation for the twostage adjustable robust problem for this class of uncertainty sets. This matches the hardness of approximation and therefore, surprisingly affine policies provide an optimal approximation for the problem (up to some constant factor). We also show strong theoretical performance bounds for affine policy for significantly more general class of intersection of budgeted sets including disjoint constrained budgeted sets, permutation invariant sets and general intersection of budgeted sets. Our analysis relies on showing the existence of a nearoptimal feasible affine policy that satisfies certain nice structural properties. Based on these structural properties, we also present an alternate algorithm to compute nearoptimal affine solution that is significantly faster than computing the optimal affine policy by solving a large linear program. Keywords: Robust Optimization, Affine Policies, Approximation Algorithms Category 1: Robust Optimization Citation: Download: [PDF] Entry Submitted: 06/30/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  