DCT Laboratory — Volume II, Chapter 3
Convex Enterprise Optimization
This laboratory demonstrates
Seed 26203 · Companion to Chapter 3 and AXIOM Lab 2.3 (module AXIOM-03) · Mirrored in DCT_V2_Ch03_Lab.xlsx
This laboratory reproduces Worked Example 3.1, How Good Is the Three-Round Plan?, with the book's declarations, and works the five steps of AXIOM Lab 2.3: recognize, solve, audit, bound, stress the prices. It ends with the two generic cases of Online Appendix 3.B.1 and 3.B.2, the two-channel budget's dual function and a tiered penalty at its kink. Every Meridian number below is the book's (Table 3.5, Figure 3.3, Online Appendix 3.B.4); the final cell checks them. Money is in $ million, undiscounted.
The declarations (Worked Example 3.1, the situation)
The instance is Worked Example 2.1's, built on Volume I's automation program (Volume I, Worked Example 6.1). A round costs $120 million, closes half the gap between operational efficiency and its ceiling of 85, and raises workforce capability by a point; it can start only with capability of at least 55. Each efficiency point above today's 71 saves $10 million a year from the year of the round, so a first round saves $70 million a year. Liquidity starts at $620 million; the board keeps its $350 million floor after paying for a round and at every year end, and its end condition, at least $470 million at the end of year 6.
Both executive pledges are dropped. An optimizer chooses the rounds (the chief operating officer's) and the payouts (the chief financial officer's), and values a plan at its six-year payout plus ten years of the year-6 savings. Enumerating the 64 schedules of rounds gives Worked Example 2.1's answer: three rounds, in years 1 to 3, $455 million paid out plus ten years of the $122.5 million year-6 savings, a value of $1,680 million. The chief risk officer accepts the arithmetic but not the method.
Python Code
import itertools
import numpy as np
from scipy.optimize import minimize
import matplotlib.pyplot as plt
plt.rcParams.update({"figure.dpi": 110, "axes.spines.top": False, "axes.spines.right": False})
SEED = 26203 # the lab's seed: the random chords of Panel 1 and the random starting plans of Panel 2
COST, CEIL, E0, HALF, VAL = 120.0, 85.0, 71.0, 0.5, 10.0 # a round: $120m; efficiency ceiling 85, today 71;
# a round closes half the gap; $10m a year a point
Q0, FLOOR, Q_END = 620.0, 350.0, 470.0 # liquidity today; the board's floor; the end condition for year 6
W0, W_MIN = 58.0, 55.0 # workforce capability today; a round needs at least 55
K, M_WE = 6, 10.0 # six years; ten years of year-6 savings credited
SMAX = VAL * (CEIL - E0) # $140m a year once efficiency reaches its ceiling
SLOPE = SMAX * np.log(2.0) # 97.04: the savings' slope, S'(Z) = 97.04 x 2^-Z (Panel 1)
PLANS = np.array(list(itertools.product((0, 1), repeat=K)), dtype=float) # the 64 schedules of rounds
def volume1(z):
# Volume I's recursion with nothing paid out: each round closes half the remaining efficiency gap
q, e, w, rows, ok = Q0, E0, W0, [], True
for k in range(K):
after = q - COST * z[k] # liquidity after paying for the year's round
if z[k]:
ok &= after >= FLOOR and w >= W_MIN
e, w = e + HALF * (CEIL - e), w + 1
s = VAL * (e - E0) # the year's savings
q = after + s
ok &= q >= FLOOR
rows.append((after, s, q))
return np.array(rows), bool(ok and q >= Q_END)
RUNS = [volume1(z) for z in PLANS]
FEASIBLE = np.array([ok for _, ok in RUNS])
NET = np.array([rows[-1, 2] for rows, _ in RUNS]) # year-6 liquidity with nothing paid out; all above 470 can be paid
S6 = np.array([rows[-1, 1] for rows, _ in RUNS]) # the year-6 savings
def lumpy_values(M):
# every plan's value at credits M: everything above $470m paid out, plus M years of the year-6 savings
M = np.atleast_1d(np.asarray(M, float))
return np.where(FEASIBLE, NET - Q_END + M[:, None] * S6, -np.inf)
def label(z):
on = [k + 1 for k in range(K) if z[k] > 0.5]
if on == list(range(1, len(on) + 1)) and len(on) > 1:
return f"years 1-{len(on)}"
return "years " + ", ".join(map(str, on)) if on else "no rounds"
V_LUMPY = lumpy_values(M_WE)[0]
BEST = int(V_LUMPY.argmax())
print(f"{len(PLANS)} schedules of rounds; {FEASIBLE.sum()} keep the floors, the capability precondition and the end condition")
print(f"best at ten years' credit, by enumeration: rounds in {label(PLANS[BEST])}, "
f"{NET[BEST] - Q_END:.2f} paid out + 10 x {S6[BEST]:.2f} of year-6 savings = {V_LUMPY[BEST]:,.2f}")64 schedules of rounds; 64 keep the floors, the capability precondition and the end condition best at ten years' credit, by enumeration: rounds in years 1-3, 455.00 paid out + 10 x 122.50 of year-6 savings = 1,680.00
Panel 1 — Recognize: relax the rounds in a form that shows convexity (Worked Example 3.1, Step 1; Table 3.2, Theorem 3.2)
AXIOM Lab 2.3, step 1. Let rounds be fractions, . Every lumpy plan remains available, so the relaxation's value will be a ceiling (Proposition 3.2(i)), provided the relaxation can be solved with a certificate, which needs convexity. Written as Volume I wrote it, each round closing half the remaining gap, the relaxed model multiplies rounds: after two years the gap is points, and two half rounds save $61.25 million in year 2, less than either whole-round plan they blend ($70 million each). The chord test fails. Written instead as , identical at every lumpy plan, the gap is an exponential of a sum of decisions, a convex shape in Table 3.2. Savings , with the rounds to date, are then concave, and so is liquidity . The explorer tests both forms on the 64 lumpy plans and on random chords, and issues the certificate block by block (Theorem 3.2(ii)).
Python Code
def savings(Z):
# the exponential form: after Z rounds the gap is 14 x 2^-Z points, so the savings are 140 (1 - 2^-Z)
return SMAX * (1.0 - 2.0 ** -np.asarray(Z, float))
def slope(Z):
return SLOPE * 2.0 ** -np.asarray(Z, float)
def volume1_form(z):
# Volume I's form written for fractional rounds: a round multiplies the gap by (1 - z_k / 2)
return SMAX * (1.0 - np.cumprod(1.0 - HALF * np.asarray(z, float), axis=-1))
def exponential_form(z):
return savings(np.cumsum(np.asarray(z, float), axis=-1))
diff_e = max(abs(rows[:, 1] - exponential_form(z)).max() for z, (rows, _) in zip(PLANS, RUNS))
diff_v = max(abs(rows[:, 1] - volume1_form(z)).max() for z, (rows, _) in zip(PLANS, RUNS))
print(f"the 64 lumpy plans, year by year: both forms give Volume I's savings exactly "
f"(largest difference {diff_e:.1e} exponential, {diff_v:.1e} Volume I's)")
y2 = lambda z1, z2: float(volume1_form([z1, z2])[1]) # year-2 savings in Volume I's form
blend, ends = y2(0.5, 0.5), (y2(1, 0), y2(0, 1))
corners = (y2(0, 0) + y2(1, 1)) / 2
print(f"\nVolume I's form, year-2 savings: {ends[0]:.2f} at (1, 0) and {ends[1]:.2f} at (0, 1); two half rounds, "
f"(0.5, 0.5), save {blend:.2f}")
print(f" the violating chord: the blend is worth less than the blend of the values, so not concave;")
print(f" (0, 0) and (1, 1) average {corners:.2f} < {blend:.2f}, so not convex either")
print(f" curvature in (z1, z2): [[0, {-SMAX * HALF ** 2:.0f}], [{-SMAX * HALF ** 2:.0f}, 0]], eigenvalues "
f"{-SMAX * HALF ** 2:.0f} and +{SMAX * HALF ** 2:.0f}: indefinite, a product of decisions")
print(f"exponential form, two half rounds: {float(exponential_form([0.5, 0.5])[1]):.2f}, the blend of 70 and 70; "
f"its curvature S''(Z) 11' has eigenvalues <= 0")
rng = np.random.default_rng(SEED) # the lab's seed: 100,000 random chords between fractional plans
N = 100_000
za, zb, th = rng.random((N, K)), rng.random((N, K)), rng.random((N, 1))
pa, pb = rng.uniform(0, 100, (N, K)), rng.uniform(0, 100, (N, K))
zm, pm = (1 - th) * za + th * zb, (1 - th) * pa + th * pb
def failed(f):
# percent of chords on which the blend is worth less than the blend of the values, year by year
return 100 * (f(zm, pm) < (1 - th) * f(za, pa) + th * f(zb, pb) - 1e-9).mean(axis=0)
print(f"\nchord test on {N:,} random chords (seed {SEED}): percent failing, years 1 to 6")
for name, form in (("Volume I's form", volume1_form), ("exponential form", exponential_form)):
s = failed(lambda z, p: form(z))
q = failed(lambda z, p: Q0 + np.cumsum(form(z) - COST * z - p, axis=-1))
print(f" {name:17s} savings " + " ".join(f"{v:5.1f}" for v in s) + " liquidity " + " ".join(f"{v:5.1f}" for v in q))
a, b = (0.0, 0.0), (2.0, float(savings(2.0)) / 2)
mid, need = ((a[0] + b[0]) / 2, (a[1] + b[1]) / 2), float(savings(1.0)) / 2
print(f"\nthe CFO's pledge p >= S/2, at (rounds to date, payout): ({a[0]:.0f}, {a[1]:.2f}) and ({b[0]:.0f}, {b[1]:.2f}) "
f"keep it; their midpoint ({mid[0]:.0f}, {mid[1]:.2f}) needs p >= {need:.2f}")
print(" a concave quantity held below the payout: not convex (the board dropped it); a cap, p <= S/2, would be convex")
BLOCKS = [("rounds 0 <= z_k <= 1", "a box", "convex region"),
("gap 14 x 2^-Z_k", "exponential of a sum of decisions", "convex"),
("savings S_k = 140 - 10 x gap", "a constant less a convex function", "concave"),
("liquidity q_k = 620 + sum(S_j - 120 z_j - p_j)", "sum of concave and affine terms", "concave"),
("floors q >= 350, after a round and at year end", "a concave quantity above a floor", "convex commitment"),
("end condition q_6 >= 470", "a concave quantity above a floor", "convex commitment"),
("objective: payouts + 10 S_6", "affine plus concave", "concave"),
("CFO's pledge p_k >= S_k / 2 (dropped)", "a concave quantity below the payout", "NOT convex")]
print(f"\n{'block':49s}{'shape or rule (Table 3.2)':37s}certificate")
for blk, shape, cert in BLOCKS:
print(f"{blk:49s}{shape:37s}{cert}")the 64 lumpy plans, year by year: both forms give Volume I's savings exactly (largest difference 0.0e+00 exponential, 0.0e+00 Volume I's) Volume I's form, year-2 savings: 70.00 at (1, 0) and 70.00 at (0, 1); two half rounds, (0.5, 0.5), save 61.25 the violating chord: the blend is worth less than the blend of the values, so not concave; (0, 0) and (1, 1) average 52.50 < 61.25, so not convex either curvature in (z1, z2): [[0, -35], [-35, 0]], eigenvalues -35 and +35: indefinite, a product of decisions exponential form, two half rounds: 70.00, the blend of 70 and 70; its curvature S''(Z) 11' has eigenvalues <= 0 chord test on 100,000 random chords (seed 26203): percent failing, years 1 to 6 Volume I's form savings 0.0 49.7 57.5 61.1 63.0 64.1 liquidity 0.0 49.7 55.9 58.6 60.1 60.9 exponential form savings 0.0 0.0 0.0 0.0 0.0 0.0 liquidity 0.0 0.0 0.0 0.0 0.0 0.0 the CFO's pledge p >= S/2, at (rounds to date, payout): (0, 0.00) and (2, 52.50) keep it; their midpoint (1, 26.25) needs p >= 35.00 a concave quantity held below the payout: not convex (the board dropped it); a cap, p <= S/2, would be convex block shape or rule (Table 3.2) certificate rounds 0 <= z_k <= 1 a box convex region gap 14 x 2^-Z_k exponential of a sum of decisions convex savings S_k = 140 - 10 x gap a constant less a convex function concave liquidity q_k = 620 + sum(S_j - 120 z_j - p_j) sum of concave and affine terms concave floors q >= 350, after a round and at year end a concave quantity above a floor convex commitment end condition q_6 >= 470 a concave quantity above a floor convex commitment objective: payouts + 10 S_6 affine plus concave concave CFO's pledge p_k >= S_k / 2 (dropped) a concave quantity below the payout NOT convex
Panel 2 — Solve: the relaxation and its duality gap (Worked Example 3.1, Step 2: $1,687.1 million)
AXIOM Lab 2.3, step 2. The book declares the relaxation in disciplined convex form, which CVXPY accepts, and solves it with the interior-point solver Clarabel, which returns after 15 iterations. This notebook needs only numpy, so it writes out the interior-point method of Section 3.6. Each commitment gets a barrier ; for a weight the method maximizes by Newton's method (the central path), then raises tenfold. Each centred plan comes with prices that leave a duality gap of for its commitments, so the gap closes on a schedule known in advance; the method stops at a few parts in a billion. The answer: whole rounds in years 1 to 3, 0.39 of a round in year 4, none after, worth $1,687.1 million, a ceiling on every plan that can be run. Started from twenty random plans, the search ends at the same value: in a convex instance no search stalls short of the best (Theorem 3.1(i)).
Python Code
TRI = np.tril(np.ones((K, K))) # cumulative sums: rounds to date Z = TRI z
class Relaxation:
# Worked Example 3.1's relaxation in exponential form, x = (z, p): maximize the payouts plus M years of the
# year-6 savings; every commitment is written h_i(x) >= 0. An optional cap on the capital: 120 sum z <= cap.
def __init__(self, M=M_WE, cap=None):
self.M, self.cap = M, cap
self.names = ([f"round limit, year {k + 1}" for k in range(K)] + [f"no negative round, year {k + 1}" for k in range(K)]
+ [f"payout >= 0, year {k + 1}" for k in range(K)] + [f"floor after the round, year {k + 1}" for k in range(K)]
+ [f"floor at year end, year {k + 1}" for k in range(K)] + ["end condition"]
+ (["capital cap"] if cap is not None else []))
self.m = len(self.names)
def evaluate(self, x):
z, p = x[:K], x[K:]
Z = TRI @ z
S, dS = savings(Z), slope(Z)
q = Q0 + TRI @ (S - COST * z - p) # year-end liquidity
dq = np.hstack([TRI @ (dS[:, None] * TRI) - COST * TRI, -TRI]) # its gradient, year by year
before = np.vstack([np.zeros(2 * K), dq[:-1]]) # gradient of last year's liquidity
h = np.r_[1 - z, z, p, np.r_[Q0, q[:-1]] - COST * z - FLOOR, q - FLOOR, q[-1] - Q_END]
A = np.vstack([np.hstack([-np.eye(K), np.zeros((K, K))]), np.hstack([np.eye(K), np.zeros((K, K))]),
np.hstack([np.zeros((K, K)), np.eye(K)]), before - COST * np.hstack([np.eye(K), np.zeros((K, K))]),
dq, dq[-1:]]) # rows: gradients of the slacks h_i
if self.cap is not None:
h = np.r_[h, self.cap - COST * z.sum()]
A = np.vstack([A, np.r_[-COST * np.ones(K), np.zeros(K)]])
J = p.sum() + self.M * S[-1]
gJ = np.r_[self.M * dS[-1] * np.ones(K), np.ones(K)]
return J, gJ, h, A, dS
def newton_step(self, x, t):
# Newton's method on t J + sum log h: the curvature of the savings enters through the liquidity slacks
J, gJ, h, A, dS = self.evaluate(x)
g = t * gJ + A.T @ (1 / h)
w = np.zeros(K) # weight of each year's liquidity in the curvature
w[:-1] += 1 / h[3 * K + 1:4 * K]
w += 1 / h[4 * K:5 * K]
w[-1] += 1 / h[5 * K]
d2S = -np.log(2.0) * dS # S''(Z) < 0: the savings are concave
H = -(A.T * (1 / h ** 2)) @ A
H[:K, :K] += TRI.T @ np.diag(d2S * np.cumsum(w[::-1])[::-1]) @ TRI + t * self.M * d2S[-1] * np.ones((K, K))
# payouts can wait, so the value is flat along their timing and the system is nearly singular there:
# solve it, scaled, in its well-determined directions
d = 1 / np.sqrt(-np.diag(H))
lam, V = np.linalg.eigh(d[:, None] * H * d[None, :])
keep = np.abs(lam) > 1e-14 * np.abs(lam).max()
dx = d * (V[:, keep] @ ((V[:, keep].T @ (-d * g)) / lam[keep]))
return dx, float(g @ dx), J, h
def solve(self, x0=None, t=1.0, mu=10.0, gap=1e-5):
# the barrier method: centre, record the gap m/t, raise t; stop when m/t <= gap
if x0 is None:
x0 = np.r_[np.full(K, 0.5 if self.cap is None else min(0.5, 0.5 * self.cap / (COST * K))), np.full(K, 10.0)]
x, steps, path, trace = np.array(x0, float), 0, [], []
while True:
for _ in range(100):
dx, dec, J, h = self.newton_step(x, t)
if dec <= 2e-10:
break
F0, s = t * J + np.log(h).sum(), 1.0
for _ in range(60): # backtrack: stay strictly inside every commitment
Jn, _, hn, _, _ = self.evaluate(x + s * dx)
if np.all(hn > 0) and t * Jn + np.log(hn).sum() >= F0 + 0.25 * s * dec:
break
s *= 0.5
else:
break
x, steps = x + s * dx, steps + 1
trace.append(Jn)
J, _, h, _, _ = self.evaluate(x)
path.append((steps, t, self.m / t, J))
if self.m / t <= gap:
return x, 1 / (t * h), J, steps, path, trace
t *= mu
R = Relaxation()
X, LAM, V_BARRIER, STEPS, PATH, TRACE = R.solve()
print(f"barrier method: {R.m} commitments, 12 decisions")
print("centring weight t gap m/t value J Newton steps so far")
for i, (st, t, g, J) in enumerate(PATH):
print(f"{i + 1:5d} {t:12.0e} {g:12.1e} {J:16.5f} {st:9d}")
Z_RELAX = X[:K]
print(f"relaxation's best plan: rounds {np.round(Z_RELAX, 3)}, worth {V_BARRIER:,.3f}; "
f"ceiling and value agree to {PATH[-1][2]:.1e}, {PATH[-1][2] / V_BARRIER * 1e9:.1f} parts in a billion")
def closed_form(M):
# Online Appendix 3.B.4: payouts can wait, so the floors never bind and the end condition prices cash at $1;
# rounds go early: n whole rounds, then a fraction where (6 - n + M) S'(Z) = 120
best = None
for n in range(K + 1):
Zs = float(K) if n == K else float(np.clip(np.log2(SLOPE * (K - n + M) / COST), n, n + 1))
V = Q0 - Q_END + savings(np.minimum(np.arange(1, K + 1), Zs)).sum() - COST * Zs + M * savings(Zs)
if best is None or V > best[0] + 1e-12:
best = (V, Zs)
return best[0], np.clip(best[1] - np.arange(K), 0.0, 1.0)
V_STAR, Z_STAR = closed_form(M_WE)
print(f"closed form: S'(Z) = 140 ln 2 x 2^-Z = {SLOPE:.2f} x 2^-Z; Z = log2({SLOPE:.2f} x 13/120) = "
f"log2 {SLOPE * 13 / COST:.3f} = {Z_STAR.sum():.3f}; value {V_STAR:,.3f} (barrier method within {abs(V_STAR - V_BARRIER):.1e})")
print(f"its payouts (not unique: payouts can wait): {np.round(X[K:], 2)}, total {X[K:].sum():.2f}")
starts = []
for i in range(20): # the lab's seed: twenty random strictly feasible starting plans
x0 = np.r_[rng.uniform(0.05, 0.95, K), rng.uniform(0.5, 20.0, K)]
starts.append((R.evaluate(x0)[0], *R.solve(x0=x0)[2:4]))
starts = np.array(starts)
print(f"twenty random starting plans (seed {SEED}), worth {starts[:, 0].min():,.0f} to {starts[:, 0].max():,.0f}: "
f"every one ends at {starts[:, 1].mean():,.4f} (spread {np.ptp(starts[:, 1]):.0e}), in {starts[:, 2].min():.0f} to "
f"{starts[:, 2].max():.0f} Newton steps")
fig, ax = plt.subplots(figsize=(7.6, 3.6))
ax.semilogy(np.arange(1, len(TRACE) + 1), np.maximum(V_STAR - np.array(TRACE), 1e-12), color="#1F4E79", lw=2,
label=r"distance of the plan's value from the best, \$1,687.09m")
ax.semilogy([p[0] for p in PATH], [p[2] for p in PATH], "o--", color="#E65100", lw=1.2, ms=5,
label="duality gap m/t that the prices certify at each centring")
ax.axhline(1e-5, color="#999999", lw=0.8)
ax.text(1, 1.5e-5, "stop: a few parts in a billion", color="#616161", fontsize=8)
ax.set(xlabel="Newton steps along the central path", ylabel=r"gap (\$ million)",
title="The central path closes the duality gap (seed 26203)")
ax.legend(frameon=False, fontsize=8, loc="upper right"); plt.tight_layout(); plt.show()barrier method: 31 commitments, 12 decisions
centring weight t gap m/t value J Newton steps so far
1 1e+00 3.1e+01 1681.05040 11
2 1e+01 3.1e+00 1686.48762 17
3 1e+02 3.1e-01 1687.02869 23
4 1e+03 3.1e-02 1687.08270 29
5 1e+04 3.1e-03 1687.08810 35
6 1e+05 3.1e-04 1687.08864 41
7 1e+06 3.1e-05 1687.08870 47
8 1e+07 3.1e-06 1687.08870 53
relaxation's best plan: rounds [1. 1. 1. 0.394 0. 0. ], worth 1,687.089; ceiling and value agree to 3.1e-06, 1.8 parts in a billion
closed form: S'(Z) = 140 ln 2 x 2^-Z = 97.04 x 2^-Z; Z = log2(97.04 x 13/120) = log2 10.513 = 3.394; value 1,687.089 (barrier method within 6.0e-07)
its payouts (not unique: payouts can wait): [ 12.69 15.99 25.58 43.24 79.57 243.19], total 420.26
twenty random starting plans (seed 26203), worth 1,100 to 1,387: every one ends at 1,687.0887 (spread 2e-13), in 54 to 97 Newton steps

