Upper Bound Evaluation

Status: Not Implemented. This spec describes a planned design that has not yet been implemented.

Purpose

This spec defines the upper bound evaluation mechanism in Cobre via inner approximation (SIDP): the vertex-based value function approximation, Lipschitz interpolation, the linearized upper bound LP, gap computation, and configuration. It complements the outer approximation (cuts) described in SDDP Algorithm by providing a convergence certificate through deterministic upper bounds.

For notation conventions (index sets, parameters, decision variables, dual variables), see Notation Conventions.

Symbol convention: This spec uses $d$ for the discount factor. See Discount Rate.

1 Motivation

Standard SDDP provides only a lower bound (outer approximation) through cuts. For convergence verification, we need an upper bound (inner approximation). This is especially important for:

1. Risk-averse problems: CVaR objectives cannot be reliably estimated via Monte Carlo simulation of the policy
2. Convergence certificates: Gap $=\bar{z}-\underline{z}$ provides a true optimality measure
3. Conservative policies: Inner approximation gives “at most $Y$” guarantees

Deterministic vs. simulation-based upper bounds: The simulation-based stopping rules (see Stopping Rules) estimate an upper bound by running the SDDP policy on sampled scenarios and averaging costs. This is a statistical estimate — valid for risk-neutral problems but not for risk-averse (CVaR) objectives. The inner approximation described here provides a deterministic upper bound that is valid regardless of the risk measure.

2 Vertex-Based Inner Approximation

The inner approximation ${\bar{V}}_t(x)$ is constructed from vertices (visited state-value pairs):

$${\mathcal{V}}_t=\{(x^{(1)},{\bar{v}}^{(1)}),(x^{(2)},{\bar{v}}^{(2)}),\dots ,(x^{(n)},{\bar{v}}^{(n)})\}$$

where each vertex stores:

• $x^{(i)}$: State vector visited during forward passes
• ${\bar{v}}^{(i)}$: Upper bound on expected cost-to-go from that state (computed recursively)

3 Lipschitz Interpolation

For a new state $x$ not in ${\mathcal{V}}_t$, the upper bound is computed via Lipschitz interpolation:

$${\bar{V}}_t(x)=\underset{(x^{(i)},{\bar{v}}^{(i)})\in {\mathcal{V}}_t}{\min }\left\{{\bar{v}}^{(i)}+L_t\cdot \Vert x-x^{(i)}{\Vert }_1\right\}$$

where $L_t$ is the Lipschitz constant for stage $t$.

Interpretation: The upper bound at $x$ is the minimum over all vertices of “vertex value plus distance penalty.” This forms a concave piecewise-linear function — the inner (concave) counterpart to the outer (convex) cut approximation.

4 Lipschitz Constant Computation

The Lipschitz constant bounds the maximum rate of change of the value function with respect to the state. For SDDP with penalty-based feasibility (relatively complete recourse):

Backward accumulation:

$$L_T=c_{max}^{penalty}$$

$$L_t=d_{t\to t+1}\cdot L_{t+1}+c_{max}^{penalty,t}$$

where:

• $c_{max}^{penalty,t}$ is the maximum penalty coefficient at stage $t$ (e.g., deficit penalty in $/MWh)
• $d_{t\to t+1}$ is the discount factor for transition $t\to t+1$ (see Discount Rate)

Note: The discount factor $d$ appears in the Lipschitz accumulation because the future cost is discounted. Without discounting ($d=1$), $L_t$ grows linearly with the remaining horizon.

Example: With deficit penalty $1000$ $/MWh over 5 stages, no discounting:

5 Vertex Value Computation

During the upper bound evaluation pass (a backward pass variant):

At terminal stage $T$:

$${\bar{v}}^{(i)}={\mathbb{E}}_{{\omega }_T}\left[c_T(x^{(i)},{\omega }_T)\right]\text{(expected immediate cost only)}$$

At stage $t<T$:

For each vertex $(x^{(i)},\cdot )\in {\mathcal{V}}_t$:

1. For each scenario ${\omega }_t$, solve the stage subproblem with incoming state $x^{(i)}$ and realization ${\omega }_t$
2. Obtain the optimal next-stage state $x_{t+1}^{\ast }({\omega }_t)$
3. Evaluate the inner approximation at the next stage: $\bar{\theta }({\omega }_t)={\bar{V}}_{t+1}(x_{t+1}^{\ast }({\omega }_t))$
4. Set vertex value as the expected discounted cost-to-go:

$${\bar{v}}^{(i)}={\mathbb{E}}_{{\omega }_t}\left[c_t(x^{(i)},{\omega }_t)+d_{t\to t+1}\cdot \bar{\theta }({\omega }_t)\right]$$

Expectation: The vertex value is an expectation over scenarios, not a single-scenario value. This parallels the backward pass for cuts, which also computes expected cost-to-go.

