3.3 无约束优化的最优性条件与梯度法

3.2 节建立了凸性的判定工具，本节开始使用它们。无约束问题是最简单的一类：可行域是整个 ${\text{R}}^n$，约束不再出现，唯一需要处理的是目标函数的形状。算法主线从最优性条件开始，经过步长的确定，落到梯度法这个最基本的迭代格式上。

本节回答四个问题。怎么判断一个点是极小点（最优性条件）；沿着什么方向走（下降方向与线搜索）；走多快、多少次能到（收敛速率与条件数）；梯度本身怎么算（有限差分与自动微分）。四个问题是所有一阶方法的共同框架：3.4 节的各种加速与随机变体改变的是方向或步长的取法，分析工具与本节相同；3.5 节的二阶方法把方向换成牛顿方向，条件数的影响被进一步削弱；3.7 节的近端方法处理目标函数不可微的情形，最优性条件换成次微分形式。

3.3.1 最优性条件

一阶与二阶必要条件

考虑无约束问题 $\underset{\mathbf{x}}{min}f(\mathbf{x})$，$f$ 在定义域内二阶连续可微。若 ${\mathbf{x}}^{\ast }$ 是局部极小点（存在邻域使 $f(\mathbf{x})\ge f({\mathbf{x}}^{\ast })$），则

$$\mathrm{\nabla }f({\mathbf{x}}^{\ast })=\mathbf{0},{\mathrm{\nabla }}^{2}f({\mathbf{x}}^{\ast })⪰\mathbf{0}$$

第一条是一阶必要条件：若梯度不为零，沿 $-\mathrm{\nabla }f({\mathbf{x}}^{\ast })$ 方向作微小移动就能降低函数值（泰勒展开的一阶项为负），与局部极小矛盾。第二条是二阶必要条件：若 Hessian 有负特征值，沿对应特征向量方向移动时二阶项为负，同样能降低函数值。满足 $\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$ 的点称为驻点（stationary point），驻点包括极小点、极大点与鞍点。

两个条件都是必要的，单独都充分。二阶条件加强为严格正定时得到充分条件。

定理（二阶充分条件）：若 $\mathrm{\nabla }f({\mathbf{x}}^{\ast })=\mathbf{0}$ 且 ${\mathrm{\nabla }}^{2}f({\mathbf{x}}^{\ast })\succ \mathbf{0}$，则 ${\mathbf{x}}^{\ast }$ 是严格局部极小点。

证明用泰勒展开：在 ${\mathbf{x}}^{\ast }$ 附近，$f({\mathbf{x}}^{\ast }+\mathbf{p})=f({\mathbf{x}}^{\ast })+\frac{1}{2}{\mathbf{p}}^T{\mathrm{\nabla }}^{2}f({\mathbf{x}}^{\ast })\mathbf{p}+o(\parallel \mathbf{p}{\parallel }^2)$，一阶项为零，二阶项为正（由正定性与 $\mathbf{p}\ne \mathbf{0}$），高阶项相对二阶项可以忽略，因此邻域内函数值严格大于 $f({\mathbf{x}}^{\ast })$。

凸情形

$f$ 凸时一阶条件变为充分条件。由 3.2 节的一阶条件，对任意 $\mathbf{y}$，

$$f(\mathbf{y})\ge f({\mathbf{x}}^{\ast })+\mathrm{\nabla }f({\mathbf{x}}^{\ast }{)}^T(\mathbf{y}-{\mathbf{x}}^{\ast })=f({\mathbf{x}}^{\ast })$$

因此 $\mathrm{\nabla }f({\mathbf{x}}^{\ast })=\mathbf{0}$ 意味着 ${\mathbf{x}}^{\ast }$ 是全局极小点。凸且严格凸时极小点唯一；凸但不严格凸时极小点可以构成一个凸集（例如 $f(x_1,x_2)=x_1^2$ 的极小点集是整条 $x_1=0$ 直线）。

这一结论是凸优化的核心：不需要二阶信息，不需要检查曲率，找到一个驻点就完成了全部工作。算法设计因此可以聚焦于如何高效地把梯度推向零，而不必担心陷入错误的驻点。

非凸情形没有这一保证。驻点可能是极小点、极大点或鞍点，二阶条件只能区分局部形状，不能给出全局结论。鞍点的识别与逃逸是 3.8 节的主题，那里的判据用到 Hessian 的负特征值（负曲率方向）。

非光滑情形

目标函数不可微时，梯度不存在，条件改用次微分表述。$f$ 凸时，

$$\mathbf{0}\in \partial f({\mathbf{x}}^{\ast })$$

是 ${\mathbf{x}}^{\ast }$ 为全局极小点的充要条件。以 $f(x)=|x|$ 为例，$\partial f(0)=[-1,1]$ 包含零，因此 $x=0$ 是最小点；$x\ne 0$ 处次微分为 $\{\mathrm{sign}(x)\}$，不含零。对非凸非光滑函数，次微分需要换成 Clarke 次微分（3.7 节），条件的必要性保留，充分性依赖正则性。