Panel 3 — Audit: the KKT conditions and the prices (Worked Example 3.1, Step 3; Theorem 3.5; Figure 3.3(a))
AXIOM Lab 2.3, step 3. The KKT verification module checks a returned plan and its prices independently of the solver, through four residuals: commitments, signs, complementarity products and stationarity. Then rebuild the economics. The marginal value of a round in year is the savings it adds from year to year 6 plus ten years of the year-6 savings it adds, : $204.9, $156.4, $132.1, $120.0, $110.8 and $101.5 million, against a cost of $120 million. Rounds are whole where the margin exceeds the cost, partial where it equals it, and absent where it falls short: complementary slackness and stationarity (Theorem 3.5(i)). The excess prices each year's limit; the shortfall prices forcing a round. The floors carry no price, because payouts can wait; the end condition costs exactly a dollar of payout per dollar. Charged at these prices, no schedule of rounds, divisible or whole, within the limits or paying for breaking them, is worth more than $1,687.1 million (Theorem 3.4(i)), and the relaxation's plan attains that figure (part (iii)).
Python Code
def marginal_values(z, M=M_WE):
# a round in year j adds S'(Z_k) in each year k >= j, and M more years of S'(Z_6)
d = slope(np.cumsum(z))
return np.array([d[j:].sum() + M * d[-1] for j in range(K)])
MV = marginal_values(Z_STAR)
LIMIT = np.where(Z_STAR > 1 - 1e-9, MV - COST, 0.0) # price of each year's one-round limit
FORCE = np.where(Z_STAR < 1e-9, COST - MV, 0.0) # price of forcing a round into the year
print("year round S'(Z_k) marginal value price of the limit price of forcing a round")
for j in range(K):
print(f"{j + 1:4d} {Z_STAR[j]:7.3f} {slope(Z_STAR.cumsum())[j]:9.2f} {MV[j]:13.2f} {LIMIT[j]:16.2f} {FORCE[j]:20.2f}")
J, gJ, h, A, _ = R.evaluate(X) # the four residuals of the solver's returned plan and prices
resid = {"commitments (largest breach)": max(0.0, -h.min()), "signs (most negative price)": max(0.0, -LAM.min()),
"complementarity (largest |price x slack|)": np.abs(LAM * h).max(),
"stationarity (largest |grad J + A' price|)": np.abs(gJ + A.T @ LAM).max()}
print("\nKKT verification of the returned plan and prices:")
for k, v in resid.items():
print(f" {k:45s} {v:.1e}")
priced = {nm: l for nm, l in zip(R.names, LAM) if l > 1e-4}
print(" the solver's prices above 1e-4:", "; ".join(f"{nm} {l:.3f}" for nm, l in priced.items()))
print(f" floors: largest price {LAM[3 * K:5 * K].max():.1e}, smallest slack {h[3 * K:5 * K].min():.1f}; "
f"end condition: price {LAM[5 * K]:.4f}")
print(f" the solver's prices against the rebuilt ones: largest difference "
f"{max(np.abs(LAM[:K] - LIMIT).max(), np.abs(LAM[K:2 * K] - FORCE).max()):.1e}")
def dual_bound(limit, force, M=M_WE, end=1.0):
# Theorem 3.4(i): price the end condition, the limits and the lower bounds (floors unpriced); maximize the
# Lagrangian over every z in R^6 and p >= 0. With the end condition at 1, payouts drop out.
def neg(z):
Zk = np.cumsum(z)
return -float(M * savings(Zk[-1]) + end * (Q0 - Q_END + savings(Zk).sum() - COST * Zk[-1])
+ limit @ (1 - z) + force @ z)
runs = [minimize(neg, z0, method="BFGS", options={"gtol": 1e-10, "maxiter": 2000})
for z0 in (np.full(K, 0.5), np.r_[1, 1, 1, 0.4, 0, 0], np.ones(K), np.zeros(K))]
r = min(runs, key=lambda r: r.fun)
return -r.fun, np.cumsum(r.x)
CEILING_KKT, _ = dual_bound(LIMIT, FORCE)
CEILING_END, Z_END = dual_bound(np.zeros(K), np.zeros(K))
print(f"\nceiling at Step 3's prices: the Lagrangian's maximum over every z in R^6 is {CEILING_KKT:,.3f} "
f"= the relaxation's value {V_STAR:,.3f}: plan and prices certify each other")
print(f"pricing only the end condition (limits neither priced nor enforced): 150 + 5 x 140 + max_Z [11 S(Z) - 120 Z] "
f"= {CEILING_END:,.2f}, at Z = {Z_END[-1]:.3f}: valid, but loose")
fig, ax = plt.subplots(figsize=(7.6, 3.6))
yrs = np.arange(1, K + 1)
kind = ["whole" if z > 1 - 1e-9 else ("partial" if z > 1e-9 else "none") for z in Z_STAR]
look = {"whole": ("#1F4E79", "a whole round"), "partial": ("#8FB3D9", f"{Z_STAR[3]:.2f} of a round"),
"none": ("#D9D9D9", "no round")}
for kd in ("whole", "partial", "none"):
sel = [k == kd for k in kind]
ax.bar(yrs[sel], MV[sel], width=0.62, color=look[kd][0], edgecolor="#1F4E79", lw=0.6, zorder=2, label=look[kd][1])
ax.axhline(COST, color="#B71C1C", lw=1.2, zorder=3, label=r"cost of a round, \$120m")
for y, v, lim, frc in zip(yrs, MV, LIMIT, FORCE):
ax.text(y, max(v, COST) + 4, f"{v:.1f}", ha="center", va="bottom", fontsize=8.5, color="#1A1A1A")
if lim > 0:
ax.text(y, COST + lim / 2, f"+{lim:.1f}", ha="center", va="center", fontsize=8, color="white")
if frc > 0:
ax.text(y, v - 6, f"-{frc:.1f}", ha="center", va="top", fontsize=8, color="#616161")
ax.set(xlim=(0.4, 6.6), ylim=(0, 240), xticks=yrs, xlabel="year of the round",
ylabel=r"marginal value of a round (\$ million)",
title="Rounds are whole where the margin exceeds the cost (seed 26203)")
ax.legend(frameon=False, fontsize=8, loc="upper right"); plt.tight_layout(); plt.show()year round S'(Z_k) marginal value price of the limit price of forcing a round 1 1.000 48.52 204.91 84.91 0.00 2 1.000 24.26 156.39 36.39 0.00 3 1.000 12.13 132.13 12.13 0.00 4 0.394 9.23 120.00 0.00 0.00 5 0.000 9.23 110.77 0.00 9.23 6 0.000 9.23 101.54 0.00 18.46 KKT verification of the returned plan and prices: commitments (largest breach) 0.0e+00 signs (most negative price) 0.0e+00 complementarity (largest |price x slack|) 1.0e-07 stationarity (largest |grad J + A' price|) 3.8e-05 the solver's prices above 1e-4: round limit, year 1 84.911; round limit, year 2 36.390; round limit, year 3 12.130; no negative round, year 5 9.231; no negative round, year 6 18.462; end condition 1.000 floors: largest price 1.8e-09, smallest slack 56.3; end condition: price 1.0000 the solver's prices against the rebuilt ones: largest difference 1.8e-06 ceiling at Step 3's prices: the Lagrangian's maximum over every z in R^6 is 1,687.089 = the relaxation's value 1,687.089: plan and prices certify each other pricing only the end condition (limits neither priced nor enforced): 150 + 5 x 140 + max_Z [11 S(Z) - 120 Z] = 1,838.51, at Z = 3.153: valid, but loose

