Chapter 10, Theorem 1 — multistage Jensen lower bound via aggregation

Fix a horizon $H$ and matrix dimensions $n, m$ (natural numbers, all of which may be zero). The statement is about two scenario trees of horizon $H$ — a fine tree $\mathcal{T}_F$ and a coarse tree $\mathcal{T}_C$ — each built from the bundle's own Tree definition, which is not unfolded here; what is used of it is only that a tree has a finite type of nodes, a distinguished root, a stage map assigning each node a stage $\operatorname{stage}(j)$ whose underlying value is a natural number, and an ancestor map $\operatorname{anc}$ (a total function, so $\operatorname{anc}$ of the root is some node, not "undefined"). Over these trees sit two instances $\mathcal{I}_F$ and $\mathcal{I}_C$ of the bundle's Instance structure, also not unfolded; the fields used are, for each node $j$: a probability-like scalar $p_j$, a vector $h_j$, a matrix $T_j$, a cost vector $c_j$, and a single recourse matrix $W$ shared across nodes. Together with these come two bundle-defined predicates that the statement leaves opaque: $\operatorname{Feasible}(\mathcal{I}, x)$ for a decision $x$, and a real-valued objective $\operatorname{obj}(\mathcal{I}, x)$. Nothing in the statement pins down what "feasible" means, what type $x$ ranges over beyond what these predicates accept, or how $\operatorname{obj}$ is computed from $p, h, T, c, W$; all of that lives in the imported definitions.

The hypotheses are as follows. There is an aggregation map $\operatorname{agg} : \operatorname{Node}(\mathcal{T}_F) \to \operatorname{Node}(\mathcal{T}_C)$ such that

• $\operatorname{agg}(\operatorname{root}_F) = \operatorname{root}_C$;
• for every fine node $j$, $\operatorname{stage}_C(\operatorname{agg}(j)) = \operatorname{stage}_F(j)$ (stages are preserved exactly);
• for every fine node $j$ whose stage value is not $0$, $\operatorname{agg}(\operatorname{anc}_F(j)) = \operatorname{anc}_C(\operatorname{agg}(j))$ (aggregation commutes with taking the parent, except that nothing is required at stage-$0$ nodes).

The data of the two instances are tied together by:

• $W_F = W_C$ (the recourse matrices coincide);
• for every fine node $j$, $c^F_j = c^C_{\operatorname{agg}(j)}$ (costs are copied from the aggregated node);
• for every coarse node $i$,

$$p^C_i \cdot h^C_i \;=\; \sum_{j \,:\, \operatorname{agg}(j) = i} p^F_j \cdot h^F_j,$$

the sum ranging over all fine nodes mapped to $i$ (an empty sum, hence the zero vector, if no fine node maps to $i$);

• for every coarse node $i$ whose stage value is not $0$,

$$p^C_i \cdot T^C_i \;=\; \sum_{j \,:\, \operatorname{agg}(j) = i} p^F_j \cdot T^F_j,$$

with the same convention; at stage-$0$ coarse nodes no relation between $T^C$ and $T^F$ is imposed.

Note that these are relations on the products $p \cdot h$ and $p \cdot T$; they do not say $p^C_i = \sum p^F_j$, nor that $h^C_i$ is a conditional expectation, and if $p^C_i = 0$ they force the fine-side sums to vanish while leaving $h^C_i$, $T^C_i$ arbitrary.

There is an arbitrary type $\Theta$ of labels and a labelling $\operatorname{curOutcome} : \operatorname{Node}(\mathcal{T}_C) \to \Theta$ such that for all coarse nodes $i, i'$ with $\operatorname{stage}_C(i) = \operatorname{stage}_C(i')$ and $\operatorname{curOutcome}(i) = \operatorname{curOutcome}(i')$, one has both $h^C_i = h^C_{i'}$ and $T^C_i = T^C_{i'}$. (This is vacuous if $\operatorname{curOutcome}$ is injective on each stage, and it forces all same-stage $h, T$ data to agree if $\Theta$ has one element.)

Finally, two real numbers $z_F$ and $z_C$ are given, each characterized as the attained minimum of its instance's objective over feasible decisions:

• $z_F \le \operatorname{obj}(\mathcal{I}_F, x)$ for every $x$ with $\operatorname{Feasible}(\mathcal{I}_F, x)$, and there exists some $x$ with $\operatorname{Feasible}(\mathcal{I}_F, x)$ and $\operatorname{obj}(\mathcal{I}_F, x) = z_F$;
• $z_C \le \operatorname{obj}(\mathcal{I}_C, x)$ for every $x$ with $\operatorname{Feasible}(\mathcal{I}_C, x)$, and there exists some $x$ with $\operatorname{Feasible}(\mathcal{I}_C, x)$ and $\operatorname{obj}(\mathcal{I}_C, x) = z_C$.

The conclusion is the single real inequality

$$z_C \;\le\; z_F .$$

Nothing is asserted about the objectives being convex, about $\operatorname{agg}$ being surjective, about the fine tree refining the coarse one in any structural sense beyond the three agg conditions, or about $p$ being nonnegative or summing to one.

In degenerate cases: if $H = 0$, or if either tree has a single node, the hypotheses reduce to statements about roots only and the claim is still $z_C \le z_F$ for whatever $\operatorname{Feasible}$ and $\operatorname{obj}$ yield there. If $n = 0$ or $m = 0$, the vectors and matrices are empty and the data hypotheses hold trivially. If some coarse node has no fine preimage under $\operatorname{agg}$, the corresponding hypothesis reads $p^C_i \cdot h^C_i = 0$ (and $p^C_i \cdot T^C_i = 0$ for non-initial stages). The attainment hypotheses require both feasible sets to be nonempty; if either Feasible predicate were unsatisfiable the theorem's hypotheses could not be met and it would assert nothing. Because the statement quantifies over arbitrary $z_F, z_C$ satisfying the minimum characterization, it does not itself define an optimal value; when a feasible set is nonempty but the objective is unbounded below, no real number satisfies the lower-bound hypothesis and the theorem again has no instances. Stage values are natural numbers, so "stage value $\ne 0$" is the only guard on the ancestor and $T$-matrix conditions; no subtraction, division, or integral appears in the statement itself, though any such junk-value behaviour inside the unexpanded Feasible, obj, Tree, and Instance definitions is inherited unseen.