3.3.2 线搜索

下降方向

迭代算法的通用格式是

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k+{\eta }_k{\mathbf{d}}_k$$

${\mathbf{d}}_k$ 是方向，${\eta }_k>0$ 是步长。方向称为下降方向，若 $\mathrm{\nabla }f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k<0$：由方向导数的定义，沿该方向作微小移动会降低函数值。负梯度方向 $-\mathrm{\nabla }f({\mathbf{x}}_k)$ 是最自然的下降方向，它在所有单位方向中给出最大的方向导数绝对值；牛顿方向 $-{\mathrm{\nabla }}^{2}f({\mathbf{x}}_k{)}^{-1}\mathrm{\nabla }f({\mathbf{x}}_k)$ 是另一个常用选择（3.5 节）。

确定步长有两条路。精确线搜索求解一维问题 $\underset{\eta >0}{min}f({\mathbf{x}}_k+\eta {\mathbf{d}}_k)$；非精确线搜索只要求步长满足若干条件，用较少的函数求值获得足够好的下降。实践中非精确方法更常用：精确线搜索的代价往往超过它带来的收益，而且远离最优点时精确的最优步长并不重要。

Armijo 条件与回溯

最基本的非精确条件是 Armijo 条件（也称充分下降条件）：

$$f({\mathbf{x}}_k+\eta {\mathbf{d}}_k)\le f({\mathbf{x}}_k)+c_1\eta \mathrm{\nabla }f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k,c_1\in (0,1)$$

右端是一条斜率被压小的直线：函数值至少要下降到这条参考线以下。常数常取 $c_1={10}^{-4}$，它容忍函数值与一阶模型之间的偏差。

回溯线搜索（backtracking）从初始步长 $\eta$（常取 ${\eta }_0=1$）出发，只要 Armijo 条件不满足就令 $\eta \leftarrow \beta \eta$（$\beta \in (0.5,1)$，常取 $0.5$ 或 $0.8$），直到条件成立。这一过程必然终止：对 $L$-光滑的函数，泰勒展开给出

$$f(\mathbf{x}+\eta \mathbf{d})\le f(\mathbf{x})+\eta \mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}+\frac{L{\eta }^2}{2}\parallel \mathbf{d}{\parallel }^2$$

只要 $\eta \le \frac{2(1-c_1)|\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}|}{L\parallel \mathbf{d}{\parallel }^2}$，右侧就不超过 Armijo 参考线，条件成立。因此回溯步长有正下界：${\eta }_k\ge min({\eta }_0,\frac{2\beta (1-c_1)|\mathrm{\nabla }f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k|}{L\parallel {\mathbf{d}}_k{\parallel }^2})$。步长不会缩到零，迭代能够持续推进，这一下界是线搜索方法全局收敛性证明的关键。

Wolfe 条件

只用 Armijo 条件可能导致步长过小：在某些方向上，很小的步长也满足充分下降，而这样的步长会拖慢后续进展。Wolfe 条件在 Armijo 之外补充一条曲率条件：

$$\mathrm{\nabla }f({\mathbf{x}}_k+\eta {\mathbf{d}}_k{)}^T{\mathbf{d}}_k\ge c_2\mathrm{\nabla }f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k,c_2\in (c_1,1)$$

含义是：新点处的方向导数相比原点处已经回升（不再那么负），说明步长已经推进到曲率开始起作用的位置，可以停止。常取 $c_2=0.9$（拟牛顿法）或 $0.1$（共轭梯度法）。两个条件合起来保证存在满足条件的步长区间，并且步长不会过小也不会过大。强 Wolfe 条件把不等式换成绝对值形式 $|\mathrm{\nabla }f({\mathbf{x}}_k+\eta {\mathbf{d}}_k{)}^T{\mathbf{d}}_k|\le c_2|\mathrm{\nabla }f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k|$，排除方向导数仍然很负的情形，拟牛顿法用它保证曲率信息的质量。

Goldstein 条件是一组更早的替代方案，用函数值的上下界同时控制步长；由于存在满足 Goldstein 条件的步长区间可能不与任何极小点相邻，现代实现更常用 Wolfe 条件。

精确线搜索的实现依赖一维插值：用两个试探点的函数值与方向导数拟合二次或三次多项式，取多项式极小点作为下一个试探点。对二次函数，三次插值可以一步定位精确步长；对一般函数，几次插值即可达到足够的精度。

3.3.3 下降引理与收敛速率

下降引理

收敛性分析从一条基本不等式开始。$f$ 为 $L$-光滑（梯度 Lipschitz 连续）时，沿线段积分并用 Lipschitz 条件放缩：

$$f(\mathbf{y})=f(\mathbf{x})+{\int }_0^1\mathrm{\nabla }f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}){)}^T(\mathbf{y}-\mathbf{x})dt\le f(\mathbf{x})+\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{L}{2}\parallel \mathbf{y}-\mathbf{x}{\parallel }^2$$

