第6章：梯度、投影与近端方法

光滑性与下降引理

设 f 可微且梯度 L-Lipschitz，即 $\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|$ 。沿线段积分并界定梯度变化可得

f(y)\le f(x)+\nabla f(x)^T(y-x)+\frac L2\|y-x\|^2.

令 $y=x-\eta\nabla f(x)$ ，若 $0<\eta\le1/L$ ，则

f(y)\le f(x)-\frac\eta2\|\nabla f(x)\|^2.

梯度方向有下降倾向不代表任意步长都下降；步长过大可能跨过谷底并发散。

对有最优解的光滑凸函数，步长 $1/L$ 的梯度法有函数值误差 $O(1/k)$ 上界。若再有 $\mu$ 强凸性，可获得与 $1-\mu/L$ 有关的线性收敛界。

例如二次函数 Hessian 为 $\operatorname{diag}(1,100)$ ，L=100、 $\mu=1$ 。安全固定步长为 0.01，较平坦方向每步只乘 0.99，解释了条件数大时的缓慢进展。

设 $x^*$ 是最优解，取步长 $1/L$ ，记 $g_k=\nabla f(x_k)$ 。展开平方距离可得

\|x_{k+1}-x^*\|^2 =\|x_k-x^*\|^2-\frac2L g_k^T(x_k-x^*)+\frac1{L^2}\|g_k\|^2.

凸性给出 $f(x_k)-f(x^*)\le g_k^T(x_k-x^*)$ ，下降引理给出 $f(x_{k+1})\le f(x_k)-\|g_k\|^2/(2L)$ 。把两式代入，梯度范数项恰好消去：

f(x_{k+1})-f(x^*) \le\frac L2\left(\|x_k-x^*\|^2-\|x_{k+1}-x^*\|^2\right).

从第 0 步累加到第 $k-1$ 步，右侧距离项相消。由于函数值单调下降，左侧每项至少是 $f(x_k)-f(x^*)$ ，于是

f(x_k)-f(x^*)\le\frac{L\|x_0-x^*\|^2}{2k}.

这不仅说明最终趋近最优值，也说明常数取决于光滑参数和初始距离。它不要求强凸，却也没有给出强凸条件下那样的几何速度。

对闭凸约束 C，使用 $x^+=\Pi_C(x-\eta\nabla f(x))$ 。先沿负梯度移动，再找最近可行点。投影可能抵消部分移动，约束最优点因此不必满足 $\nabla f=0$ 。

固定点条件等价于 $0\in\nabla f(x)+N_C(x)$ ，把几何法锥与最优性联系起来。

若目标为光滑 f 加非光滑凸 g，定义

\operatorname{prox}_{\eta g}(v)=\arg\min_x\left\{g(x)+\frac1{2\eta}\|x-v\|^2\right\},

再令 $x^+=\operatorname{prox}_{\eta g}(x-\eta\nabla f(x))$ 。取 g 为集合指示函数就退化为投影梯度。

对 $g(x)=\lambda\|x\|_1$ ，逐坐标求解得到软阈值 $x_i=\operatorname{sign}(v_i)\max(|v_i|-\eta\lambda,0)$ 。小坐标被直接置零，说明稀疏性来自最优性条件，而不只是数值舍入。