无约束数值优化：梯度与 Newton

前面关心的是模型结构和可证明的候选。变量很多时，逐个列角点并不现实，算法需要从一个初始点出发，产生一串越来越好的迭代。这里的重点不是重新求“极值点”，而是解释一次更新为何下降、什么时候会失败、停止时能说到什么程度。

梯度给出局部下降方向

可微函数在 $x$ 附近满足

选择 $d=-\nabla f(x)$ 时，一阶项为 $-\|\nabla f(x)\|^2<0$。因此对足够小的正步长 $\alpha$，更新

会下降。注意“足够小”依赖函数的曲率；任意固定的 $\alpha$ 都不是普遍安全的。

对二次函数

其中 $Q$ 对称正定，梯度为 $Qx-b$，唯一最优点满足 $Qx^*=b$。梯度法便是在迭代地逼近这个线性方程的解。

步长稳定性

一维模型 $f(x)=\frac12\lambda x^2$ 的更新是

误差收敛需要 $|1-\alpha\lambda|<1$，也就是 $0<\alpha<2/\lambda$。步长接近上界会来回震荡；超过上界则误差放大。多维正定二次函数要同时满足所有特征值的稳定范围，最大特征值控制最严格的上限。

Newton 用曲率改方向

在 $x_k$ 处用二阶模型近似：

其中 $g_k=\nabla f(x_k)$、$H_k=\nabla^2f(x_k)$。令模型梯度 $g_k+H_kd$ 为零，得到 Newton 方向

二次正定函数的 Hessian 恒定，Newton 一步就到达解；一般函数只有在解附近 Hessian 非奇异且变化平稳时才有局部二次收敛。若 Hessian 不正定，Newton 方向可能不是下降方向，实际算法会配合阻尼或线搜索。

停止与解释

常用停止量包括 $\|\nabla f(x_k)\|$、步长 $\|x_{k+1}-x_k\|$ 和目标变化。梯度小表示一阶驻点残差小，不自动表示全局最优；若函数已知凸且可行，才可把它升级为全局结论。数值实现还要看变量尺度和线性方程求解误差。

练习

1. 对 $f(x)=\frac12(4x^2)-8x$，写出梯度法更新，并给出稳定步长范围。

2. 为什么 Newton 一步解二次正定函数？

3. 梯度范数很小但不能说明全局最优的情形是什么？