这条下降引理（descent lemma）给出函数的二次上界。取 $\mathbf{y}=\mathbf{x}-\frac{1}{L}\mathrm{\nabla }f(\mathbf{x})$（固定步长的梯度下降），代入得

$$f({\mathbf{x}}^{+})\le f(\mathbf{x})-\frac{1}{2L}\parallel \mathrm{\nabla }f(\mathbf{x}){\parallel }^2$$

每步的函数值下降量与梯度范数的平方成正比。沿极小点方向前进的量在此式中没有出现，这正是分析收敛速率时需要补上的部分：把梯度下降与最优性间隙 $f(\mathbf{x})-f({\mathbf{x}}^{\ast })$ 联系起来，需要凸性或强凸性。

三档速率

按函数的凸性强度，梯度法（固定步长 $\eta =1/L$）的收敛速率分三档。

强凸且光滑（$m$-强凸、$L$-光滑）：由强凸的二次下界可得最优性间隙夹住梯度范数，$\frac{1}{2L}\parallel \mathrm{\nabla }f(\mathbf{x}){\parallel }^2\le f(\mathbf{x})-f({\mathbf{x}}^{\ast })\le \frac{1}{2m}\parallel \mathrm{\nabla }f(\mathbf{x}){\parallel }^2$。结合下降引理

$$f({\mathbf{x}}^{+})-f({\mathbf{x}}^{\ast })\le f(\mathbf{x})-f({\mathbf{x}}^{\ast })-\frac{1}{2L}\parallel \mathrm{\nabla }f(\mathbf{x}){\parallel }^2\le (1-\frac{m}{L})(f(\mathbf{x})-f({\mathbf{x}}^{\ast }))$$

每步把最优性间隙乘以 $1-m/L$，这是线性收敛。达到精度 $ϵ$ 的迭代次数约为

$$k\approx \frac{L}{m}\log \frac{f({\mathbf{x}}_0)-f({\mathbf{x}}^{\ast })}{ϵ}=\kappa \log \frac{1}{ϵ}$$

其中 $\kappa =L/m$ 是 3.2 节的条件数。线性收敛的实现依赖两个常数：$m=0$ 时上述因子等于 $1$，结论退化。

凸且光滑：只有凸性时不能写出上述因子，收敛速率为

$$f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })\le \frac{2L\parallel {\mathbf{x}}_0-{\mathbf{x}}^{\ast }{\parallel }^2}{k+4}$$

即 $O(1/k)$ 的次线性收敛（Nesterov 的标准结论，证明用估计序列技巧，见 3.4 节的加速方法）。达到精度 $ϵ$ 需要 $O(1/ϵ)$ 次迭代，比强凸情形差得多：精度每提高一位，迭代次数按十倍增长。

非凸且光滑：没有全局最优的保证，可保证的目标是梯度范数趋于零：

$$\underset{0\le i\le k}{min}\parallel \mathrm{\nabla }f({\mathbf{x}}_i){\parallel }^2\le \frac{2L(f({\mathbf{x}}_0)-f({\mathbf{x}}^{\ast }))}{k}$$

这是 $O(1/k)$ 的次线性收敛（Nesterov 的标准结论）。含义是把最优点替换为下界 $f({\mathbf{x}}^{\ast })$ 后同样的分析成立，结论是某个迭代点的梯度足够小，即靠近驻点。

三档速率放在一起，可以看到条件数在其中的地位：强凸情形的最优速率由 $\kappa$ 决定，$\kappa$ 大时慢得可观。加速方法（3.4 节）把 $\kappa$ 依赖改为 $\sqrt{\kappa }$，二阶方法（3.5 节）进一步削弱依赖，而预条件与自适应方法通过改善问题的条件数起作用。

步长与条件数的数值验证

二次函数上的梯度下降可以精确计算，是检验上述速率的理想对象。对 $f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{Q}\mathbf{x}$，梯度下降的更新为 $\mathbf{x}\leftarrow (\mathbf{I}-\eta \mathbf{Q})\mathbf{x}$，每个特征方向独立地按因子 $1-\eta {\lambda }_i$ 收缩。两种步长给出不同的收缩因子。

import numpy as np

# 强凸二次函数：对角矩阵，条件数 25
Q = np.diag([1.0, 25.0])
L, m = 25.0, 1.0
kappa = L / m

def run(eta, k=400):
    x = np.array([1.0, 1.0])
    hist = []
    for _ in range(k):
        hist.append(float(x @ x))          # 记录到原点的平方距离
        x = x - eta * (Q @ x)
    return np.array(hist)

