StochDynamicProgramming.jl

A package for discrete-time optimal stochastic control
Popularity
62 Stars
Updated Last
4 Months Ago
Started In
November 2015

StochDynamicProgramming

Documentation Build Status Social
Build Status Gitter
Codecov branch

This is a Julia package for optimizing controlled stochastic dynamic system, in discrete time. It offers three methods of resolution :

  • Stochastic Dual Dynamic Programming (SDDP) algorithm.
  • Extensive formulation.
  • Stochastic Dynamic Programming.

It is built on top of JuMP.

StochDynamicProgramming asks the user to provide explicit the cost c(t, x, u, w) and dynamics f(t, x, u, w) functions. Also, the package was developed back in 2016, and some parts of its API are not idiomatic, in a Julia sense. For other implementations of the SDDP algorithm in Julia, we advise to have a look at these two packages:

What problems solves this package ?

StochDynamicProgramming targets problems with

  • Stage-wise independent discrete noise
  • Linear dynamics
  • Linear or convex piecewise linear costs

Extension to non-linear formulation are under development.

Why SDDP?

SDDP is a dynamic programming algorithm relying on cutting planes. The algorithm requires convexity of the value function but does not discretize the state space. The complexity is linear in the number of stage, and can accomodate higher dimension state spaces than standard dynamic programming. The algorithm returns exact lower bound and estimated upper bound as well as approximate optimal control strategies.

Why Extensive formulation ?

An extensive formulation approach consists in representing the stochastic problem as a deterministic one and then calling a standard deterministic solver. It is mainly usable in a linear setting. Computational complexity is exponential in the number of stages.

Why Stochastic Dynamic Programming ?

Dynamic Programming is a standard tool to solve stochastic optimal control problem with independent noise. The method requires discretizing the state space, and its complexity is exponential in the dimension of the state space.

Installation

StochDynamicProgramming is a registered Julia package. To install the package, open Julia and enter

julia> ]
pkg> add StochDynamicProgramming

Usage

IJulia Notebooks are provided to explain how this package works. A first example on a two dams valley here.

Documentation

The documentation is built with Sphinx, so ensure that this package is installed:

sudo apt-get install python-sphinx

To build the documentation:

cd doc
make html

License

Released under Mozilla Public License (see LICENSE.md for further details).