凹函数y(x)的g(t)=sup[y-tx]的解析证明及凸性验证

我完全懂这种图形上一眼看明白，但解析推导就是卡壳的感觉！别着急，咱们一步步把这个问题拆解开，先搞定第一个等式的证明，再验证g(t)的凸性。

一、证明g(t) = y_t - t x_t（其中y’(x_t)=t） #

首先明确前提：y(x)是可导凹函数（题目提到了dy/dx，默认可导）。凹函数有个核心支撑性质：对任意x和x_t，函数图像永远在任意一点的切线下方，也就是：

y(x) ≤ y(x_t) + y’(x_t)(x - x_t)

现在我们取x_t为满足y’(x_t)=t的点，把y’(x_t)替换成t，然后对不等式变形：
$$
y(x) ≤ y(x_t) + t(x - x_t)
$$
把右边展开后移项，得到：
$$
y(x) - t x ≤ y(x_t) + t x - t x_t - t x = y(x_t) - t x_t
$$

这就说明：对所有x，y(x)-t x的取值都不会超过y(x_t)-t x_t。而当x=x_t时，左边刚好等于右边，所以这个上确界$\sup[y(x)-t x]$就等于$y(x_t)-t x_t$，也就是$g(t)=y_t - t x_t$（这里$y_t=y(x_t)$）。

你之前尝试用凸组合不等式推导的思路其实是对的，咱们补全那个矛盾推导：假设存在某个点$x_s≠x_t$，使得$y(x_s)-t x_s > y(x_t)-t x_t$，根据凹函数的凸组合性质，对任意$\lambda∈(0,1)$，有：
$$
y(\lambda x_s + (1-\lambda)x_t) ≥ \lambda y(x_s) + (1-\lambda)y(x_t)
$$
两边减去$t(\lambda x_s + (1-\lambda)x_t)$，得到：
$$
y(\lambda x_s + (1-\lambda)x_t) - t(\lambda x_s + (1-\lambda)x_t) ≥ \lambda(y(x_s)-t x_s) + (1-\lambda)(y(x_t)-t x_t)
$$
因为假设$y(x_s)-t x_s > y(x_t)-t x_t$，右边会大于$\lambda(y(x_t)-t x_t) + (1-\lambda)(y(x_t)-t x_t) = y(x_t)-t x_t$。但当$\lambda$趋近于0时，左边的点$\lambda x_s + (1-\lambda)x_t$趋近于$x_t$，左边的极限就是$y(x_t)-t x_t$，这就产生了矛盾——一个趋近于某个值的表达式，却始终大于这个值，显然不可能。所以不存在这样的$x_s$，最大值只能在$x_t$处取到。

二、证明g(t)是凸函数 #

这个有两种直观的解析思路，咱们都理一遍：

方法一：利用上确界的凸性 #

g(t)是一族仿射函数（对每个固定的x，$y(x)-t x$是关于t的仿射函数）的上确界，而仿射函数的上确界必然是凸函数。不过咱们用定义严谨验证：

根据凸函数的定义：对任意$t_1,t_2∈ℝ$，任意$\lambda∈[0,1]$，需要证明$g(\lambda t_1 + (1-\lambda)t_2) ≤ \lambda g(t_1) + (1-\lambda)g(t_2)$。

首先展开g的表达式：
$$
g(\lambda t_1 + (1-\lambda)t_2) = \sup_x [y(x) - (\lambda t_1 + (1-\lambda)t_2)x] = \sup_x [\lambda(y(x)-t_1 x) + (1-\lambda)(y(x)-t_2 x)]
$$

对任意x，因为$y(x)-t_1 x ≤ g(t_1)$，$y(x)-t_2 x ≤ g(t_2)$，乘以非负系数$\lambda$和$1-\lambda$后相加，不等式依然成立：
$$
\lambda(y(x)-t_1 x) + (1-\lambda)(y(x)-t_2 x) ≤ \lambda g(t_1) + (1-\lambda)g(t_2)
$$

上确界是所有x对应表达式的最大值，这个最大值自然不会超过右边的$\lambda g(t_1)+(1-\lambda)g(t_2)$，也就是：
$$
g(\lambda t_1 + (1-\lambda)t_2) ≤ \lambda g(t_1) + (1-\lambda)g(t_2)
$$
满足凸函数定义，所以g(t)是凸函数。

方法二：利用导数单调性 #

我们已经知道$g(t)=y(x_t)-t x_t$，其中$y’(x_t)=t$。对t求导（用隐函数求导法则）：
$$
\frac{dg}{dt} = y’(x_t)\frac{dx_t}{dt} - x_t - t\frac{dx_t}{dt}
$$
因为$y’(x_t)=t$，代入后化简：
$$
\frac{dg}{dt} = t\frac{dx_t}{dt} - x_t - t\frac{dx_t}{dt} = -x_t
$$

因为y(x)是凹函数，它的导数$y’(x)$是单调递减的，所以$x_t$作为$t=y’(x)$的反函数，是单调递减的，那么$\frac{dg}{dt}=-x_t$就是单调递增的——导数单调递增的函数是凸函数，这也验证了g(t)的凸性。

备注：内容来源于stack exchange，提问作者ZED