h1, h2 = run(1 / L), run(2 / (L + m))
print(f"kappa = {kappa:.0f}")
print(f"步长 1/L：平方距离收缩因子 = {h1[21] / h1[20]:.6f}（理论 (1 - m/L)^2 = {(1 - m / L) ** 2:.6f}）")
print(f"最优步长 2/(L+m)：收缩因子 = {h2[21] / h2[20]:.6f}（理论 ((kappa-1)/(kappa+1))^2 = {((kappa - 1) / (kappa + 1)) ** 2:.6f}）")
for name, h in [("1/L", h1), ("2/(L+m)", h2)]:
    print(f"  步长 {name}：平方距离降到 1e-6 的步数 = {int(np.argmax(h <= 1e-6))}")

# 条件数 1e4 的问题：慢方向主导迭代次数
Q2 = np.diag([1e-4, 1.0])
x = np.array([1.0, 1.0])
hist = []
for _ in range(100000):
    hist.append(float(x @ x))
    x = x - 1.0 * (Q2 @ x)
hist = np.array(hist)
print(f"\nkappa = 1e4：平方距离收缩因子 = {hist[100] / hist[99]:.8f}，"
      f"降到 1e-6 的步数 = {int(np.argmax(hist <= 1e-6))}")

# 变量缩放 x1 = 100 z1 后，问题变为 0.5 (z1^2 + z2^2)，条件数为 1
z = np.array([1.0, 1.0])
for k in range(1, 101):
    z = z - 1.0 * z                        # 缩放后一步把两个方向同时归零
    if z @ z <= 1e-6:
        break
print(f"缩放后：平方距离降到 1e-6 的步数 = {k}，z = {z}")
# 步长 1/L 的收缩因子为 0.9216，最优步长把两个方向同步按 0.8521 收缩
# 条件数 1e4 时需要约 7 万步，变量缩放把条件数降到 1 后一步收敛

输出给出四个数字。步长 $1/L$ 时平方距离每步按 $0.9216$ 收缩，与 $(1-m/L{)}^2$ 完全一致（距离每步乘 $1-m/L$，平方再乘一次）；最优步长 $2/(L+m)$ 使两个特征方向同步按 $((\kappa -1)/(\kappa +1){)}^2$ 收缩，实测 $0.8521$，步数从 $170$ 降到 $91$。条件数 ${10}^4$ 的例子里收缩因子为 $0.9998$，降到 ${10}^{-6}$ 需要约 $6.9\times {10}^4$ 步，与 $\frac{\kappa }{2}\log \frac{1}{ϵ}$ 的估算同量级；同一个问题在缩放后的坐标下条件数为 $1$，一步收敛。这组对比是本节最实用的结论：迭代次数由条件数决定，改善条件数（缩放、预条件、自适应步长）的收益往往是数量级的。

3.3.4 梯度的计算

有限差分

目标函数的解析梯度并非总能写出，退一步可以用差分近似。前向差分与中心差分为

$$\frac{\partial f}{\partial x_i}\approx \frac{f(\mathbf{x}+h{\mathbf{e}}_i)-f(\mathbf{x})}{h},\frac{\partial f}{\partial x_i}\approx \frac{f(\mathbf{x}+h{\mathbf{e}}_i)-f(\mathbf{x}-h{\mathbf{e}}_i)}{2h}$$

误差由两部分组成：截断误差（前向 $O(h)$，中心 $O(h^2)$）与舍入误差（约为 ${ϵ}_{\text{mach}}/h$，来自两个相近函数值的相减）。两部分叠加给出最优步长：前向差分约 $\sqrt{{ϵ}_{\text{mach}}}\approx {10}^{-8}$，中心差分约 ${ϵ}_{\text{mach}}^{1/3}\approx 6\times {10}^{-6}$，对应的最小误差分别为 ${10}^{-8}$ 与 ${10}^{-11}$ 量级。计算代价上一目了然：中心差分对每个坐标需要两次函数求值，$n$ 维问题需要 $2n$ 次。

有限差分适合作为开发期的检查手段（梯度检查），不适合作为训练时的梯度来源：代价随维数线性增长，精度也受限。

自动微分

自动微分（automatic differentiation）在计算过程中精确地传播导数，不引入截断误差。两种模式。

前向模式沿计算顺序同时计算函数值与方向导数。实现方式是为每个数与一个导数分量组成对偶数（dual number）$a+bϵ$（约定 ${ϵ}^2=0$），所有算术运算按这一规则进行：$(a+bϵ)(c+dϵ)=ac+(ad+bc)ϵ$，$\exp (a+bϵ)=e^a(1+bϵ)$，等等。一次前向传播给出一个方向的方向导数，计算代价约为一次函数求值的常数倍。要求整个梯度需要 $n$ 次前向传播，代价随维数线性增长。

反向模式先做一次前向传播记录计算图，再从输出反向传播伴随量（adjoint），一次反向传播给出全部 $n$ 个偏导数，代价约为一次函数求值的几倍，与维数无关。深度学习中的反向传播就是反向模式自动微分，这一复杂度优势是神经网络训练可行的原因之一：参数维度 $n$ 可以到 ${10}^9$，代价仍然只与一次前向相当。

