A root \(r\) has children \(a,b\), each with two terminal children. Keeping \(r\) costs one with error six; splitting it adds overhead one. Keeping either \(a\) or \(b\) costs three with error two. Splitting \(a\) costs four with zero error, and splitting \(b\) costs five with zero error.
Reading the drawing
The finite candidate tree determines which subsets are legal prunings. The frontier compares all five choices and shows the declared budget optimum.
Drawing labels and data 12 labels
Read the original labels as selectable text. Tables preserve grid relationships; other short labels are grouped compactly.
- 0
- 2
- 4
- 6
- 1
- 5
- 10
- error
- cost
- Budget \(B=2\): cost \(8\)
- Penalty optimum: root or full split
\(8+2\lambda\le1+6\lambda\)
and \(8+2\lambda\le10\)
cannot both hold.
The five complete prunings have \((\text{cost},\text{error})\) pairs
At budget two the unique cheapest pruning is \(\{a_0,a_1,b\}\), costing eight. It is Pareto optimal, but never minimizes \({\operatorname{cost}}+\lambda{\operatorname{err}}\) for any \(\lambda\ge0\).
See the incompatible inequalities
To beat the root, that pruning would require \(8+2\lambda\le1+6\lambda\), hence \(\lambda\ge7/4\). To beat the full split, it would require \(8+2\lambda\le10\), hence \(\lambda\le1\). No multiplier meets both conditions.
The exact budget recurrence retains the point because it enumerates admissible weight allocations. A sweep of Lagrangian parameters sees only supported frontier points. The two compiler formulations are therefore genuinely different, even on this tiny tree.
Read this as
A penalty parameter is not a universal substitute for an explicit budget. Discrete, nonconvex frontiers can contain useful optima that no penalty selects.