有限设计的凸最小二乘回归

有时我们不愿预先指定二次曲线，却有理由相信响应随投入呈凸形。能否直接在所有凸函数中找一条最贴近数据的曲线？看起来需要优化无穷多个函数值，实际上有限数据允许把问题压成有限个高度和支撑斜率。压缩之后，还能回答两个容易混淆的问题：训练点处的最佳高度是否唯一，以及这些高度是否已经唯一决定了新输入处的预测。

形式陈述

输入、损失和允许的函数

给定两两不同的输入 $x_1,\ldots,x_m\in\mathbb R^d$ ， $m,d\ge1$ ，响应 $y_i\in\mathbb R$ 和权重 $w_i>0$ 。我们最小化

L(f)=\frac12\sum_{i=1}^mw_i\bigl(f(x_i)-y_i\bigr)^2 \tag{1}

其中 $f:\mathbb R^d\to\mathbb R$ 为任意处处有限的凸函数。这是平方损失回归的一种形状约束，也是凸函数类上的经验风险最小化。有限优化结论对当前数据确定成立；将它解释为条件均值估计，还需另给抽样模型及“条件均值确实凸”的假设。

如果同一输入出现多次，函数不能对同一点给多个高度。先把该组权重相加、响应取加权平均。恒等式

\sum_{r\in G}w_r(t-y_r)^2 =\left(\sum_{r\in G}w_r\right)(t-\bar y_G)^2 +\sum_{r\in G}w_r(y_r-\bar y_G)^2 \tag{2}

说明聚合只减去与拟合无关的常数。以下不同输入的合同由此得到，而不是任意丢掉重复记录。

定理说：样本处的最优高度 $\widehat\theta_i=f(x_i)$ 存在且唯一，并等于下面有限二次规划的高度部分：

\begin{aligned} \min_{\theta,\zeta_1,\ldots,\zeta_m}\quad &\frac12\sum_iw_i(\theta_i-y_i)^2,\\ \text{使}\quad &\theta_i+\zeta_i^{\mathsf T}(x_j-x_i)-\theta_j\le0 \quad(i\ne j). \end{aligned} \tag{3}

每个 $\zeta_i\in\mathbb R^d$ 是点 $i$ 的候选支撑斜率。它们未必唯一；目标只对 $\theta$ 严格凸，不能从这里推出全部二次规划变量唯一。

任一可行 $(\theta,\zeta)$ 都给出全域凸延拓

f_\zeta(x)=\max_i\{\theta_i+\zeta_i^{\mathsf T}(x-x_i)\}. \tag{4}

有限个仿射函数的最大值处处有限且凸；在 $x_j$ ，全部平面不超过 $\theta_j$ ，第 $j$ 张恰好达到它。因此 $f_\zeta(x_j)=\theta_j$ 。特别地，式(3)的最优解确实恢复式(1)中的一份最优函数。

为什么这些线性不等式没有遗漏凸函数

定义对每个 $i$ 的凸组合集合

\mathcal A_i=\{\alpha\in\mathbb R^m: \alpha\ge0,\ \sum_j\alpha_j=1,\ \sum_j\alpha_jx_j=x_i\}. \tag{5}

它非空，因为可全部选第 $i$ 点。一个高度向量能由凸函数插值，当且仅当

\theta_i\le\sum_j\alpha_j\theta_j \quad\text{对所有 }i\text{ 及 }\alpha\in\mathcal A_i. \tag{6}

必要性是凸组合不等式。为证充分性，最小化 $\sum_j\alpha_j\theta_j$ 于 $\mathcal A_i$ 。单位向量给上界 $\theta_i$ ，式(6)给下界，故最优值恰为 $\theta_i$ 。这是一个非空紧可行集上的线性规划；LP强对偶给达到相同值的 $(b_i,\zeta_i)$ ，满足

b_i+\zeta_i^{\mathsf T}x_j\le\theta_j\quad\text{对所有 }j, \qquad b_i+\zeta_i^{\mathsf T}x_i=\theta_i.

消去 $b_i$ ，正好是式(3)的全部约束。再用式(4)即可完成插值。因此式(1)、式(3)和式(6)具有完全相同的可实现训练高度，不要求输入张成整个 $\mathbb R^d$ 。

由式(6)，可实现高度集合 $K$ 是闭半空间的交，故闭且凸；它包含所有仿射函数的样本值，尤其非空，并对非负倍数与相加封闭。正权重使式(3)关于高度的目标随 $\|\theta\|\to\infty$ 趋于无穷，所以在闭集 $K$ 上达到最小值。严格凸性再保证 $\widehat\theta$ 唯一。以上论证没有把“闭集的任意线性投影仍闭”当成一般真命题。

直觉

