On the optimality of affine policies for budgeted uncertainty sets

DOI10.1287/MOOR.2020.1082MaRDI QIDQ5000650zbMATH OpenOpenAlexFDO

Authors Omar El Housni, Vineet Goyal

Publication date 15 July 2021

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.00163

zbMATH Keywords

robust optimizationaffine policiesbudget of uncertainty

Mathematics Subject Classification ID

Stochastic programming (90C15) Minimax problems in mathematical programming (90C47) Robustness in mathematical programming (90C17)

Abstract: 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 $Omegaleft(fraclognloglognight)$ 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 $Oleft(fraclognloglognight)$-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.

Recommendations

• On the performance of affine policies for two-stage adaptive optimization: a geometric perspective
• On the power and limitations of affine policies in two-stage adaptive optimization
• On the approximability of adjustable robust convex optimization under uncertainty
• A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization
• Robust combinatorial optimization with variable budgeted uncertainty

Cites work

• A Linear Decision-Based Approximation Approach to Stochastic Programming
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides
• A geometric characterization of the power of finite adaptability in multistage stochastic and adaptive optimization
• A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization
• Adjustable robust optimization via Fourier-Motzkin elimination
• Adjustable robust solutions of uncertain linear programs
• Design of near optimal decision rules in multistage adaptive mixed-integer optimization
• Duality in two-stage adaptive linear optimization: faster computation and stronger bounds
• Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set
• On the performance of affine policies for two-stage adaptive optimization: a geometric perspective
• On the power and limitations of affine policies in two-stage adaptive optimization
• Online primal-dual algorithms for covering and packing
• Optimality of affine policies in multistage robust optimization
• Robust Combinatorial Optimization with Exponential Scenarios
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• Robust optimization
• Supermodularity and affine policies in dynamic robust optimization
• The Price of Robustness
• Theory and applications of robust optimization
• Thresholded covering algorithms for robust and max-min optimization
• Tractable stochastic analysis in high dimensions via robust optimization
• \(K\)-adaptability in two-stage robust binary programming

Cited in

(12)

• On the power of static assignment policies for robust facility location problems
• Decision rule-based method in solving adjustable robust capacity expansion problem
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
• A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization
• A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides
• On the power and limitations of affine policies in two-stage adaptive optimization
• Optimality of affine policies in multistage robust optimization
• Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
• Robust convex optimization: a new perspective that unifies and extends
• Adjustability in robust linear optimization
• Designing tractable piecewise affine policies for multi-stage adjustable robust optimization

This page was built for publication: On the optimality of affine policies for budgeted uncertainty sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5000650)