Panel 4 — Bound the lumpy plans (Worked Example 3.1, Step 4; Proposition 3.2: within $7.1 million)
AXIOM Lab 2.3, step 4. Every lumpy plan is a relaxed plan with the same value, so none is worth more than $1,687.1 million. The three-round plan is worth $1,680.0 million: within $7.1 million, or 0.42 percent, of the ceiling (Proposition 3.2(iii)). This is the certificate the chief risk officer asked for, obtained from one convex solve and no enumeration; the enumeration below only confirms it. Rounding the relaxation's plan happens to work here, 0.39 rounds down to the three-round plan and four rounds are worth only $1,673.75 million, but rounding is not a method, as Panel 5 shows.
Python Code
relaxed_at_lumpy = np.array([Q0 - Q_END + exponential_form(z).sum() - COST * z.sum() + M_WE * exponential_form(z)[-1]
for z in PLANS])
print(f"every lumpy plan is a relaxed plan with the same value: largest difference {np.abs(relaxed_at_lumpy - V_LUMPY).max():.1e}")
lag = V_LUMPY + (1 - PLANS) @ LIMIT + PLANS @ FORCE # each plan's Lagrangian at Step 3's prices
print(f"at Step 3's prices each lumpy plan's Lagrangian is at most {lag.max():,.2f}: the ceiling bounds all 64")
GAP = V_STAR - V_LUMPY[BEST]
print(f"\nthe ceiling {V_STAR:,.2f}; the best of the 64, rounds in {label(PLANS[BEST])}, {V_LUMPY[BEST]:,.2f}: "
f"gap {GAP:.2f}, or {100 * GAP / V_LUMPY[BEST]:.2f} percent")
print("the five best lumpy plans and their distance from the ceiling:")
for i in np.argsort(-V_LUMPY)[:5]:
print(f" {label(PLANS[i]):18s} {V_LUMPY[i]:10,.2f} {V_STAR - V_LUMPY[i]:8.2f}")
down, up = int(np.floor(Z_STAR.sum())), int(np.ceil(Z_STAR.sum()))
early = lambda n: int(np.flatnonzero((PLANS == np.r_[np.ones(n), np.zeros(K - n)]).all(axis=1))[0])
ROUND_DOWN, ROUND_UP = V_LUMPY[early(down)], V_LUMPY[early(up)]
print(f"rounding the relaxation's {Z_STAR.sum():.3f} rounds: down, {down} rounds, {ROUND_DOWN:,.2f}; "
f"up, {up} rounds, {ROUND_UP:,.2f}")every lumpy plan is a relaxed plan with the same value: largest difference 0.0e+00 at Step 3's prices each lumpy plan's Lagrangian is at most 1,680.00: the ceiling bounds all 64 the ceiling 1,687.09; the best of the 64, rounds in years 1-3, 1,680.00: gap 7.09, or 0.42 percent the five best lumpy plans and their distance from the ceiling: years 1-3 1,680.00 7.09 years 1-4 1,673.75 13.34 years 1, 2, 3, 5 1,665.00 22.09 years 1, 2, 4 1,662.50 24.59 years 1, 2, 3, 6 1,656.25 30.84 rounding the relaxation's 3.394 rounds: down, 3 rounds, 1,680.00; up, 4 rounds, 1,673.75
Panel 5 — Stress the prices: move the credit (Worked Example 3.1, Step 5; Table 3.5; Figure 3.3(b)–(c))
AXIOM Lab 2.3, step 5. Repeat the solve for credits from 0 to 60 years. Three regularities appear. On bands of credit the relaxation's own answer is lumpy, so it is the best lumpy plan, proved without any search (Proposition 3.2(ii)); with no credit it proves Worked Example 2.1's two-round plan best. The ceiling never exceeds the best lumpy value by more than $10.3 million, and comes closest to that only where the best number of rounds changes, at the credits found in Chapter 2. And just past each of those credits rounding fails: at 54 years the relaxation runs 5.47 rounds, which round to five, while the best plan has six. A ceiling is reliable; a rounded answer is not.
Python Code
def closed_forms(Ms):
# the closed form for many credits at once: each candidate n, then the best (the first, if tied)
Ms = np.asarray(Ms, float)
Zn = np.array([np.full_like(Ms, K) if n == K else np.clip(np.log2(SLOPE * (K - n + Ms) / COST), n, n + 1)
for n in range(K + 1)])
Vn = (Q0 - Q_END + savings(np.minimum(np.arange(1, K + 1)[:, None, None], Zn[None])).sum(0)
- COST * Zn + Ms * savings(Zn))
i = np.argmax(Vn >= Vn.max(0) - 1e-9, axis=0)
return Vn[i, np.arange(len(Ms))], Zn[i, np.arange(len(Ms))]
def best_lumpy(Ms):
v = lumpy_values(Ms)
i = v.argmax(axis=1)
return v[np.arange(len(i)), i], PLANS[i].sum(axis=1), i
T35 = [0.0, 5.0, 10.0, 20.0, 40.0, 60.0]
ceil35, rounds35 = closed_forms(T35)
lv35, ln35, li35 = best_lumpy(T35)
print("Table 3.5 credit relaxation's rounds ceiling best lumpy plan its value gap")
for M, c, r, v, i in zip(T35, ceil35, rounds35, lv35, li35):
print(f"{M:17.0f} {r:15.2f} {c:16,.2f} {label(PLANS[i]):15s} {v:13,.2f} {c - v:9.2f}")
check = [Relaxation(M=M).solve()[2] for M in T35]
print(f"the barrier method re-solves every row: largest difference from the closed form {np.abs(np.array(check) - ceil35).max():.1e}")
BANDS = [(n, max(COST / float(slope(n)) - (K + 1 - n), 0.0), COST / float(slope(n)) - (K - n) if n < K else np.inf)
for n in range(2, K + 1)]
print("\nthe relaxation's answer is lumpy, and proves the lumpy plan best, for credits "
+ "; ".join(f"{lo:.2f} to {hi:.2f} ({n} rounds)" if np.isfinite(hi) else f"from {lo:.2f} ({n} rounds)"
for n, lo, hi in BANDS))
early_net = np.array([NET[early(n)] for n in range(K + 1)])
early_s6 = np.array([S6[early(n)] for n in range(K + 1)])
THRESH = [(early_net[n] - early_net[n + 1]) / (early_s6[n + 1] - early_s6[n]) for n in range(2, K)]
FRAC = np.log2(SLOPE / 70.0)
GAP_AT = 240 * (1 - 2.0 ** -FRAC) - COST * FRAC
print("the best number of rounds changes at credits " + ", ".join(f"{m:.2f}" for m in THRESH)
+ f" (Chapter 2); there the relaxation's fraction is log2({SLOPE:.2f}/70) = {FRAC:.3f}")
print(f" and the gap is 240 (1 - 2^-{FRAC:.3f}) - 120 x {FRAC:.3f} = {GAP_AT:.2f}")
MS = np.round(np.arange(0.0, 60.0 + 1e-9, 0.01), 2)
gap_scan = closed_forms(MS)[0] - best_lumpy(MS)[0]
MAXGAP, MAXGAP_AT = gap_scan.max(), MS[gap_scan.argmax()]
print(f"credits 0 to 60 in steps of 0.01: largest gap {MAXGAP:.2f}, at {MAXGAP_AT:.2f} years")
MF = np.round(np.arange(0.0, 60.0 + 1e-9, 0.001), 3)
wrong = np.floor(closed_forms(MF)[1] + 0.5) != best_lumpy(MF)[1]
edges = np.flatnonzero(np.diff(np.r_[0, wrong.astype(int), 0]))
WINDOWS = [(MF[s], MF[e - 1]) for s, e in zip(edges[::2], edges[1::2])]
ENDS = [COST * 2 ** (n + 0.5) / SLOPE - (K - n) for n in range(2, K)]
print("rounding to the nearest whole number picks the wrong number of rounds on credits (steps of 0.001): "
+ ", ".join(f"{a:.3f}-{b:.3f}" for a, b in WINDOWS))
print(" each window ends where the relaxation reaches n + 1/2 rounds, 120 x 2^(n + 1/2)/97.04 - (6 - n): "
+ ", ".join(f"{e:.2f}" for e in ENDS))
c54, r54 = closed_forms([54.0])
v54, n54, _ = best_lumpy([54.0])
print(f"at 54 years: the relaxation runs {r54[0]:.2f} rounds, which round to {np.floor(r54[0] + 0.5):.0f}; "
f"the best plan has {n54[0]:.0f} (gap {c54[0] - v54[0]:.2f})")
fig, ax = plt.subplots(figsize=(7.6, 3.6))
for i, (a, b) in enumerate(WINDOWS):
ax.axvspan(a, b, color="#B71C1C", alpha=0.22, lw=0, label="rounding picks the wrong number" if i == 0 else None)
ax.plot(MS, gap_scan, color="#2E7D32", lw=1.6, label="ceiling minus the best lumpy value")
ax.plot(T35, ceil35 - lv35, "o", color="#1F4E79", ms=5, label="Table 3.5's credits")
ax.axvline(M_WE, color="#999999", lw=0.8, ls=":")
ax.annotate(rf"largest: \${MAXGAP:.2f}m at {MAXGAP_AT:.2f} years", xy=(MAXGAP_AT, MAXGAP), xytext=(34, 11.4),
fontsize=8, color="#2E7D32", arrowprops=dict(arrowstyle="-", color="#2E7D32", lw=0.7))
ax.text(M_WE + 0.5, 0.4, "ten years", fontsize=7.5, color="#616161")
ax.set(xlim=(0, 60), ylim=(0, 15.5), yticks=[0, 2, 4, 6, 8, 10], xlabel="years of year-6 savings credited",
ylabel=r"gap (\$ million)", title=r"The ceiling stays within \$10.3m of the best lumpy plan (seed 26203)")
ax.legend(frameon=False, fontsize=8, loc="upper center", ncol=3); plt.tight_layout(); plt.show()Table 3.5 credit relaxation's rounds ceiling best lumpy plan its value gap
0 2.00 505.00 years 1-2 505.00 0.00
5 2.86 1,068.25 years 1-3 1,067.50 0.75
10 3.39 1,687.09 years 1-3 1,680.00 7.09
20 4.15 2,987.26 years 1-4 2,986.25 1.01
40 5.05 5,675.11 years 1-5 5,675.00 0.11
60 5.62 8,406.33 years 1-6 8,400.94 5.39
the barrier method re-solves every row: largest difference from the closed form 7.0e-07
the relaxation's answer is lumpy, and proves the lumpy plan best, for credits 0.00 to 0.95 (2 rounds); 5.89 to 6.89 (3 rounds); 16.79 to 17.79 (4 rounds); 37.57 to 38.57 (5 rounds); from 78.14 (6 rounds)
the best number of rounds changes at credits 2.86, 10.71, 25.43, 53.86 (Chapter 2); there the relaxation's fraction is log2(97.04/70) = 0.471
and the gap is 240 (1 - 2^-0.471) - 120 x 0.471 = 10.33
credits 0 to 60 in steps of 0.01: largest gap 10.33, at 53.86 years
rounding to the nearest whole number picks the wrong number of rounds on credits (steps of 0.001): 2.858-2.995, 10.715-10.990, 25.429-25.980, 53.858-54.961
each window ends where the relaxation reaches n + 1/2 rounds, 120 x 2^(n + 1/2)/97.04 - (6 - n): 3.00, 10.99, 25.98, 54.96
at 54 years: the relaxation runs 5.47 rounds, which round to 5; the best plan has 6 (gap 10.19)