凸回归同时放置两层信息。高度说每个训练点预测多少；支撑平面说从这里往任意方向走，函数不能低于哪条仿射下界。每张平面必须通过自己的高度，并压在所有其他高度下面。若这些平面能共同存在，它们的最大值就是一张满足全部训练值的凸曲面。

这与把一个指定参数向量放进凸优化器不同：这里的统计假设是要学的函数凸。有限二次规划是实现这项假设的工具，输入维数和支撑斜率也不是原始线性回归系数。它不要求函数递增；例如 $x^2$ 在负半轴下降，仍完全凸。

非等距输入的凸回归约束比较相邻弦斜率；训练高度可以唯一，而两种合法延拓在未见点处仍给不同预测

支撑斜率为何不能只对邻近样本检查

在一般多维数据上，式(3)要求每个 $i$ 对所有 $j$ ，总共 $m(m-1)$ 条不等式。只核几个最近邻，可能放过一张在远处穿过另一个高度的平面。式(4)仍然凸，但它在那个训练点会超过声明的 $\theta_j$ ，原先计算的损失就不是返回函数的实际损失。

在式(4)自己的训练点处， $\zeta_i$ 确实是该函数的一条次梯度，因为对应平面处处在最大值下方并在那里取等。不同可行斜率给不同最大值函数，是后面非唯一延拓的来源之一。

例子与边界

一份完整的乘子证书

记

g_{ij}(\theta,\zeta) =\theta_i+\zeta_i^{\mathsf T}(x_j-x_i)-\theta_j.

对每个 $i\ne j$ 交一个乘子 $\lambda_{ij}$ 。最优性的完整条件为

g_{ij}\le0,\qquad \lambda_{ij}\ge0,\qquad \lambda_{ij}g_{ij}=0, \tag{7}

以及高度和斜率两类驻点等式

w_i(\widehat\theta_i-y_i) +\sum_{j\ne i}\lambda_{ij} -\sum_{j\ne i}\lambda_{ji}=0, \tag{8}

\sum_{j\ne i}\lambda_{ij}(x_j-x_i)=0 \quad\text{对每个 }i. \tag{9}

式(9)不能省略：斜率也是优化变量。只让高度梯度抵消，可能给出根本不属于此问题的“证书”。

这些KKT条件在这里充要。充分性可以不用记忆一般定理：对任何可行竞争对 $(\theta',\zeta')$ ，展开平方损失，并用两类驻点及互补，得到

L(\theta')-L(\widehat\theta) =\frac12\sum_iw_i(\theta'_i-\widehat\theta_i)^2 -\sum_{i\ne j}\lambda_{ij}g_{ij}(\theta',\zeta')\ge0. \tag{10}

这还再次说明高度唯一。必要性也有明确资格：不同输入允许选择

\theta_i=\|x_i\|^2,\qquad \zeta_i=2x_i, \qquad g_{ij}=-\|x_i-x_j\|^2<0.

因此式(3)严格可行，Slater条件成立；结合已证明的最优解存在，KKT乘子必存在。 $m=1$ 时没有约束，最优高度就是唯一响应。相同输入先按式(2)聚合，避免把不可能严格的重复点约束混进这项论证。

一维可以缩成相邻斜率约束

若 $x_1<\cdots<x_m$ 是实数，令 $h_i=x_{i+1}-x_i>0$ 。高度可实现当且仅当

\frac{\theta_{i+1}-\theta_i}{h_i} \le \frac{\theta_{i+2}-\theta_{i+1}}{h_{i+1}} \quad(1\le i\le m-2). \tag{11}

凸性给必要性；反向把高度连成折线，斜率非降便得到区间内凸函数，再把两端斜率线性延伸到实线。 $m=1,2$ 没有这类限制，任意高度都可插值。

取等距输入 $0,1,2$ 、响应 $(0,1,0)$ 、等权。唯一约束为 $-\theta_1+2\theta_2-\theta_3\le0$ 。令约束乘子 $\mu=1/3$ ，驻点给

\widehat\theta=(1/3,1/3,1/3),\qquad L(\widehat\theta)=1/3.

要把它核成完整式(7)–(9)，可令所有支撑斜率为零，只取 $\lambda_{21}=\lambda_{23}=1/3$ ，其余为零。中点向左右的位移相消，两个端点的残差则恰好被流入乘子抵消。

但式(11)不意味着可以对原始相邻斜率直接运行PAVA后积分。损失惩罚的是高度，多个高度共同依赖斜率与截距，斜率误差并不是独立的加权平方项。等距三点例子可能碰巧让这种做法奏效；终点中的非等距三点则给严格失败例。应解高度上的正确二次规划，不能只看斜率已排好序。

