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
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.
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.
StochDynamicProgramming is a registered Julia package. To install the package, open Julia and enter
julia> ] pkg> add StochDynamicProgramming
IJulia Notebooks are provided to explain how this package works. A first example on a two dams valley here.
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
Released under Mozilla Public License (see LICENSE.md for further details).