形状约束实作：把密度阶梯和凸回归变成证书 ​

这一站对应形状约束学习路线。先读递减密度的有限似然理路Grenander递减密度估计Grenander estimator · Monotone density maximum likelihood · 递减密度的最小凹上界估计在已知半直线支持上，以样本间距加权合并构造唯一递减密度MLE，证明它是经验CDF最小凹上界的左斜率，并交出完整似然证书与端点边界。与凸函数的平方损失拟合理路有限设计的凸最小二乘回归Convex least squares regression · Multivariate convex regression · 凸回归的有限证书将凸函数类上的加权平方拟合精确化为逐对支撑平面约束，证明拟合值唯一、交付全局乘子证书，并区分非等距斜率约束、未见点延拓与统计风险。，再完成下面四项任务。你要交付的是别人能逐项复核的数值和不等式，不只是软件说“优化成功”。

标准库精确程序使用整数和有理数；一份运行结果列出样例与测试分类。下载程序后，在同一个目录执行：

python foundations-shape-constraints-check.py --output normal.json
python -O foundations-shape-constraints-check.py --output optimized.json
cmp normal.json optimized.json

两个输出文件刻意使用不同名字，避免第二次运行覆盖第一次结果。cmp无输出且退出码为零才说明这两份字节相同。程序用显式异常检查，不依赖会被-O删掉的assert。凸回归部分枚举小实例的活跃约束和Jensen基本解，计算量可随样本数指数增长；它是一份可读的证书参考，不是大型数据优化器。

两种枚举为什么完整？平方损失最优点的负梯度属于活跃约束法向量生成的锥；一份非负表示可以不断去掉线性依赖，直到只剩线性无关的活跃法向量，数量不超过拟合高度的维数。所以程序遍历这些小子集并求解其Gram方程，会找到一份有效乘子证书。另一方面，Jensen凸组合多面体的每个顶点只需仿射无关的输入，支持大小至多$d+1$；程序也枚举所有更小的支持，因此输入共线等退化情况不会被跳过。

任务一：频数和间距都不能丢 ​

在已知支撑半直线$[0,\mathrm{\infty })$上，八个观测整理为位置与频数

要求输出原始间隔高度、每次合并、最终密度、各位置的积分值，以及证明全局似然最优的一组乘子。密度取正点左连续版本，故每个区间右端包含在该区间内。

相邻间距为$\mathrm{\Delta }=(1,1,2,1)$，经验质量为$p=(1/8,3/8,1/8,3/8)$，原始高度是

第一、二段违反递减顺序，合并成质量$1/2$、长度$2$、高度$1/4$的块。第三、四段合并成质量$1/2$、长度$3$、高度$1/6$的块。两个块的高度已经递减，于是

归一化检查是$2/4+3/6=1$。积分到四个观测位置，得到

上包络在两个块的终点$2,5$碰到经验CDF，在块内则可以严格高于它。这里没有置信概率承诺。

接下来计算

检查每个${\eta }_k\ge 0$、最后一个为零，以及${\eta }_k({\hat{q}}_k-{\hat{q}}_{k+1})=0$。对任何另一份满足$\sum {\mathrm{\Delta }}_j{q}_j=1$的正递减高度，必须自己写出这条证书：

它比较的是所有可行竞争者，不只本程序枚举到的分割。若竞争者某个样本高度为零，其似然为零，直接输给这里的正似然。完整密度的有限化论证则由前置正文保证。

任务二：资料改变后，旧证书不再自动有效 ​

保留位置，把频数改成$(1,1,1,5)$。要求重算块与乘子，再判断以下两种数据变换能否沿用答案。

原始高度变为$(1/8,1/8,1/16,5/8)$。最后两段先合并为$1/4$，这个高度又超过前面的$1/8$；继续向左合并，最终四段同属一个块：

请把它代回任务一的三项乘子检查。旧答案$(1/4,1/4,1/6,1/6)$虽然仍是合法密度，却不再拥有新资料的最优性证书。程序分别计算两份资料，没有缓存旧分块。

• 若所有位置乘以$3$，而频数不变，块成员不变，长度乘以$3$，密度高度除以$3$。原资料的两块高度变为$1/12,1/18$；变更频数后的统一高度变为$1/15$。积分质量不变，所有候选的未归一化样本对数似然共同减去$n\log 3$；正文使用的平均对数似然$\ell$则减去$\log 3$。
• 若擅自把每个位置减去样本最小值$1$，支撑原点随资料改变，而且会出现零观测。这不是上面的尺度等变性，不能把“递减到已知原点”的模型原封不动搬过去。

