A deterministic algorithm for solving multistage stochastic minimax dynamic programmes
Regan Baucke (r.bauckeauckland.ac.nz)
Abstract: In this paper, we present an algorithm for solving multistage stochastic minimax dynamic programmes. We begin by presenting linear-programming upper and lower bound representations of saddle functions -- extending outer representations from traditional convex cutting plane algorithms. Our algorithm is similar to many stochastic dual dynamic programming (SDDP) type algorithms. Bounding functions are iteratively updated in order to compute cost-to-go functions; however special consideration must be taken in ensuring the validity of the cost-to-go bounding functions (which are now saddle functions) over the domain. We apply the theory developed in this paper to multistage risk-averse optimisation. Through the dual representation of coherent risk measures, we represent risk-averse stochastic optimisation problems as minimax stochastic dynamic programmes, and provide two formulations for these problems: the nested risk formulation, and the end-of-horizon formulation. Finally, we demonstrate our algorithm on a risk-averse portfolio optimisation problem; providing numerical results and a discussion.
Keywords: dynamic programming,decomposition, multistage, SDDP, stochastic programming,minimax, game theory, sub-game perfect equilibria, risk, robust optimisation
Category 1: Stochastic Programming
Category 2: Robust Optimization
Category 3: Other Topics (Dynamic Programming )
Citation: Unpublished. The Department of Engineering Science, The University of Auckland, 70 Symonds Street, Auckland1010, New Zealand. 31st January 2018.
Entry Submitted: 01/30/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|