Optimization Online


A deterministic algorithm for solving 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 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.

Download: [PDF]

Entry Submitted: 01/30/2018
Entry Accepted: 02/01/2018
Entry Last Modified: 08/06/2019

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