两种模式的选择由输入输出维数决定：求 $f:{\text{R}}^n\to \text{R}$ 的梯度时反向模式最优（输出维度低）；求 $\text{R}\to {\text{R}}^m$ 的导数时前向模式最优。雅可比矩阵的完整计算通常用反向模式的 $m$ 次调用完成。

下列代码用对偶数实现前向模式自动微分，与解析梯度对比，并给出中心差分的误差随步长的变化。

import numpy as np

class Dual:
    """前向模式自动微分的对偶数：值 + 导数"""
    def __init__(self, v, dv=0.0):
        self.v, self.dv = float(v), float(dv)
    def __add__(self, o):
        o = o if isinstance(o, Dual) else Dual(o)
        return Dual(self.v + o.v, self.dv + o.dv)
    def __mul__(self, o):
        o = o if isinstance(o, Dual) else Dual(o)
        return Dual(self.v * o.v, self.dv * o.v + self.v * o.dv)
    def __neg__(self):
        return Dual(-self.v, -self.dv)
    def __sub__(self, o):
        return self + (-o)
    def exp(self):
        e = np.exp(self.v)
        return Dual(e, e * self.dv)
    def log(self):
        return Dual(np.log(self.v), self.dv / self.v)

def f_dual(t):
    """f(t) = log(1 + exp(2t)) + t^3 / 3"""
    return (Dual(1.0) + (Dual(2.0) * t).exp()).log() + t * t * t / 3

def f_val(t): return np.log(1 + np.exp(2 * t)) + t ** 3 / 3
def f_der(t): return 2 / (1 + np.exp(-2 * t)) + t ** 2

t0 = 0.7
val = f_dual(Dual(t0, 1.0))
print(f"对偶数：f = {val.v:.8f}，f' = {val.dv:.8f}")
print(f"解析值：f = {f_val(t0):.8f}，f' = {f_der(t0):.8f}")

print("\n中心差分误差：")
for h in [1e-2, 1e-4, 1e-5, 1e-6, 1e-7, 1e-8]:
    err = abs((f_val(t0 + h) - f_val(t0 - h)) / (2 * h) - f_der(t0))
    print(f"  h = {h:.0e}: 绝对误差 = {err:.3e}")
# 对偶数给出的导数是精确的（与解析值逐位相同）
# 中心差分误差在 h = 1e-5 附近最小（约 1e-11），两侧分别由截断误差与舍入误差主导

输出验证两点。对偶数与解析梯度的数值逐位一致，说明前向模式自动微分在机器精度内精确；中心差分的误差在 $h={10}^{-5}$ 附近最小（$1.1\times {10}^{-11}$），$h$ 更大时截断误差上升，$h$ 更小时舍入误差上升，两段趋势与理论分析一致。

3.3.5 本节小结

条件、步长、速率与梯度

本节给出无约束优化的一阶方法框架。最优性条件方面，一阶必要条件 $\mathrm{\nabla }f=\mathbf{0}$ 与二阶必要条件 ${\mathrm{\nabla }}^{2}f⪰\mathbf{0}$ 刻画驻点与曲率，$f$ 凸时一阶条件变成全局最优的充要条件，非光滑时改用 $\mathbf{0}\in \partial f$。线搜索方面，Armijo 条件保证充分下降，回溯步长由 $L$-光滑性保证了正下界，Wolfe 条件额外控制步长不过小并保证曲率信息可用。收敛速率方面，下降引理给出每步至少下降 $\parallel \mathrm{\nabla }f{\parallel }^2/(2L)$，配合凸性强度得到三档结论：强凸光滑时线性收敛，迭代次数约为 $\kappa \log (1/ϵ)$；凸光滑时 $O(1/k)$；非凸光滑时梯度范数最优点 $O(1/k)$。数值验证确认了二次函数上的收缩因子公式，并展示了条件数与变量缩放对迭代次数的决定作用。梯度的计算方面，中心差分的精度受截断与舍入的权衡限制在 ${10}^{-11}$ 量级，自动微分给出机器精度的导数，其中反向模式的计算代价与维数无关，是深度学习中梯度计算的标准方式。

本节的分析都以每步都能看到真实梯度为前提，实际训练中梯度往往只由一小批样本估计，且问题规模巨大。下一节处理这些情形：动量与加速改善条件数依赖，随机梯度把每次迭代的代价降到与样本量无关，方差缩减与自适应步长处理噪声与尺度问题，本地 SGD 与联邦学习处理分布式场景。

练习题

第 1 题 概念推导