6 Upper Bound Evaluation LP

For policy evaluation with inner approximation, the stage LP replaces the outer approximation (cut constraints on $\theta$) with inner approximation (vertex constraints on $\bar{\theta }$).

Standard LP (outer approximation — lower bound):

$$\min c_t^{\top }{x}_t+d_{t\to t+1}\cdot \theta$$

$$\text{s.t. }\theta \ge {\alpha }_k+{\pi }_k^{\top }{x}_t\forall k\text{ (cuts)}$$

Inner approximation LP (upper bound):

$$\min c_t^{\top }{x}_t+d_{t\to t+1}\cdot \bar{\theta }$$

$$\text{s.t. }\bar{\theta }\le {\bar{v}}^{(i)}+L_t\sum _j|x_{t,j}-x_j^{(i)}|\forall i\in {\mathcal{V}}_t\text{ (vertices)}$$

Direction: Cut constraints are lower bounds on $\theta$ ($\theta \ge \dots$). Vertex constraints are upper bounds on $\bar{\theta }$ ($\bar{\theta }\le \dots$). The cut approximation is convex (piecewise-linear from below); the vertex approximation is concave (piecewise-linear from above).

7 Linearized Upper Bound LP

The absolute value $|x_j-x_j^{(i)}|$ in the vertex constraints is linearized using standard splitting:

$$|x_j-x_j^{(i)}|=u_j^{(i)+}+u_j^{(i)-}$$

$$x_j-x_j^{(i)}=u_j^{(i)+}-u_j^{(i)-}$$

$$u_j^{(i)+},u_j^{(i)-}\ge 0$$

Additional variables (per vertex $i$, per state component $j$):

Constraints (for each vertex $i\in {\mathcal{V}}_t$):

$$\bar{\theta }\le {\bar{v}}^{(i)}+L_t\sum _j(u_j^{(i)+}+u_j^{(i)-})$$

$$x_j-x_j^{(i)}=u_j^{(i)+}-u_j^{(i)-}\forall j$$

8 Gap Computation

At each iteration $k$ where the upper bound is evaluated:

Lower bound (from cuts at stage 1):

$${\underline{z}}^k=c_1({\hat{x}}_1)+d_{1\to 2}\cdot {\underline{V}}_2({\hat{x}}_1)$$

Upper bound (from vertices at stage 1):

$${\bar{z}}^k=c_1({\hat{x}}_1)+d_{1\to 2}\cdot {\bar{V}}_2({\hat{x}}_1)$$

Relative gap:

$${\text{gap}}^k=\frac{{\bar{z}}^k-{\underline{z}}^k}{\max (1,|{\bar{z}}^k|)}\times 100\%$$

Convergence: As $k\to \infty$, ${\text{gap}}^k\to 0$ for convex problems with finitely many scenarios.

For stopping rules that use the gap, see Stopping Rules.

9 Computational Considerations

Recommendation: Enable upper bound evaluation every 5-10 iterations after an initial burn-in period (10+ iterations) for convergence monitoring without excessive overhead.

10 Infinite Horizon

For cyclic policy graphs (see Infinite Horizon), the inner approximation operates on the same seasonal cut-pool structure: vertices are organized by season $\tau$, not by absolute stage ID. The Lipschitz constant must account for the cumulative discount around the cycle, which bounds the geometric series of future contributions.

The convergence guarantee still holds: with $d_{cycle}<1$, both the outer (cut) and inner (vertex) approximations converge to the true value function at the fixed point.

11 References

Costa, B.F.P., & Leclere, V. (2023). “Duality of upper bounds in stochastic dynamic programming.” Optimization Online. https://optimization-online.org/?p=23738

Philpott, A.B., de Matos, V.L., & Finardi, E.C. (2013). “On solving multistage stochastic programs with coherent risk measures.” Operations Research, 61(4), 957-970. https://doi.org/10.1287/opre.2013.1175

Cross-References

• SDDP Algorithm — Core algorithm providing the outer approximation (lower bound) that this spec complements
• Notation Conventions — Standard symbols for state variables, value functions, and cost-to-go
• Discount Rate — Discount factor $d$ used in vertex value computation (§5) and Lipschitz accumulation (§4)
• Infinite Horizon — Seasonal vertex organization for cyclic policy graphs
• Cut Management — Outer approximation cuts that provide the lower bound counterpart
• Stopping Rules — Convergence criteria that use the gap between inner and outer approximations
• Risk Measures — CVaR objectives where deterministic upper bounds are essential
• Binary Formats §3.3 — FlatBuffers Vertex and StageVertices schemas for persistence
• Input Directory Structure §2.2 — upper_bound_evaluation configuration in config.json
• Configuration Reference — Full configuration schema with defaults