Abstract
We propose a method to compute derivatives of multistage linear stochastic optimization problems with respect to parameters that influence the problem’s data. Our results are based on classical envelope theorems and can be used in problems directly solved via their deterministic equivalents as well as in stochastic dual dynamic programming for which the derivatives of the optimal value are sampled. We derive smoothness properties for optimal values of linear optimization problems, which we use to show that the computed derivatives are valid almost everywhere under mild assumptions. We discuss two numerical case studies, demonstrating that our approach is superior, both in terms of accuracy and computationally, to naïve methods of computing derivatives that are based on difference quotients.
Original language | English |
---|---|
Pages (from-to) | 1608-1629 |
Number of pages | 22 |
Journal | Operations Research |
Volume | 69 |
Issue number | 5 |
DOIs | |
State | Published - 1 Sep 2021 |
Keywords
- Markov decision processes
- Semi-algebraic sets
- Sensitivity analysis
- Stochastic dual dynamic programming