为什么零观测尤其不同？取任意处处正、递减、归一化的密度$g$，例如$g(x)=e^{-x}$。对足够小的$\epsilon >0$，定义

它仍是递减归一化密度，正点取左连续版本。零处高度至少$1/(2\epsilon )$，其余固定正观测的高度最终是$g(x)/2>0$。有零观测时，有限似然可随$\epsilon \downarrow 0$任意增大，所以不存在有限似然最大值。若允许$f(0)=+\mathrm{\infty }$并把似然也解释为扩展实数，不能再把这句话改成“连扩展无穷的最大值也不存在”；这正是程序拒绝非正样本位置的原因。

任务三：原始斜率池化会优化错目标 ​

输入、响应、权重分别是

要求求出最小化$\frac{1}{2}\sum _i{w}_i({\theta }_i-y_i{)}^2$的凸拟合、唯一斜率约束的乘子，并给逐对次梯度版本的证书。

两段斜率递增等价于

记$W=\mathrm{diag}(1,2,1)$。原始响应违反约束，因为$a^{\mathsf{T}}y=6$。最优点落在边界，驻点方程给

因此

两段斜率都为$-4/19$，所以一条可选延拓是$\hat{f}(x)=24/19-4x/19$。逐对约束取三个${\zeta }_i=-4/19$，所有$g_{ij}$均为零；只给${\lambda }_{21}=24/19$、${\lambda }_{23}=12/19$，其余为零。现在核验高度驻点：残差加权后为$(24,-36,12)/19$，正好由入流、出流抵消。第二点的斜率驻点也成立：

反过来，若先对原始相邻斜率$(2,-1)$按间隔权重$(1,2)$做递增池化，会得到零斜率。再挑最好的常数截距，结果为加权均值$1$，损失为

这不是块合并实现不够精细，而是响应平方损失在斜率坐标中相互耦合，不能直接拿独立斜率平方损失代替它。你应交付这两个严格不同的目标值，不能只展示两条“看起来都凸”的线。

再做一个资料整理检查：输入$(0,0,1,1,3)$、响应$(0,2,1,3,0)$、权重$(1,3,2,2,1)$应聚合成三个位置，权重$(4,4,1)$、响应$(3/2,2,0)$。原目标等于聚合目标加常数$7/2$。程序核验这个恒等式，而不是把重复位置当成五个可取不同高度的输入。

任务四：二维证书不等于唯一预测函数 ​

取四个角点和中心，顺序固定为

等权响应为$(0,0,0,0,2)$。要求检查全部20条非平凡有向约束，并报告损失。

候选拟合为${\hat{\theta }}_i=2/5$，次梯度全部取零。于是20条约束全部取等号。只设置从中心指向角点的四个乘子

其余乘子为零。每个角点的高度残差为$2/5$，与入流抵消；中心残差为$-8/5$，与四份出流抵消。中心指向四角的位移之和为零，故两维斜率驻点也成立，其他点没有出流。目标值是

这是一份全局最优证书；拟合值唯一来自严格凸的平方损失，不来自乘子的唯一性。

现在删去中心观测，只保留四个角点的零响应。训练拟合唯一为零，但以下两个全平面凸函数都完全拟合它：

在中心，二者分别取$0$和$-1/2$。按上述角点顺序，$f_1$可使用的支撑斜率为$(-1,0),(0,-1),(0,1),(1,0)$；全部乘子取零就给出零训练损失证书。对任意$M>0$换成$M{f}_1$，中心值可降到$-M/2$。因此连凸包内部的新点预测也没有由训练高度唯一确定。

如果明确选择“所有训练高度凸组合中的最小值”作为上包络约定，那么正方形内的最大凸插值函数恰为零；这是一个额外延拓选择。查询$(2,2)$时没有四角的凸组合表示，程序返回None，要求调用者拒绝这项上包络预测。你也可以另选一个全空间最大仿射延拓，但必须把这个规则说清楚，不能把凸包外的$+\mathrm{\infty }$冒充有限回归预测。

程序还测试只有一个输入、二维共线设计、零或负权、重复位置未聚合、浮点误入精确接口，以及错误约束方向和被清空乘子的失效。全部结论是有限资料的优化与插值结论；样本外风险仍需要额外统计假设和论证。