Isotonic regression

Remarks

The set of non-decreasing vectors is a closed convex cone, so $\hat y$ is the projection of $y$ onto it for the weighted inner product, and it exists and is unique. It has the min-max formula $\hat y_i = \max_{s \le i} \min_{t \ge i} \mathrm{Av}(s, t)$, where $\mathrm{Av}(s, t) = \sum_{k=s}^{t} w_k y_k / \sum_{k=s}^{t} w_k$. The pool adjacent violators algorithm computes $\hat y$ in $O(n)$ steps: it merges adjacent blocks whose averages are out of order and replaces them by their weighted average. The same definition works for any partial order on the index set, with $z_i \le z_j$ required whenever $i$ precedes $j$.

Example: $y = (1, 3, 2)$ with equal weights. The pair $3, 2$ violates the order, and pooling gives $\hat y = (1, 2.5, 2.5)$, which is non-decreasing. Its squared error is $0 + 0.25 + 0.25 = 0.5$.

Non-example: $z = (1, 3, 2)$ itself has error $0$ but it is not non-decreasing, so it is not admissible; the monotone constraint is what makes $\hat y$ differ from $y$.