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

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

梯度给出局部下降方向

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

$$f(x+d)=f(x)+\nabla f(x)^Td+o(\|d\|).$$

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

$$x^+=x-\alpha\nabla f(x)$$

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

对二次函数

$$f(x)=\frac12x^TQx-b^Tx,$$

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

步长稳定性

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

$$x_{k+1}=(1-\alpha\lambda)x_k.$$

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

Newton 用曲率改方向

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

$$m_k(d)=f(x_k)+g_k^Td+\frac12d^TH_kd,$$

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

$$H_kd_k=-g_k.$$

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

停止与解释

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

练习

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

查看解答

梯度为 $4x-8$，更新为 $x_{k+1}=x_k-\alpha(4x_k-8)$。这里曲率 ，由 得稳定范围 。

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

查看解答

二次函数的 Hessian $Q$ 恒定，梯度为 $Qx-b$。Newton 方程 $Qd=-(Qx-b)$ 给出 $x+d=Q^{-1}b=x^*$，正好满足最优性方程。

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

查看解答

非凸函数的鞍点或局部极大也可能梯度为零；此外约束问题的边界解不一定满足无约束梯度为零。需要凸性或 KKT 等额外结构才能给出更强结论。

1

对一维二次函数，步长超过稳定上界通常会发生什么？

A.一步精确到最优点B.误差振荡并放大C.Hessian 自动变正定D.约束自动出现