Monotone Spending Plan via Isotonic L2 Regression (No-Borrowing)

Context: You observe yearly discretionary income profit[1..65] (nonnegative reals) and want a spending plan s[1..65] that is as even (nondecreasing) as possible over time while never spending future money. Formally, solve the quadratic program:

• Minimize: Σ_{t=1}^{65} (s_t − profit_t)^2
• Subject to:
  1. 0 ≤ s_1 ≤ s_2 ≤ … ≤ s_65 (smoothly nondecreasing spending)
  2. For all t: Σ_{i=1}^t s_i ≤ Σ_{i=1}^t profit_i (no borrowing)
  3. Σ_{t=1}^{65} s_t = Σ_{t=1}^{65} profit_t (no unallocated money)

Tasks:

1. Show that the solution is the isotonic L2 regression of profit under the nondecreasing constraint (solved by the Pool-Adjacent-Violators Algorithm, PAVA), and explain why it respects no-borrowing when mass is only shifted forward.
2. Implement an O(n) PAVA (R or Python) that returns s and the block structure.
3. Using set.seed(12345) and profit ~ rnorm(65, mean=1000, sd=100) (clip at 0 if needed), run your algorithm, report Σ(s_t − profit_t)^2, verify monotonicity, and demonstrate that cumulative spend never exceeds cumulative profit at any prefix.
4. Compare against a naive iterative averaging method (e.g., repeatedly averaging decreasing runs) on both correctness and runtime.