  In this paper, we study the performance of affine policies for two-stage
adjustable robust optimization problem with fixed recourse and 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 two-stage adjustable robust
optimization problem is hard to approximate within a factor better than $\Omega
\left( \frac{\log n}{\log \log n} \right)$ even for budget of uncertainty sets
and fixed non-negative recourse where $n$ is the number of decision variables.
Affine policies, where the second-stage decisions are constrained to be an
affine function of the uncertain parameters, provide a tractable approximation
for the problem and have been observed to exhibit good empirical performance.
We show that affine policies give an $O\left( \frac{\log n}{\log \log n}
\right)$-approximation for the two-stage adjustable robust problem with fixed
non-negative recourse for budgeted uncertainty sets. This matches the hardness
of approximation and therefore, surprisingly affine policies provide an optimal
approximation for the problem (up to a 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 near-optimal feasible affine
policy that satisfies certain nice structural properties. Based on these
structural properties, we also present an alternate algorithm to compute
near-optimal affine solution that is significantly faster than computing the
optimal affine policy by solving a large linear program.
