Envelope theorems for multistage linear stochastic optimization

Gonçalo Terça, David Wozabal

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish
Pages (from-to)1608-1629
Number of pages22
JournalOperations Research
Volume69
Issue number5
DOIs
StatePublished - 1 Sep 2021

Keywords

  • Markov decision processes
  • Semi-algebraic sets
  • Sensitivity analysis
  • Stochastic dual dynamic programming

Fingerprint

Dive into the research topics of 'Envelope theorems for multistage linear stochastic optimization'. Together they form a unique fingerprint.

Cite this