Finding the minimum of the Bellman operator inside SDDP iterations

Specific Domains Optimization (Mathematical)
1

Hello!
I’m currently working on a multistage stochastic optimization problem using SDDP.jl. At each iteration (and each node), I would like to solve the following problem:
inf_{x \in X} T(V^k)(x)
where T is the Bellman operator and V^k is the current approximation of the value function. (Note that this is a two-stage problem)

Does anyone have suggestions on how to do this efficiently with SDDP?

Thanks in advance!

2

Hi @Mathis_3,

Why do you want this? Are you trying to solve some sort of decision-hazard formulation? What is the full problem you are trying to solve?

3

Hi @odow !

I’m working on a new method to solve multistage problems with an infinite horizon. As part of this approach, I need to solve : \inf_{x \in X} T(V^k)(x) which is a two stage problem (x represents the first stage decisions). In particular, for a given node, the problem considers the incoming state values as decision variables, and needs an outgoing state variable for each scenario.

The method I’m developing is quite general and can be applied to any problem currently supported by SDDP.jl.

4

Unfortunately this is not possible, and there are no simple work-arounds. A core design premise of SDDP.jl is that the uncertainty is realized before entering the node, and that each subproblem is a deterministic optimization problem for a single realization of the uncertainty.

I’m working on a new method to solve multistage problems with an infinite horizon.

I guess you know this, but SDDP.jl supports discounted infinite horizons problems.

5

Yes, I’m aware that SDDP.jl supports discounted infinite-horizon problems. However, in practice, when the discount factor \beta is close to 1, convergence becomes very slow. The method I’m developing aims to address this issue.

Thanks for your response! I’ll explore modifying the structure of SDDP.jl slightly to see if I can implement my approach within its framework.

6

when the discount factor
β
is close to 1, convergence becomes very slow

Yeah, this is mainly because of excessively long forward passes. You may want to experiment with the options in:

You could try terminate_on_cycle = true, or try setting some rollout_limit.

I’ll explore modifying the structure of SDDP.jl slightly to see if I can implement my approach within its framework.

This won’t be simple. It’s probably easiest to implement a new prototype of the algorithm to prove that it works. Then if it is promising we could consider ways to integrate it into SDDP.jl.