Optimization Online


Envelope Theorems for Multi-Stage Linear Stochastic Optimization

David Wozabal(david.wozabal***at***tum.de)
Goncalo Terca(g.terca***at***tum.de)

Abstract: We propose a method to compute derivatives of multi-stage 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 as well as computationally, to naive methods of computing derivatives that are based on difference quotients.

Keywords: Markov decision processes, sensitivity analysis, stochastic dual dynamic programming, semi-algebraic sets

Category 1: Stochastic Programming

Citation: TUM School of Management

Download: [PDF]

Entry Submitted: 06/18/2018
Entry Accepted: 06/19/2018
Entry Last Modified: 06/18/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society