$f$ 二阶连续可微，${\mathbf{x}}^{\ast }$ 满足 $\mathrm{\nabla }f({\mathbf{x}}^{\ast })=\mathbf{0}$ 且 ${\mathrm{\nabla }}^{2}f({\mathbf{x}}^{\ast })$ 有负特征值。证明 ${\mathbf{x}}^{\ast }$ 不是局部极小点；再说明当 ${\mathrm{\nabla }}^{2}f({\mathbf{x}}^{\ast })⪰0$ 但存在零特征值时，二阶条件为什么无法单独给出结论，并以 $f_1(x)=x^3$、$f_2(x)=x^4$、$f_3(x)=-x^4$ 三个例子说明三种可能性。

参考答案

负特征值情形：设 $\mathbf{v}$ 是单位负特征向量，对应特征值 $\lambda <0$。取 $\mathbf{x}={\mathbf{x}}^{\ast }+t\mathbf{v}$，泰勒展开

$$f(\mathbf{x})-f({\mathbf{x}}^{\ast })=\frac{t^2}{2}{\mathbf{v}}^T{\mathrm{\nabla }}^{2}f({\mathbf{x}}^{\ast })\mathbf{v}+o(t^2)=\frac{\lambda t^2}{2}+o(t^2)$$

当 $t$ 足够小时，$o(t^2)$ 不超过 $|\lambda |t^2/4$，因此差值为负，$f(\mathbf{x})<f({\mathbf{x}}^{\ast })$，${\mathbf{x}}^{\ast }$ 不是局部极小点。这类点称为鞍点，负特征向量方向称为负曲率方向（3.8 节用它设计逃逸算法）。

零特征值情形：$f=\pm x^4$ 与 $f=x^3$ 在 $x^{\ast }=0$ 处的二阶导数都为零，二阶条件不能区分。逐个检查：

$f_1(x)=x^3$：$x<0$ 时 $f_1<0=f_1(0)$，$x>0$ 时 $f_1>0$，因此 $0$ 既不是极小点也不是极大点，是拐点（一种退化的鞍点）。按一阶条件它是驻点，二阶信息的缺失只能靠更高阶导数补救：三阶导数非零说明函数在两侧变号。

$f_2(x)=x^4$：$x\ne 0$ 时 $f_2>0=f_2(0)$，$0$ 是严格局部极小点，而且是全局极小点。四阶导数在零处为正。

$f_3(x)=-x^4$：$x\ne 0$ 时 $f_3<0=f_3(0)$，$0$ 是严格局部极大点。

结论：二阶条件在 Hessian 满秩时是判别工具（正定给出极小，有负特征值排除极小），在出现零特征值时失效。数值算法处理这一退化时通常加入微小扰动或利用高阶信息（三次正则化是 3.8 节的应对手段之一）。

第 2 题 计算推理

$f(x_1,x_2)=\frac{1}{2}(x_1^2+100x_2^2)-x_1$。求极小点与最优值；写出 $L$、$m$、$\kappa$ 与步长 $1/L$ 下梯度法的收敛因子；计算使最优性间隙降到 ${10}^{-6}$ 的迭代次数估计；若把问题改写为变量 $z_1=x_1$，$z_2=10x_2$，说明条件数与迭代次数的变化，并解释这与牛顿法的关系。

参考答案

极小点：梯度为 $(x_1-1,100x_2)$，令其为零得 ${\mathbf{x}}^{\ast }=(1,0)$，最优值 $f({\mathbf{x}}^{\ast })=-\frac{1}{2}$。

常数与收敛因子：Hessian 为 $\mathrm{diag}(1,100)$，$L=100$，$m=1$，$\kappa =100$。步长 $\eta =1/L=0.01$ 时收敛因子为 $1-m/L=0.99$。

迭代次数：$(0.99{)}^k\le {10}^{-6}$ 给出

$$k\ge \frac{\log {10}^{-6}}{\log 0.99}=\frac{-13.816}{-0.01005}\approx 1375$$

注意初值的间隙约 $0.5$ 量级，与 ${10}^{-6}$ 的比值对数贡献了约 $13$ 的因子，其余的 $100$ 倍来自条件数（$k\approx \kappa \log (1/ϵ)$ 中的 $\kappa$ 部分）。

缩放后的变化：令 $x_2=z_2/10$，目标变为 $\frac{1}{2}(z_1^2+z_2^2)-z_1$，Hessian 为单位矩阵，$\kappa =1$，梯度下降一步到达极小点（在 $z$ 坐标下）。迭代次数从约 $1375$ 降到 $1$。

与牛顿法的关系：牛顿法用 ${\mathbf{H}}^{-1}$ 修正梯度方向，对这个二次问题一步到达极小点，效果等同于找到了正确的坐标缩放。拟牛顿法（3.5 节）在迭代中估计 ${\mathbf{H}}^{-1}$，自适应方法（3.4 节）用梯度历史近似对角缩放，两者都在逼近同一目标：把条件数变成 $1$ 附近的量。这个例子说明条件数不是问题的内在属性，它依赖坐标的选择；算法能否自动完成这一纠正，是区分方法优劣的关键维度。

第 3 题 代码验证

用数值实验检验本节的三个结论。取一维非对称双井函数

