Asset Details
Do you wish to reserve the book?
On the power and limitations of affine policies in two-stage adaptive optimization
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
On the power and limitations of affine policies in two-stage adaptive optimization
Do you wish to request the book?
On the power and limitations of affine policies in two-stage adaptive optimization
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Journal Article
On the power and limitations of affine policies in two-stage adaptive optimization
2012
Overview
We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be
times the worst-case cost of an optimal fully-adaptable solution for any
δ
> 0, where
m
is the number of linear constraints. We also show that the worst-case cost of the best affine policy is
times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only
k
≤
m
uncertain parameters, we generalize the performance bound for affine policies to
, which is particularly useful if only a few parameters are uncertain. We also provide an
-approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set,
is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if
is a convex combination of only (
m
+ 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 −
δ
) worse than the worst-case cost of an optimal fully-adaptable solution for any
δ
> 0.
Publisher
Springer-Verlag,Springer,Springer Nature B.V
Subject
/ Analysis
/ Calculus of variations and optimal control
/ Calculus of Variations and Optimal Control; Optimization
/ Exact sciences and technology
/ Mathematical and Computational Physics
/ Mathematical Methods in Physics
/ Operational research and scientific management
/ Operational research. Management science
/ Policies
/ Reliability theory. Replacement problems
/ Sciences and techniques of general use
/ Studies