高度唯一，函数却可以在样本之间任意分开

只有两个观测 $(0,0)$ 、 $(2,0)$ 时，唯一训练高度是 $(0,0)$ ，损失为零。但两种函数

f_0(x)=0,\qquad f_M(x)=M(|x-1|-1),\quad M>0, \tag{12}

都凸且通过两点；在未见的 $x=1$ ，前者为零，后者为 $-M$ 。它们都能由式(4)实现：端点斜率分别取 $(0,0)$ 或 $(-M,M)$ 。所以即使在输入凸包内部，训练高度也不唯一决定预测，甚至不给这里的统一下界。

给定可实现高度 $\theta$ ，还可以定义一份不依赖斜率选择的函数

G_\theta(x)=\min\left\{\sum_i\alpha_i\theta_i: \alpha\ge0,\ \sum_i\alpha_i=1,\ \sum_i\alpha_ix_i=x\right\} \tag{13}

于样本凸包内。可行集紧，故最小值存在。把两个最优凸组合再混合，证明 $G_\theta$ 凸；式(6)又保证它在每个 $x_i$ 恰等于 $\theta_i$ 。任何凸插值函数都不超过任意这种凸组合值，故不超过 $G_\theta$ ：这是凸包内最大的凸插值函数。

这是一种明确的预测约定，和选定斜率的式(4)并不总相同。凸包外式(13)无可行组合，若约定值为 $+\infty$ ，就不能把它当作原来处处有限的实值预测器返回；要么拒绝外推，要么另选有限延拓。加斜率界或Lipschitz约束也可控制差异，但会改变拟合问题。

推论与应用

从投影几何得到稳定性，而不是线性帽矩阵

写加权内积 $\langle u,v\rangle_w=\sum_iw_iu_iv_i$ ，范数为 $\|u\|_w$ 。最优高度 $\widehat\theta$ 是 $y$ 到闭凸集 $K$ 的最近点。沿任意可行线段求方向导数得

\langle y-\widehat\theta,\theta-\widehat\theta\rangle_w\le0 \quad(\theta\in K). \tag{14}

对相同输入和权重的另一响应 $y'$ ，设拟合为 $\widehat\theta'$ 。将两份式(14)相加，再用Cauchy–Schwarz不等式，得到

\|\widehat\theta-\widehat\theta'\|_w^2 \le\langle\widehat\theta-\widehat\theta',y-y'\rangle_w \le\|\widehat\theta-\widehat\theta'\|_w\|y-y'\|_w.

因此拟合高度关于响应非扩张。它通常不是固定线性帽矩阵；哪些约束活跃会随响应改变。此稳定性只控制这组训练点的高度，不控制式(12)那种任意选取的未见点延拓。

仿射残差矩与验收

给任意凸函数加上任意仿射函数仍凸。沿两个符号的仿射扰动都可移动，所以最优残差满足

\sum_iw_i(\widehat\theta_i-y_i)=0, \qquad \sum_iw_i(\widehat\theta_i-y_i)x_i=0. \tag{15}

这些是很有用的算术检查，但单独不充分；很多非最优甚至非凸高度也可能满足相同矩。完整交付仍应包括原始逐对可行性、两类驻点、非负乘子和互补，或一维等价约束的同样证书。

确定性最优性也不是总体风险保证。模型形状错误、极端响应、输入覆盖稀疏和过大的外推斜率都可能影响统计效果。额外平滑、限制斜率或选择不同延拓时，应清楚记录目标类和预测规则怎样改变，再为相应程序研究泛化与不确定性，不能把式(10)当成一份无需条件的预测误差界。

参考资料

Emilio Seijo and Bodhisattva Sen，Nonparametric Least Squares Estimation of a Multivariate Convex Regression Function，2012版，§§2.1–2.3，Lemmas 2.1–2.5：凸组合/支撑平面的两种有限表示、闭凸拟合值集合及QP。本文明确加入正权重，给出完整乘子证书与非等距任务，不调用后续一致性定理。
Rahul Mazumder, Arkopal Choudhury, Garud Iyengar and Bodhisattva Sen，A Computational Framework for Multivariate Convex Regression and its Variants，2015，§1式(1)–(3)与§2开头：凸回归QP和最大仿射延拓。这里不采用其ADMM实现、性能或统计速率声明。

形式陈述 ​

输入、损失和允许的函数 ​

为什么这些线性不等式没有遗漏凸函数 ​

支撑斜率为何不能只对邻近样本检查 ​

一份完整的乘子证书 ​

一维可以缩成相邻斜率约束 ​

高度唯一，函数却可以在样本之间任意分开 ​

从投影几何得到稳定性，而不是线性帽矩阵 ​

仿射残差矩与验收 ​

反向链接