$$f(x)=\frac{1}{4}{x}^4-\frac{1}{2}{x}^2+0.35x$$

在区间 $[-1.6,1.6]$ 上二阶导数的上界为 $6.68$，取 $L=11$（保守上界）与步长 $1/L$。检验三件事：其一，下降引理的结论 $f(x^{+})\le f(x)-\parallel \mathrm{\nabla }f(x){\parallel }^2/(2L)$ 是否每步成立；其二，非凸情形的界 $\underset{i\le k}{min}\parallel \mathrm{\nabla }f(x_i){\parallel }^2\le 2L(f(x_0)-f^{\ast })/k$（$f^{\ast }$ 取全局最小值）是否成立、松紧程度如何；其三，从两个不同初值出发的结果是否相同，说明这对非凸问题的含义。给出代码、输出与结论。

参考答案

import numpy as np

def f(x): return 0.25 * x ** 4 - 0.5 * x ** 2 + 0.35 * x
def g(x): return x ** 3 - x + 0.35

L, eta = 11.0, 1 / 11
rp = np.sort(np.roots([1, 0, -1, 0.35]).real)
print("临界点：", np.round(rp, 6))
print("对应函数值：", [round(float(f(r)), 6) for r in rp])

f_star = float(f(rp[0]))                    # 全局最小值
for x0 in [-1.6, 1.6]:
    x, best, viol = x0, np.inf, 0
    for k in range(1, 4001):
        grad = g(x)
        best = min(best, grad * grad)
        if f(x - grad / L) > f(x) - grad ** 2 / (2 * L) + 1e-12:   # 下降引理
            viol += 1
        x = x - eta * grad
    print(f"x0 = {x0:+.1f}：收敛到 x = {x:.6f}，f = {f(x):.6f}，下降引理违背 {viol} 次")
    print(f"    min grad^2 = {best:.3e}，界 2L(f(x0)-f*)/k 在 k = 100 处 = {2 * L * (f(x0) - f_star) / 100:.4f}")

输出：

临界点： [-1.142907  0.428896  0.714011]
对应函数值： [-0.626572, 0.066597, 0.059975]
x0 = -1.6：收敛到 x = -1.142907，f = -0.626572，下降引理违背 0 次
    min grad^2 = 6.040e-31，界 2L(f(x0)-f*)/k 在 k = 100 处 = 0.0935
x0 = +1.6：收敛到 x = 0.714011，f = 0.059975，下降引理违背 0 次
    min grad^2 = 3.729e-31，界 2L(f(x0)-f*)/k 在 k = 100 处 = 0.3399

结论：函数有三个临界点，中间一个是局部最大点（$f=0.066597$），两侧是局部极小点，其中左侧点是全局最小点（$f=-0.626572$）。

其一，下降引理从两个初值出发的 $4000$ 步中零违背，与定理一致。检验中使用的 $L=11$ 大于区间内二阶导数的上界 $6.68$，界更松但依然成立，说明引理对 $L$ 的取值是单调的：任何不小于真实 Lipschitz 常数的 $L$ 都能用。

其二，界在 $k=100$ 处给出 $0.0935$ 与 $0.3399$，而实测的 $min\parallel \mathrm{\nabla }f{\parallel }^2$ 在 ${10}^{-31}$ 量级（机器精度内的零），界的方向正确但非常松。原因是非凸界是最坏情形保证：它对任何光滑函数都成立，因此不能反映这个具体函数在局部极小点附近曲率转正、衰减变为线性的事实。这解释了为什么实践中非凸优化比理论界乐观：界给出的是保底，实际表现由问题结构决定（3.8 节展开这一话题）。

其三，两个初值收敛到不同的局部极小点（$x=-1.142907$ 与 $x=0.714011$，函数值相差约 $0.69$）。一维情形已经如此，高维问题中初值、批量顺序、随机种子的影响只会更大。含义有两层：非凸优化不能承诺找到全局最优，收敛结果依赖初始化；工程上因此需要多起点、随机重启或更好的初始化策略来缓解，而不是期望单一运行成功。

第 4 题 综合应用

某训练系统实现了一个通用梯度下降求解器，用户可以传入目标函数与梯度。上线后发现两类问题：其一，用户传入的梯度函数存在实现错误（数值上不对），求解器却报告收敛，停在一个错误的位置；其二，多个用户报告不同量纲的特征导致收敛极慢。请设计一个梯度检查流程，说明检查的步长、容差与判断标准；针对第二类问题给出具体的排查方法与三种可行的修复方案；并说明修复方案中哪一种最适合用户无法修改目标函数的场景。

参考答案

梯度检查流程：对随机选取的若干点与若干方向，用中心差分估计方向导数，与传入的梯度点乘结果比较：

$$\text{相对误差}=\frac{|f(\mathbf{x}+h\mathbf{v})-f(\mathbf{x}-h\mathbf{v})-2h\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{v}|}{max(|f(\mathbf{x}+h\mathbf{v})|,|f(\mathbf{x}-h\mathbf{v})|,1)}$$