Panel 6 — Stress the prices: cap the capital (Worked Example 3.1, Step 6; Theorem 3.5(iii): $0.31 to $0.42 a dollar)
AXIOM Lab 2.3, step 5, second part. Suppose the board also capped the program's capital at $360 million, three rounds' worth. The relaxation then chooses exactly the three rounds; its answer is lumpy, so it proves them best under the cap. The cap's price is one point of a range: an extra dollar of capital would buy a fraction of a year-4 round worth $0.31 net of its cost; a dollar cut would remove part of the year-3 round and lose $0.42. At a kink a cut costs more than an increase gains, and a solver reports one point of the range: Clarabel reports 0.370, this notebook's barrier method its own point. Theorem 3.5(iii) says that for every price in the range a cap of is worth at most ; re-solves check it.
Python Code
RC = Relaxation(cap=360.0)
XC, LC, V_CAP, _, _, _ = RC.solve(gap=1e-8)
PRICE_CAP = LC[-1]
RIGHT = ((K - 3 + M_WE) * float(slope(3)) - COST) / COST # a dollar more buys part of a year-4 round
LEFT = ((K - 3 + 1 + M_WE) * float(slope(3)) - COST) / COST # a dollar cut removes part of the year-3 round
print(f"capital capped at $360m: rounds {np.round(XC[:K], 3)}, worth {V_CAP:,.2f}: lumpy, so best under the cap")
print(f"the cap's price is a range: an increase gains 13 x {float(slope(3)):.2f}/120 - 1 = {RIGHT:.3f} a dollar, "
f"a cut loses 14 x {float(slope(3)):.2f}/120 - 1 = {LEFT:.3f}")
print(f" the barrier method reports {PRICE_CAP:.3f} and Clarabel 0.370: each solver reports one point of the range")
def capped(B, M=M_WE):
# the closed form under a cap: rounds go early until the capital runs out (or the uncapped answer is reached)
Z = np.minimum(np.asarray(B, float) / COST, closed_form(M)[1].sum())
return (Q0 - Q_END + savings(np.minimum(np.arange(1, K + 1)[:, None], np.atleast_1d(Z)[None])).sum(0)
- COST * Z + M * savings(Z))
SHIFTS = np.array([-72.0, -48.0, -24.0, -12.0, -1.0, -0.01, 0.01, 1.0, 12.0, 24.0, 48.0, 72.0])
RESOLVE = np.array([Relaxation(cap=360.0 + s).solve(gap=1e-8)[2] for s in SHIFTS])
print(f"\nre-solves at caps 360 + s (barrier method; the closed form agrees to {np.abs(RESOLVE - capped(360 + SHIFTS)).max():.0e})")
print(" s best value change a dollar")
for s, v in zip(SHIFTS, RESOLVE):
print(f"{s:+8.2f} {v:12.3f} {(v - V_CAP) / s:12.4f}")
d_up = (RESOLVE[SHIFTS == 0.01][0] - V_CAP) / 0.01
d_dn = (V_CAP - RESOLVE[SHIFTS == -0.01][0]) / 0.01
print(f"an increase gains at most {d_up:.3f} a dollar, a cut loses at least {d_dn:.3f}: the kink at $360 million")
print("\nTheorem 3.5(iii): a price bounds every re-solve, 1,680 + price x s, when the largest excess is not above zero")
for lam, what in ((RIGHT, "what an increase gains"), (0.370, "Clarabel's"), (PRICE_CAP, "the barrier method's"),
(LEFT, "what a cut loses"), (0.30, "below the range"), (0.43, "above the range")):
excess = RESOLVE - V_CAP - lam * SHIFTS
print(f" {lam:.3f} ({what}): largest excess {excess.max():+.5f}"
+ (" -> a price of the cap" if excess.max() <= 1e-6 else f" -> fails, at s = {SHIFTS[excess.argmax()]:+.2f}"))
BB = np.linspace(288, 432, 289)
fig, ax = plt.subplots(figsize=(7.6, 3.6))
ax.plot(BB, capped(BB), color="#1F4E79", lw=2, label="best value under the cap")
ax.plot(360 + SHIFTS, RESOLVE, "o", ms=5, mfc="white", mec="#1F4E79", mew=1.2, label="re-solves (barrier method)")
for lam, ls, col, lab in ((RIGHT, "--", "#E65100", f"1,680 + {RIGHT:.3f} s: what an increase can gain"),
(LEFT, ":", "#B71C1C", f"1,680 + {LEFT:.3f} s: what a cut must lose"),
(PRICE_CAP, "-.", "#616161", f"the barrier method's price, {PRICE_CAP:.3f}")):
ax.plot(BB, V_CAP + lam * (BB - 360), ls=ls, color=col, lw=1.2, label=lab)
ax.plot(360, V_CAP, "o", color="#1F4E79", ms=7)
ax.set(xlim=(288, 432), ylim=(1620, 1700), xlabel=r"capital cap, 360 + s (\$ million)", ylabel=r"best value (\$ million)",
title=r"The value of capital bends at \$360m (seed 26203)")
ax.legend(frameon=False, fontsize=8, loc="lower right"); plt.tight_layout(); plt.show()capital capped at $360m: rounds [1. 1. 1. 0. 0. 0.], worth 1,680.00: lumpy, so best under the cap
the cap's price is a range: an increase gains 13 x 12.13/120 - 1 = 0.314 a dollar, a cut loses 14 x 12.13/120 - 1 = 0.415
the barrier method reports 0.373 and Clarabel 0.370: each solver reports one point of the range
re-solves at caps 360 + s (barrier method; the closed form agrees to 7e-10)
s best value change a dollar
-72.00 1625.649 0.7549
-48.00 1649.721 0.6308
-24.00 1667.569 0.5180
-12.00 1674.416 0.4654
-1.00 1679.581 0.4193
-0.01 1679.996 0.4152
+0.01 1680.003 0.3141
+1.00 1680.310 0.3103
+12.00 1683.235 0.2696
+24.00 1685.450 0.2271
+48.00 1687.089 0.1477
+72.00 1687.089 0.0985
an increase gains at most 0.314 a dollar, a cut loses at least 0.415: the kink at $360 million
Theorem 3.5(iii): a price bounds every re-solve, 1,680 + price x s, when the largest excess is not above zero
0.314 (what an increase gains): largest excess -0.00000 -> a price of the cap
0.370 (Clarabel's): largest excess -0.00045 -> a price of the cap
0.373 (the barrier method's): largest excess -0.00042 -> a price of the cap
0.415 (what a cut loses): largest excess -0.00000 -> a price of the cap
0.300 (below the range): largest excess +0.01030 -> fails, at s = +1.00
0.430 (above the range): largest excess +0.01073 -> fails, at s = -1.00

Panel 7 — Two generic cases (Online Appendix Examples 3.B.1 and 3.B.2; Figure 3.2)
Not Meridian. The two-channel budget, with , has the dual function : every price of the budget gives a ceiling, and the best price, , gives exactly the best value (Figure 3.2(b)); at , the price 0.25 and the value 50, while the price 0.5 gives the ceiling 62.5. A tiered penalty, nothing up to a target of 40, 1 per unit for the next 5 units and 3 per unit beyond, rewritten with one extra variable above each tier's line (Theorem 3.6(ii)), puts the best plan at the kink, where the prices of the two binding pieces identify the active tiers.
Python Code
a1, a2, BUDGET = 3.0, 4.0, 100.0
dual = lambda lam: (a1 ** 2 + a2 ** 2) / (4 * lam) + lam * BUDGET # the Lagrangian's maximum at the price lam
LAM_B = np.sqrt(a1 ** 2 + a2 ** 2) / (2 * np.sqrt(BUDGET))
x1, x2 = a1 ** 2 / (4 * LAM_B ** 2), a2 ** 2 / (4 * LAM_B ** 2)
VALUE_B = a1 * np.sqrt(x1) + a2 * np.sqrt(x2)
grid = np.linspace(0.05, 1.0, 95_001)
print(f"two-channel budget: best price {LAM_B:.2f}, plan ({x1:.0f}, {x2:.0f}), value {VALUE_B:.2f}; "
f"q(0.25) = {dual(0.25):.2f}, q(0.5) = {dual(0.5):.2f}")
print(f" the dual function's least value on a grid of prices: {dual(grid).min():.4f} at {grid[dual(grid).argmin()]:.4f}")
print(f" equal margins: 3/(2 sqrt 36) = {a1 / (2 * np.sqrt(x1)):.2f} = 4/(2 sqrt 64) = {a2 / (2 * np.sqrt(x2)):.2f}; "
f"the plan (50, 50) is worth {7 * np.sqrt(50):.2f}, so the best value lies between {7 * np.sqrt(50):.2f} and {dual(0.5):.1f}")
penalty = lambda x: np.maximum(np.maximum(0 * x, x - 40), 3 * (x - 40) - 10)
cost = lambda x: (x - 50) ** 2 / 4 + penalty(x)
xs = np.round(np.arange(30.0, 60.0 + 1e-9, 0.001), 3)
X_T = xs[cost(xs).argmin()]
print(f"\ntiered penalty: stationarity on the middle tier gives x = {50 - 2 * 1:.0f}, outside (40, 45); on the top tier "
f"x = {50 - 2 * 3:.0f}, outside (45, inf)")
SIG3 = ((50 - 45) / 2 - 1) / (3 - 1) # sigma_2 + sigma_3 = 1 and (45 - 50)/2 + sigma_2 + 3 sigma_3 = 0
SIG2 = 1 - SIG3
print(f" the best plan sits at the kink: x* = {X_T:.0f}, t* = {penalty(X_T):.0f}, cost {cost(X_T):.2f} (grid search agrees)")
print(f" prices of the two binding pieces: {SIG2:.2f} and {SIG3:.2f}; the slope the plan faces, "
f"{SIG2:.2f} + 3 x {SIG3:.2f} = {SIG2 + 3 * SIG3:.1f}, inside the range [1, 3] at the kink")two-channel budget: best price 0.25, plan (36, 64), value 50.00; q(0.25) = 50.00, q(0.5) = 62.50 the dual function's least value on a grid of prices: 50.0000 at 0.2500 equal margins: 3/(2 sqrt 36) = 0.25 = 4/(2 sqrt 64) = 0.25; the plan (50, 50) is worth 49.50, so the best value lies between 49.50 and 62.5 tiered penalty: stationarity on the middle tier gives x = 48, outside (40, 45); on the top tier x = 44, outside (45, inf) the best plan sits at the kink: x* = 45, t* = 5, cost 11.25 (grid search agrees) prices of the two binding pieces: 0.25 and 0.75; the slope the plan faces, 0.25 + 3 x 0.75 = 2.5, inside the range [1, 3] at the kink
Validation — the book's numbers, and agreement with DCT_V2_Ch03_Lab.xlsx
Each checkpoint is a number printed in Chapter 3 (Worked Example 3.1, Table 3.5, Figure 3.3) or in Online
Appendix 3.B.1, 3.B.2 and 3.B.4. The workbook recomputes the ones marked workbook with Excel formulas and
shows PASS against the same engine values on its Checks sheet.
Python Code
r = dict(zip(T35, zip(rounds35, ceil35, lv35)))
checks = [
("forms agree at the 64 lumpy plans (workbook)", diff_e, 0.0, 1e-9),
("two half rounds, year-2 savings (workbook)", blend, 61.25, 5e-3),
("a whole round, year-2 savings (workbook)", ends[0], 70.0, 5e-3),
("(0, 0) and (1, 1) average (workbook)", corners, 52.5, 5e-3),
("pledge: payout needed at the midpoint (workbook)", need, 35.0, 5e-3),
("relaxation's value, barrier method", V_BARRIER, 1687.09, 5e-3),
("relaxation's value, closed form (workbook)", V_STAR, 1687.09, 5e-3),
("relaxation's year-4 round (workbook)", Z_STAR[3], 0.394, 5e-4),
("rounds to date, log2 10.513 (workbook)", Z_STAR.sum(), 3.394, 5e-4),
("slope coefficient 140 ln 2 (workbook)", SLOPE, 97.04, 5e-3),
("S'(Z) in year 1 (workbook)", float(slope(1)), 48.52, 5e-3),
("S'(Z) in year 4 (workbook)", float(slope(Z_STAR.sum())), 9.23, 5e-3),
] + [(f"marginal value of a round, year {j + 1} (workbook)", MV[j], v, 5e-3)
for j, v in enumerate((204.91, 156.39, 132.13, 120.00, 110.77, 101.54))] + [
("price of the year-1 limit (workbook)", LIMIT[0], 84.91, 5e-3),
("price of the year-2 limit (workbook)", LIMIT[1], 36.39, 5e-3),
("price of the year-3 limit (workbook)", LIMIT[2], 12.13, 5e-3),
("price of forcing a round, year 5 (workbook)", FORCE[4], 9.23, 5e-3),
("price of forcing a round, year 6 (workbook)", FORCE[5], 18.46, 5e-3),
("solver's price of the year-1 limit", LAM[0], 84.91, 5e-3),
("solver's price of forcing a round, year 6", LAM[2 * K - 1], 18.46, 5e-3),
("solver's price of the end condition", LAM[5 * K], 1.0, 5e-4),
("solver's largest price of a floor", LAM[3 * K:5 * K].max(), 0.0, 5e-4),
("Lagrangian ceiling at the KKT prices", CEILING_KKT, 1687.09, 5e-3),
("ceiling pricing only the end condition (workbook)", CEILING_END, 1838.5, 0.05),
("best lumpy plan at ten years (workbook)", V_LUMPY[BEST], 1680.00, 5e-3),
("its payout (workbook)", NET[BEST] - Q_END, 455.0, 5e-3),
("its year-6 savings (workbook)", S6[BEST], 122.5, 5e-3),
("gap to the ceiling (workbook)", GAP, 7.09, 5e-3),
("gap, percent of the plan's value (workbook)", 100 * GAP / V_LUMPY[BEST], 0.42, 5e-3),
("rounded up: four rounds (workbook)", ROUND_UP, 1673.75, 5e-3),
] + [(f"Table 3.5, credit {M:.0f}: relaxation's rounds (workbook)", r[M][0], v, 5e-3)
for M, v in ((0, 2.00), (5, 2.86), (20, 4.15), (40, 5.05), (60, 5.62))] + [
(f"Table 3.5, credit {M:.0f}: ceiling (workbook)", r[M][1], v, 5e-3)
for M, v in ((0, 505.00), (5, 1068.25), (20, 2987.26), (40, 5675.11), (60, 8406.33))] + [
(f"Table 3.5, credit {M:.0f}: best lumpy value (workbook)", r[M][2], v, 5e-3)
for M, v in ((0, 505.00), (5, 1067.50), (20, 2986.25), (40, 5675.00), (60, 8400.94))] + [
(f"Table 3.5, credit {M:.0f}: gap (workbook)", r[M][1] - r[M][2], v, 5e-3)
for M, v in ((0, 0.00), (5, 0.75), (20, 1.01), (40, 0.11), (60, 5.39))] + [
(f"band of lumpy answers, {n} rounds: from (workbook)", lo, v, 5e-3)
for (n, lo, hi), v in zip(BANDS, (0.0, 5.89, 16.79, 37.57, 78.14)) if n > 2] + [
(f"band of lumpy answers, {n} rounds: to (workbook)", hi, v, 5e-3)
for (n, lo, hi), v in zip(BANDS, (0.95, 6.89, 17.79, 38.57)) if np.isfinite(hi)] + [
(f"best number of rounds changes, {n} to {n + 1} (workbook)", m, v, 5e-3)
for n, m, v in zip(range(2, K), THRESH, (2.86, 10.71, 25.43, 53.86))] + [
(f"rounding fails until, {n} rounds (workbook)", e, v, 5e-3)
for n, e, v in zip(range(2, K), ENDS, (3.00, 10.99, 25.98, 54.96))] + [
("rounding windows found by the scan", len(WINDOWS), 4, 0),
("relaxation's fraction at a threshold (workbook)", FRAC, 0.471, 5e-4),
("gap at a threshold (workbook)", GAP_AT, 10.33, 5e-3),
("largest gap, credits 0 to 60", MAXGAP, 10.33, 5e-3),
("credit of the largest gap", MAXGAP_AT, 53.86, 5e-3),
("relaxation's rounds at 54 years (workbook)", r54[0], 5.47, 5e-3),
("best lumpy rounds at 54 years (workbook)", n54[0], 6, 0),
("capital cap: value of the relaxation (workbook)", V_CAP, 1680.00, 5e-3),
("capital cap: an increase gains, a dollar (workbook)", RIGHT, 0.314, 5e-4),
("capital cap: a cut loses, a dollar (workbook)", LEFT, 0.415, 5e-4),
("capital cap: re-solve at 360.01, gain a dollar", d_up, 0.31, 5e-3),
("capital cap: re-solve at 359.99, loss a dollar", d_dn, 0.42, 5e-3),
("two-channel budget: best price (workbook)", LAM_B, 0.25, 5e-3),
("two-channel budget: value (workbook)", VALUE_B, 50.0, 5e-3),
("two-channel budget: ceiling at 0.5 (workbook)", dual(0.5), 62.5, 5e-3),
("two-channel budget: the plan (50, 50) (workbook)", 7 * np.sqrt(50), 49.50, 5e-3),
("tiered penalty: best plan (workbook)", X_T, 45.0, 5e-4),
("tiered penalty: cost (workbook)", cost(X_T), 11.25, 5e-3),
("tiered penalty: price of the middle tier (workbook)", SIG2, 0.25, 5e-3),
("tiered penalty: price of the top tier (workbook)", SIG3, 0.75, 5e-3),
]
ok = 0
for name, got, want, tol in checks:
status = "PASS" if abs(got - want) <= tol else "FAIL"
ok += status == "PASS"
print(f"{name:55s} {got:12.4f} book {want:10.4f} {status}")
print(f"\n{ok} of {len(checks)} checkpoints PASS")forms agree at the 64 lumpy plans (workbook) 0.0000 book 0.0000 PASS two half rounds, year-2 savings (workbook) 61.2500 book 61.2500 PASS a whole round, year-2 savings (workbook) 70.0000 book 70.0000 PASS (0, 0) and (1, 1) average (workbook) 52.5000 book 52.5000 PASS pledge: payout needed at the midpoint (workbook) 35.0000 book 35.0000 PASS relaxation's value, barrier method 1687.0887 book 1687.0900 PASS relaxation's value, closed form (workbook) 1687.0887 book 1687.0900 PASS relaxation's year-4 round (workbook) 0.3941 book 0.3940 PASS rounds to date, log2 10.513 (workbook) 3.3941 book 3.3940 PASS slope coefficient 140 ln 2 (workbook) 97.0406 book 97.0400 PASS S'(Z) in year 1 (workbook) 48.5203 book 48.5200 PASS S'(Z) in year 4 (workbook) 9.2308 book 9.2300 PASS marginal value of a round, year 1 (workbook) 204.9105 book 204.9100 PASS marginal value of a round, year 2 (workbook) 156.3902 book 156.3900 PASS marginal value of a round, year 3 (workbook) 132.1301 book 132.1300 PASS marginal value of a round, year 4 (workbook) 120.0000 book 120.0000 PASS marginal value of a round, year 5 (workbook) 110.7692 book 110.7700 PASS marginal value of a round, year 6 (workbook) 101.5385 book 101.5400 PASS price of the year-1 limit (workbook) 84.9105 book 84.9100 PASS price of the year-2 limit (workbook) 36.3902 book 36.3900 PASS price of the year-3 limit (workbook) 12.1301 book 12.1300 PASS price of forcing a round, year 5 (workbook) 9.2308 book 9.2300 PASS price of forcing a round, year 6 (workbook) 18.4615 book 18.4600 PASS solver's price of the year-1 limit 84.9105 book 84.9100 PASS solver's price of forcing a round, year 6 18.4615 book 18.4600 PASS solver's price of the end condition 1.0000 book 1.0000 PASS solver's largest price of a floor 0.0000 book 0.0000 PASS Lagrangian ceiling at the KKT prices 1687.0887 book 1687.0900 PASS ceiling pricing only the end condition (workbook) 1838.5097 book 1838.5000 PASS best lumpy plan at ten years (workbook) 1680.0000 book 1680.0000 PASS its payout (workbook) 455.0000 book 455.0000 PASS its year-6 savings (workbook) 122.5000 book 122.5000 PASS gap to the ceiling (workbook) 7.0887 book 7.0900 PASS gap, percent of the plan's value (workbook) 0.4219 book 0.4200 PASS rounded up: four rounds (workbook) 1673.7500 book 1673.7500 PASS Table 3.5, credit 0: relaxation's rounds (workbook) 2.0000 book 2.0000 PASS Table 3.5, credit 5: relaxation's rounds (workbook) 2.8636 book 2.8600 PASS Table 3.5, credit 20: relaxation's rounds (workbook) 4.1531 book 4.1500 PASS Table 3.5, credit 40: relaxation's rounds (workbook) 5.0512 book 5.0500 PASS Table 3.5, credit 60: relaxation's rounds (workbook) 5.6244 book 5.6200 PASS Table 3.5, credit 0: ceiling (workbook) 505.0000 book 505.0000 PASS Table 3.5, credit 5: ceiling (workbook) 1068.2505 book 1068.2500 PASS Table 3.5, credit 20: ceiling (workbook) 2987.2597 book 2987.2600 PASS Table 3.5, credit 40: ceiling (workbook) 5675.1102 book 5675.1100 PASS Table 3.5, credit 60: ceiling (workbook) 8406.3280 book 8406.3300 PASS Table 3.5, credit 0: best lumpy value (workbook) 505.0000 book 505.0000 PASS Table 3.5, credit 5: best lumpy value (workbook) 1067.5000 book 1067.5000 PASS Table 3.5, credit 20: best lumpy value (workbook) 2986.2500 book 2986.2500 PASS Table 3.5, credit 40: best lumpy value (workbook) 5675.0000 book 5675.0000 PASS Table 3.5, credit 60: best lumpy value (workbook) 8400.9375 book 8400.9400 PASS Table 3.5, credit 0: gap (workbook) 0.0000 book 0.0000 PASS Table 3.5, credit 5: gap (workbook) 0.7505 book 0.7500 PASS Table 3.5, credit 20: gap (workbook) 1.0097 book 1.0100 PASS Table 3.5, credit 40: gap (workbook) 0.1102 book 0.1100 PASS Table 3.5, credit 60: gap (workbook) 5.3905 book 5.3900 PASS band of lumpy answers, 3 rounds: from (workbook) 5.8928 book 5.8900 PASS band of lumpy answers, 4 rounds: from (workbook) 16.7855 book 16.7900 PASS band of lumpy answers, 5 rounds: from (workbook) 37.5711 book 37.5700 PASS band of lumpy answers, 6 rounds: from (workbook) 78.1421 book 78.1400 PASS band of lumpy answers, 2 rounds: to (workbook) 0.9464 book 0.9500 PASS band of lumpy answers, 3 rounds: to (workbook) 6.8928 book 6.8900 PASS band of lumpy answers, 4 rounds: to (workbook) 17.7855 book 17.7900 PASS band of lumpy answers, 5 rounds: to (workbook) 38.5711 book 38.5700 PASS best number of rounds changes, 2 to 3 (workbook) 2.8571 book 2.8600 PASS best number of rounds changes, 3 to 4 (workbook) 10.7143 book 10.7100 PASS best number of rounds changes, 4 to 5 (workbook) 25.4286 book 25.4300 PASS best number of rounds changes, 5 to 6 (workbook) 53.8571 book 53.8600 PASS rounding fails until, 2 rounds (workbook) 2.9952 book 3.0000 PASS rounding fails until, 3 rounds (workbook) 10.9905 book 10.9900 PASS rounding fails until, 4 rounds (workbook) 25.9810 book 25.9800 PASS rounding fails until, 5 rounds (workbook) 54.9619 book 54.9600 PASS rounding windows found by the scan 4.0000 book 4.0000 PASS relaxation's fraction at a threshold (workbook) 0.4712 book 0.4710 PASS gap at a threshold (workbook) 10.3286 book 10.3300 PASS largest gap, credits 0 to 60 10.3258 book 10.3300 PASS credit of the largest gap 53.8600 book 53.8600 PASS relaxation's rounds at 54 years (workbook) 5.4750 book 5.4700 PASS best lumpy rounds at 54 years (workbook) 6.0000 book 6.0000 PASS capital cap: value of the relaxation (workbook) 1680.0000 book 1680.0000 PASS capital cap: an increase gains, a dollar (workbook) 0.3141 book 0.3140 PASS capital cap: a cut loses, a dollar (workbook) 0.4152 book 0.4150 PASS capital cap: re-solve at 360.01, gain a dollar 0.3141 book 0.3100 PASS capital cap: re-solve at 359.99, loss a dollar 0.4152 book 0.4200 PASS two-channel budget: best price (workbook) 0.2500 book 0.2500 PASS two-channel budget: value (workbook) 50.0000 book 50.0000 PASS two-channel budget: ceiling at 0.5 (workbook) 62.5000 book 62.5000 PASS two-channel budget: the plan (50, 50) (workbook) 49.4975 book 49.5000 PASS tiered penalty: best plan (workbook) 45.0000 book 45.0000 PASS tiered penalty: cost (workbook) 11.2500 book 11.2500 PASS tiered penalty: price of the middle tier (workbook) 0.2500 book 0.2500 PASS tiered penalty: price of the top tier (workbook) 0.7500 book 0.7500 PASS 91 of 91 checkpoints PASS
Next. Chapter 4 leaves convexity: local optima that are not global, multipliers that price commitments only nearby, and lumpy decisions searched by branch-and-bound with a certified gap at every stage. Its Worked Example lets Meridian automate part of a plant line; this chapter's relaxation puts the best plan within $1.01 million of anything achievable, and five convex solves prove it best. AXIOM-03 runs this lab interactively (Lab 2.3); this notebook and the workbook are its reproducible record.


