Optimization Online


A deterministic algorithm for solving multistage stochastic minimax dynamic programmes

Regan Baucke (r.baucke***at***auckland.ac.nz)
Anthony Downward (a.downward***at***auckland.ac.nz)
Golbon Zakeri (g.zakeri***at***auckland.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.

Download: [PDF]

Entry Submitted: 01/30/2018
Entry Accepted: 02/01/2018
Entry Last Modified: 02/11/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