A deterministic algorithm for solving stochastic minimax dynamic programmes
Regan Baucke (r.bauckeauckland.ac.nz)
Abstract: In this paper, we present an algorithm for solving stochastic minimax dynamic programmes where state and action sets are convex and compact. A feature of the formulations studied is the simultaneous non-rectangularity of both `min' and `max' feasibility sets. We begin by presenting convex programming upper and lower bound representations of saddle functions -- extending outer representations from traditional convex cutting plane algorithms. Our algorithm is similar in spirit to existing 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 (now saddle functions) over the domain. We apply the theory developed in this paper to multistage risk-averse optimization. Through the dual representation of coherent risk measures, we represent risk-averse stochastic optimization 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 optimization problem; providing numerical validation 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|