The SDDP Framework in One Page

Purpose

This chapter gives a reader new to stochastic dynamic programming the minimum context needed to follow the rest of this site. It covers the SDDP idea in one page; the chapters it links, starting with SDDP Algorithm, develop each claim in detail.

1. The Core Idea

Optimal dispatch over a multi-stage horizon cannot be solved by enumerating all scenarios: the number of scenario paths grows exponentially with the number of stages. SDDP avoids enumeration by exploiting the structure of the problem.

The stages and scenario paths introduced here are the special case of a more general policy graph of nodes and transitions; see Policy Graphs for the general structure.

At each stage, the future is summarised by a cost-to-go function $V_t$ — the minimum expected cost from that stage forward, as a function of the incoming state (reservoir levels, inflow lags). The dispatch problem obeys a stagewise (Bellman) recursion: the cost-to-go at stage $t$ is the expected cost of the best decision now plus the cost-to-go of the state that decision leaves behind:

$$V_t(x_{t-1}) = \mathbb{E}_{\omega_t}\!\left[\, \min_{x_t, u_t}\; c_t(x_t, u_t) + V_{t+1}(x_t) \,\right]$$

with terminal condition $V_{T+1}(x) = 0$. The minimisation runs over the feasible stage-$t$ state $x_t$ and control $u_t$, $(x_t, u_t) \in \mathcal{X}_t(x_{t-1}, \omega_t)$, given the incoming state $x_{t-1}$ and the realized uncertainty $\omega_t$. For LP subproblems $V_t$ is convex and piecewise linear — the property SDDP exploits.

SDDP never forms $V_{t+1}$ explicitly. It approximates it from below with a growing collection of affine functions called Benders cuts, each a valid underestimator everywhere:

$$V_{t+1}(x) \;\ge\; \beta_{0,i} + \beta_i^\top x \qquad \text{for every cut } i$$

In the stage problem the future cost is carried by an epigraph variable $\theta_t$, approximating $V_{t+1}(x_t)$ and bounded by every cut ($\theta_t \ge \beta_{0,i} + \beta_i^\top x_t$), so the approximation is the upper envelope $\max_i (\beta_{0,i} + \beta_i^\top x)$.

The approximation improves iteratively. Starting with no cuts, the algorithm alternates two passes:

Forward pass: Starting from the initial state, simulate a batch of scenario paths forward through all stages under the current policy — the rule that sets each stage’s decisions by solving the stage problem with the current cuts — recording the state each path reaches at every stage. These states are the trial points.

Backward pass: Starting from the last stage and working back to the second, solve each stage’s subproblem at every trial point under each of the stage’s openings, its pre-generated noise realizations, and aggregate the resulting dual information into one new cut per trial point for the previous stage: the single-cut formulation. The cut encodes how the cost-to-go changes as the incoming state changes.

One SDDP iteration: draw a batch of scenario paths (sampled, or every path when the forward pass is enumerated); the forward pass simulates them under the current policy and records the trial points; the backward pass adds one cut per trial point; periodic cut selection runs when configured; the bounds are updated; the loop repeats until the stopping rules are met, and the final cuts define the policy.

As iterations accumulate, the piecewise-linear approximation covers more of the state space and the lower bound never decreases:

The convex cost-to-go $V(x)$ approximated from below by Benders cuts. Each cut is a tangent at a trial state — its slope is the analytic derivative — and the upper envelope of the cuts tightens toward the true function as cuts are added.

2. Bounds and Convergence

SDDP maintains two bounds on the optimal (risk-adjusted) cost:

Lower bound $\underline{z}$: The first stage’s risk-adjusted value over its openings with the current cuts (definition). Under the hypotheses of Cut Management — when bounds and certificates hold, this value is a valid lower bound on the optimal (risk-adjusted) cost, and it does not decrease as cuts are added.

Upper bound $\bar{z}$: an enumerated forward pass, which visits every scenario path once, gives the policy’s exact risk-adjusted cost, an upper bound on the optimal value, when the risk measure is uniform across stages; a sampled forward pass gives the mean cost of its sampled paths, a statistical estimate with a confidence interval that certifies nothing (Upper Bound Evaluation, Tier 3).

The optimality gap is the upper bound minus the lower bound; its percent form normalises that difference by the magnitude of the lower bound, floored at one currency unit (see Optimality gap).

Training stops when its stopping rules are met: an iteration or time limit, a stalled lower bound, or, with an exact upper bound, a gap within tolerance (Stopping Rules).

A non-decreasing lower bound and a sampled upper-bound estimate with its 95% confidence band approach each other across iterations. The band describes the sampled cost and certifies nothing; the gap rule compares the lower bound with an exact upper bound.

Under an expectation measure at every stage and the hypotheses of Tier 2, which also names the cut-selection settings that leave them, the lower bound converges to the optimal value with probability 1 as iterations accumulate; under a risk-averse measure that convergence is not established.

3. Risk Measures

The basic SDDP algorithm minimises expected cost. Novomodelo supports risk-averse formulations through nested risk measures applied at each stage, based on the conditional value-at-risk (CVaR), which shifts weight toward high-cost scenarios:

$$\text{CVaR}_\alpha(Z) = \min_{\eta \in \mathbb{R}} \left\{ \eta + \frac{1}{\alpha} \mathbb{E}\left[(Z - \eta)^+\right] \right\}$$

where $\alpha \in (0, 1]$ is the tail fraction — $\text{CVaR}_\alpha$ is the expected cost in the worst $\alpha$-fraction of scenarios. Novomodelo uses a convex combination of expectation and CVaR,

$$\rho^{\lambda, \alpha}[Z] = (1 - \lambda)\, \mathbb{E}[Z] + \lambda \cdot \text{CVaR}_\alpha[Z]$$

with risk-aversion weight $\lambda \in [0, 1]$ ($\lambda = 0$ recovers the risk-neutral mean, $\lambda = 1$ is pure CVaR). The measure is applied inside the backward pass: cut coefficients are aggregated using risk-weighted averages rather than simple expectations. See Risk Measures for the formulation.

Cost distribution with the mean, $\mathrm{VaR}_\alpha$ and $\mathrm{CVaR}_\alpha$ marked and the worst $\alpha$ tail shaded; raising $\lambda$ moves the policy from the mean toward the tail.

4. Where to Go Next

This overview omits the implementation detail: the LP layout, cut storage, the scenario tree and the warm-start strategy. The System Modelling, Stochastic Modelling and The SDDP Algorithm groups cover them.

For the full algorithm, with stage LP formulation, cut coefficient derivation, and convergence monitoring, see SDDP Algorithm.

For the cut mechanics — how cuts are generated, stored, and pruned — see Cut Management.

Cross-References

• SDDP Algorithm — complete algorithmic treatment: stage LP formulation, cut generation, convergence monitoring
• Cut Management — cut storage, selection strategies, and domination pruning
• Risk Measures — CVaR and nested risk measure formulations for risk-averse SDDP
• Stopping Rules — iteration and time limits, bound stalling, the gap rule and how rules combine