步长取 $h\approx {10}^{-5}$（由 3.3.4 节的误差分析，中心差分在此附近精度最高）；容差取 ${10}^{-4}$ 量级（不是 ${10}^{-12}$：差分本身有 ${10}^{-11}$ 量级的误差，容差过严会产生大量假警报）。方向选择有两类：随机方向（覆盖面广，适合自动化）与坐标方向（定位到具体坐标的实现错误）。判断标准是相对误差超过容差的点数与方向是否集中：集中在一个坐标上说明该分量写错，遍布全部坐标说明整体缩放或符号出错。检查应使用双精度、关闭随机性、避免目标函数在检查点附近有不可微结构（若函数包含 $max$、$|x|$ 等非光滑项，选择避开折点的检查点）。

第二类问题的排查：计算或估计 Hessian 的最大与最小特征值（对小规模问题直接计算，对大规模问题用幂迭代估计谱的极端值），得到条件数 $\kappa$。若 $\kappa$ 远大于 ${10}^3$，逐一检查各特征的取值范围与相关性（条件数大通常来自量纲差异或强相关特征）。另一种更直接的排查方式是记录迭代过程中各坐标方向梯度分量的量级：量级相差多个数量级的坐标就是问题所在。

三种修复方案：其一，特征标准化（减均值除标准差）；其二，用自适应方法（Adam 类）自动调整每个坐标的有效步长；其三，用二阶信息或拟牛顿法估计曲率做预条件。

无法修改目标函数的场景：最适合的方案是第二种。标准化要求改写目标函数与梯度（因为数据被改变），拟牛顿法需要求解器内部实现并假设函数两阶可微。自适应方法（第 3.4 节）只使用梯度的历史信息，在求解器内部即可实现，用户无感知。它的原理正是本节的例子所显示的：用梯度平方的滑动平均近似每个方向的曲率，等价于学习一个对角缩放矩阵，把条件数大的问题在迭代中逐步校正。

常见错误

错误 1 · 把驻点当作极小点

原因：一阶必要条件只排除非驻点，不能排除鞍点与极大点。非凸问题中相当一部分驻点是鞍点（高维问题中这一比例更高），算法停在鞍点后报告收敛会给出错误的最优值。

解决：报告最小的同时报告二阶信息或梯度范数的变化：计算最优点处 Hessian 的最小特征值（小规模问题直接计算，大规模问题用 Hessian-向量积与幂迭代估计），若存在负特征值则说明结果不可信。非凸训练中采用带扰动的初始化或多起点策略，3.8 节给出系统的逃逸方法。

错误 2 · 线搜索只保留 Armijo 条件并用过小的初始步长

原因：只有充分下降条件时，线搜索可能返回极小的步长，迭代看起来稳定但进展极慢（方向正确而步子太小）。若初始步长又设得很小，回溯根本不会触发，问题被误解为算法效率低。

解决：初始步长取 $1$ 或前一步的步长（前后步长通常接近），并配合 Wolfe 曲率条件保证步长不过小。监控实际步长序列：若步长持续缩到 ${10}^{-8}$ 以下，说明方向或梯度有问题（方向不是下降方向、梯度实现错误、函数在附近非光滑），应先排查这些前提而不是继续调小步长。

错误 3 · 用有限差分作为大规模训练中的梯度来源

原因：中心差分对每个参数需要两次函数求值，参数规模 ${10}^9$ 时单次梯度计算需要 $2\times {10}^9$ 次前向计算，完全不可行；精度也限制在 ${10}^{-11}$ 量级。把差分当作训练梯度会带来无法承受的代价，或者迫使参数规模缩小到玩具级别。

解决：实现解析梯度或用自动微分（反向模式）。开发期用有限差分做梯度检查（3.3.4 节），训练期用自动微分。若必须使用无梯度方法（目标函数不可微或实现为黑箱），改用 3.9 节的专门方法，而不是在梯度框架里硬塞差分。

错误 4 · 把强凸的线性收敛速率套用到所有凸问题

原因：$(1-m/L{)}^k$ 的结论依赖正的强凸常数 $m$。秩亏最小二乘、含有平坦方向的问题、以及无正则的逻辑回归（数据可分时最优解不存在）都不满足强凸性，实际表现是 $O(1/k)$ 甚至更慢。按线性收敛估计迭代次数会严重低估（练习题 2 中条件数 $100$ 时估计 $1375$ 步，非强凸问题可能超出任何实际预算）。

解决：先检查强凸性：计算 Hessian 的最小特征值（或它的下界估计），为零则改用 $O(1/k)$ 的结论。工程上更常用的是加正则项制造强凸性（岭回归、权重衰减），或者接受 $O(1/k)$ 并用加速方法（3.4 节）改善常数，两者都比等待线性收敛现实。