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.
Citation
Unpublished. The Department of Engineering Science, The University of Auckland, 70 Symonds Street, Auckland1010, New Zealand. 31st January 2018.
Article
View A deterministic algorithm for solving stochastic minimax dynamic programmes