2
$\begingroup$

I am implementing a Stochastic Dual Dynamic Programming (SDDP) algorithm for multi-stage linear stochastic program. To validate the solution by SDDP, I also implemented an extensive form (deterministic equivalent, DE) based on discrete scenario tree. However, it turns out that the SDDP solution is different from DE's, even when SDDP draws samples from the scenario tree for DE.

In each Forward Simulation process, a sample path is randomly drawn from the scenario tree. In each Backward Recursion process, all the possible sample paths are used for cuts generation. I calculated the SDDP lower bound (LB) as in https://doi.org/10.1007/BF01582895. To be brief, the LB is the initial stage objective + estimator (bounded by cuts added) of the future expected costs. I calculated the SDDP upper bound (UB) by recursively solving problems from stage 0 to T with all the possible sample paths from the scenario tree. The UB is calculated as the expected cost over all the possibilities.

My questions are:

  1. Should I expect the SDDP UB (based on my definition) to be equal to DE's objective?
  2. If not 1, what is the possible relationship between SDDP's LB and UB with DE's objective?
$\endgroup$
1
  • $\begingroup$ DEBUG: applied standard SDDP to Markov data series. $\endgroup$ Oct 25, 2022 at 15:01

1 Answer 1

2
$\begingroup$

Once converged, the objective of the first-stage problem in SDDP (if minimizing, this is your SDDP lower bound) will equal the objective value of the deterministic equivalent. In theory, if you can simulate every possible scenario, then the mean of those simulation values (if minimizing, this is your SDDP upper bound) will also equal the deterministic equivalent objective value. But usually there are too many scenarios to simulate, so you get a statistical estimate for the upper bound.

Having said that, the in theory part is important. There are a variety of computational reasons why, when simulated, you might not recover the same objective value, but that's a much longer explanation. Moreover, everything I have said relates only to the first stage objective value. The state and control variables may be different, and the objective values deeper in the tree may also be different.

I am implementing a Stochastic Dual Dynamic Programming (SDDP) algorithm for multi-stage linear stochastic program.

I general, I would encourage you not to code your own implementation of the algorithm. As you're probably starting to find, it's really tricky to get right.

Use an (shameless self-promotion) general purpose implementation like: https://github.com/odow/SDDP.jl. It is battle-tested, and implements a much greater bag of tricks than the classical T-stage linear SDDP.

If you do decide to keep coding your own algorithm, SDDP.jl has a number of tutorials that might be helpful: https://odow.github.io/SDDP.jl/stable/tutorial/theory/21_theory_intro/

$\endgroup$
1
  • 1
    $\begingroup$ Oscar, thanks! You are completely right (about SDDP convergence and implementation difficulties). Implementing SDDP is complicated, but it helps beginner (me) understand how the algorithm works. $\endgroup$ Oct 25, 2022 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.