第3章：凸函数、次梯度与共轭

上图与一阶条件

函数凸等价于上图 $\{(x,t):f(x)\le t\}$ 凸。对可微函数，在开凸域上凸性等价于

$$f(y)\ge f(x)+\nabla f(x)^T(y-x).$$

梯度给出全局仿射下界。若二阶连续可微，凸性又等价于 Hessian 在域内处处半正定。某一个点 Hessian 半正定不足以说明全局凸。

次梯度

不可微时，若向量 g 满足对所有 y 有

$$f(y)\ge f(x)+g^T(y-x),$$

则 g 是 x 处次梯度，所有这样的 g 构成 $\partial f(x)$。对 $f(x)=|x|$，正半轴次梯度为 1，负半轴为 -1，在 0 处为整个区间 $[-1,1]$。

零属于次微分，当且仅当该点为全局极小点。反向证明也直接来自定义：若 x 最优，取 g=0 就是全局下界。

保持凸性的运算

非负加权和、逐点上确界和与仿射映射复合保持凸。一般非线性复合要检查外函数单调性以及内函数凸凹性，不能看到两层都是凸就直接判断复合凸。

例如 $f(t)=t^2$、$g(x)=x^2-1$ 都凸，但 $(x^2-1)^2$ 在原点附近二阶导数为负。问题在于平方函数并非在整个实轴单调递增。

Fenchel 共轭

共轭函数定义为

$$f^*(y)=\sup_x\{y^Tx-f(x)\}.$$

它是关于 y 的仿射函数族的上确界，因此总凸。定义直接给出 Fenchel–Young 不等式 $f(x)+f^*(y)\ge y^Tx$；等号对应 $y\in\partial f(x)$。

对 $f(x)=\tfrac12\|x\|^2$，配方得最大点 x=y，所以 $f^*(y)=\tfrac12\|y\|^2$。对集合指示函数 $\delta_C$，共轭为支撑函数 $\sup_{x\in C}y^Tx$。

适当闭凸函数满足 $f^{**}=f$，闭性是该表述的重要条件。共轭把函数描述转换为全部线性支撑的描述，为对偶推导提供工具。

练习

1. 从定义求 $f(x)=|x|$ 的共轭，说明何时取 $+\infty$。
2. 验证 $x^4-2x^2+1$ 在原点附近不是凸函数。
3. 用 Fenchel–Young 等号解释梯度与共轭的关系。