第18课|Armijo 与 Backtracking:不知道精确 L,如何安全地选步长?
2026 年 11 月 6 日|第三周·第4天|讲授约18分钟(自测另计)
上一讲研究了强凸 Nesterov 加速和周期重启,其更新通常依赖 (1/L) 这样的预设步长。但真实问题中,精确的全局梯度 Lipschitz 常数 (L) 往往难算,而且使用很保守的上界会造成步长过小。今天研究:能否通过实际检查目标函数是否充分下降来选步长,并给出严格保证?
本课三条主线:下降引理 (\to) Armijo 条件 (\to) Backtracking 有限终止;统一步长下界 (\to) 梯度范数收敛;额外强凸 (\to) 函数值几何收敛。最后解释为什么带回溯的 GD 并不会自动获得 Nesterov AGD 的加速速率。
一、问题、方向与假设
考虑无约束优化 [ \min_{x\in\mathbb R^n}f(x). ] 假设 (f) 连续可微,梯度全局 (L)-Lipschitz((L>0)): [ |\nabla f(x)-\nabla f(y)|\le L|x-y|, ] 并且 (f_{\inf}:=\inf_x f(x)>-\infty)。本节前半程不假设凸性。在第 (k) 步记 (g_k=\nabla f(x_k))。若 (g_k=0),停止并报告“驻点”(非凸情形不能直接报告“全局最优”);否则选最速下降方向 (d_k=-g_k),更新 (x_{k+1}=x_k+\alpha_kd_k)。
为什么不只检查 (f(x_{k+1})<f(x_k))?因为下降极其微弱也可能满足这个条件,无法有效分析累计进展。Armijo 要求下降量与局部一阶预测成比例。
二、Armijo 充分下降条件
给定参数 (c\in(0,1)) 与试探步长 (\alpha>0),对一般方向 (d) 要求 [ \boxed{f(x+\alpha d)\le f(x)+c\alpha\nabla f(x)^Td.}\tag{1} ] 必须选真正的下降方向:(\nabla f(x)^Td<0),否则以下终止论证不适用。对 (d=-g): [ \boxed{f(x-\alpha g)\le f(x)-c\alpha|g|^2.}\tag{2} ] 右端严格小于 (f(x))(当 (g\ne0)),因此接受的每一步确实下降。
用一阶 Taylor 近似理解:方向导数预测变化 (-\alpha|g|^2),Armijo 只要求实现其中 (c) 比例的下降;(c) 越大,条件越严格。不过这是检查条件,还没有证明候选一定存在。
三、关键推导:为什么回溯一定会结束?
(L)-Smooth 的下降引理是
[
f(y)\le f(x)+g^T(y-x)+\frac L2|y-x|^2.
]
令 (y=x-\alpha g),得
[
\begin{aligned}
f(x-\alpha g)
&\le f(x)-\alpha|g|^2+\frac{L\alpha^2}{2}|g|^2
&=f(x)-\alpha\left(1-\frac{L\alpha}{2}\right)|g|^2.
\end{aligned}\tag{3}
]
为使该上界不大于 Armijo 右端,只需
[
1-\frac{L\alpha}{2}\ge c.
]
因此当
[
\boxed{0<\alpha\le T:=\frac{2(1-c)}L}\tag{4}
]
时,Armijo 一定成立。这是充分条件,并非必要条件:某些具体点可能接受 (\alpha>T)。
注意式(4)用于理论证明,不要求实际程序知道 (L)。
3.1 Backtracking 算法
给定初始步长 (\alpha_0>0) 与缩步因子 (0<\beta<1),每轮从 (\alpha_0) 开始试探:
g = ∇f(x)
if ||g|| = 0: stop (stationary point)
α = α0
while f(x - αg) > f(x) - c α ||g||²:
α = β α
x = x - αg
因 (\alpha_0\beta^j\to0),且所有 (\alpha\le T) 都会通过,非零梯度处回溯在有限次缩步后必定终止。
更强地,接受步长满足统一下界 [ \boxed{\alpha_k\ge\underline\alpha:= \min\left{\alpha_0,\frac{2\beta(1-c)}L\right}>0.}\tag{5} ] 证明分两种情况:若初始试探 (\alpha_0\le T),直接接受 (\alpha_0);若 (\alpha_0>T),在首次接受之前的候选 (\alpha_k/\beta) 未通过,而“所有 (\alpha\le T) 必通过”,故 (\alpha_k/\beta>T),即 (\alpha_k>\beta T)。即使首次步长大于 (T) 就被接受,也不妨碍该下界成立。
重要区别: 回溯需要多次目标函数评估,但通常每轮只需在当前点计算一次梯度。它未必降低墙钟时间,取决于函数评估成本。
四、非凸情况下的严格收敛结论
式(2)及统一下界给出: [ f(x_k)-f(x_{k+1}) \ge c\alpha_k|g_k|^2 \ge c\underline\alpha|g_k|^2.\tag{6} ] 对 (k=0,\ldots,K-1) 求和: [ c\underline\alpha\sum_{k=0}^{K-1}|g_k|^2 \le f(x_0)-f(x_K) \le f(x_0)-f_{\inf}. ] 故 [ \boxed{\min_{0\le k<K}|\nabla f(x_k)|^2 \le\frac{f(x_0)-f_{\inf}}{c\underline\alpha K}.}\tag{7} ] 这给出最佳梯度平方 (O(1/K)),即找到梯度范数不超过 (\varepsilon) 的点可由 (K=O(\varepsilon^{-2})) 次迭代保证(常数保持固定)。如果无限迭代,由全部非负梯度平方项可和,还可推出 (|\nabla f(x_k)|\to0)。
没有证明 (f(x_k)\to f^*)(全局最优),也没有仅凭这些假设证明迭代点 (x_k) 必须收敛。非凸情况下,驻点可能是局部极小、局部极大或鞍点。
五、额外假设强凸:几何收敛如何得到?
进一步假设 (f) 为 (\mu)-强凸、(0<\mu\le L),最优点 (x^) 存在且唯一。强凸推出 [ |\nabla f(x)|^2\ge2\mu\big(f(x)-f^\big).\tag{8} ] 证明:由强凸 (f(y)\ge f(x)+g^T(y-x)+(\mu/2)|y-x|^2),对右侧关于 (y-x) 求最小,得到 (f^*\ge f(x)-|g|^2/(2\mu)),移项即式(8)。
将式(8)代入 Armijo 下降:
[
\begin{aligned}
f(x_{k+1})-f^*
&\le f(x_k)-f^-c\alpha_k|g_k|^2
&\le\big(1-2c\mu\underline\alpha\big)\big(f(x_k)-f^\big).
\end{aligned}
]
因此
[
\boxed{f(x_K)-f^*
\le(1-2c\mu\underline\alpha)^K[f(x_0)-f^*].}\tag{9}
]
在非平凡情形,基于前述合法常数得到的因子位于 ([0,1));若一步达到最优则迭代结束。结论是函数值几何收敛,不是说每轮回溯次数相同,更不是 AGD 的 (O(\sqrt\kappa\log(1/\varepsilon))) 加速复杂度。
对于普通凸但非强凸问题,单凭式(6)只控制梯度平方;若再假设初始下水平集内到某个最优点距离统一不超过 (R),则凸性给出 (\Delta_k=f(x_k)-f^*\le R|g_k|),进一步得到 (\Delta_{k+1}\le\Delta_k-(c\underline\alpha/R^2)\Delta_k^2),从而可推出函数值 (O(1/K))。这里的有界水平集条件不可偷偷省略。
六、手算例子:同一问题不同轮次接受不同步长
考虑 [ f(x,y)=\tfrac12(x^2+4y^2),\qquad \nabla f=(x,4y),\qquad L=4. ] 取 (x_0=(2,1)),(f(x_0)=4),(\nabla f(x_0)=(2,4)),(|g_0|^2=20)。设 [ c=\tfrac14,\quad \beta=\tfrac12,\quad\alpha_0=1. ] 每轮都重新从初始试探 (\alpha_0=1) 开始。第一轮 Armijo 上界为 (4-5\alpha)。
| 第一轮候选 (\alpha) | 更新点 | 实际 (f) | Armijo 右端 | 判定 |
|---|---|---|---|---|
| (1) | ((0,-3)) | (18) | (-1) | 拒绝 |
| (1/2) | ((1,-1)) | (5/2) | (3/2) | 拒绝 |
| (1/4) | ((3/2,0)) | (9/8) | (11/4) | 接受 |
于是 (\alpha_0^{\mathrm{accepted}}=1/4),第一个新点为 (x_1=(3/2,0)),(f(x_1)=9/8)。
第二轮 (g_1=(3/2,0)),(|g_1|^2=9/4)。重新试探 (\alpha=1):更新到 ((0,0)),函数值 (0),Armijo 右端 (9/8-(1/4)(9/4)=9/16),因此直接接受。得到 (x_2=(0,0)),达到最优。
这个例子显示:同一个全局 (L=4) 的问题,回溯第一轮选 (1/4),第二轮却可接受 (1>1/L);式(4)是充分阈值而不是步长上限。
七、失败反例与边界
反例一:步长过大。 对 (f(t)=2t^2),(L=4),取 (t=1),使用固定步长 (\alpha=1) 做 GD,得到 (t^+=1-1\cdot4=-3),而 (f(t^+)=18>2=f(t))。负梯度只在足够合适的步长下保证下降。
反例二:非下降方向不保证回溯成功。 对 (f(t)=t^2/2),在 (t=1) 取 (d=+1),有 (g^Td=1>0)。对任意 (\alpha>0),实际变化是 (\alpha+\alpha^2/2>c\alpha)((c<1)),因此 Armijo 不通过,缩到再小也不行。有限终止论证不能省略“下降方向”。
反例三:梯度为零不保证全局最优。 (f(t)=1-\cos t) 全局 (1)-Smooth 且下有界,但从 (t_0=\pi) 出发梯度是零,函数值 (2),而全局最小值为 (0)。Armijo/GD 只能报告驻点,不能声称全局最优。
与上一讲 AGD 的联系: 固定参数 AGD 的 (O(1/K^2)) 势函数证明依赖加速权重和梯度步长之间精确的抵消关系。把其中的 (1/L) 任意改成回溯接受的步长,会改变证明用的恒等式,因此不能直接继承加速保证。有专门设计的自适应加速方案,但需要新的算法和证明。
八、概念总结
| 方法 | 如何定步长 | 在明确假设下的保证 | 代价或局限 |
|---|---|---|---|
| 固定步长 GD | 预先选 (1/L) | 凸:函数值 (O(1/K));强凸:几何收敛 | 需要已知可靠 (L) 上界 |
| Armijo + Backtracking GD | 逐轮检查充分下降 | 非凸下有界:最佳梯度平方 (O(1/K));强凸:几何收敛 | 多次函数值评估;不是 AGD 加速 |
| Nesterov AGD | 特定权重与梯度步耦合 | 凸 Smooth:函数值 (O(1/K^2)) | 不能随意更改更新参数仍引用原证明 |
flowchart TD
A["L-Smooth + 负梯度方向"] --> B["下降引理"]
B --> C["Armijo:α≤2(1-c)/L 一定接受"]
C --> D["Backtracking 有限终止"]
D --> E["统一正步长下界"]
E --> F["f 下有界:最佳梯度平方 O(1/K)"]
E --> G["再加 μ-强凸:函数值几何收敛"]
H["AGD 固定势函数结构"] -. "直接替换步长不能沿用证明" .-> D
本节的三条必须记住的公式: [ \boxed{\alpha\le\frac{2(1-c)}L\ \Longrightarrow\ \text{Armijo 必通过}}, \quad \boxed{\alpha_k\ge\min{\alpha_0,2\beta(1-c)/L}}, ] [ \boxed{\min_{k<K}|\nabla f(x_k)|^2 \le\frac{f(x_0)-f_{\inf}}{c\underline\alpha K}.} ]
九、四级自测(共100分)
首次发布不展示答案和开放题评分要点。请勿提前查看独立测验 JSON,以免泄题。
Lv1|Armijo 线搜索的适用条件|15 分|预计 2 分钟|单选
设 (f) 可微且 (L)-Smooth,当前梯度 (g=\nabla f(x)\ne0),采用方向 (d=-g),Armijo 参数 (c\in(0,1)),回溯因子 (\beta\in(0,1)) 与初始试探步长 (\alpha_0>0)。下面哪项一定正确?
A. 只要 Armijo 检查通过,新的迭代点就是全局最优点。
B. 回溯线搜索将在有限次缩步后接受一个正步长;这本身不保证非凸问题的全局最优性。
C. 必须预先知道精确的最小 Lipschitz 常数 (L),才能运行回溯线搜索。
D. 即使选择方向 (d=+g),也必定能在有限次缩步后满足 Armijo 条件。
提示:分别检查:方向导数的符号、下降引理以及非凸驻点与全局最优的区别。
Lv2|Backtracking 首次接受的步长|20 分|预计 3 分钟|数值
考虑 (f(x)=2x^2),从 (x_0=1) 沿负梯度方向做 Armijo 回溯线搜索。取 (c=0.25)、初始步长 (\alpha_0=1)、回溯因子 (\beta=0.5)。依次测试 (\alpha=1,0.5,0.25,\ldots),求首次被接受的步长 (\alpha)。仅填数值,保留三位小数。
| *提示:先求 f(1)、f’(1),比较 f(1-α f’(1)) 与 f(1)-cα | f’(1) | ²。* |
Lv3|线搜索的全局收敛指标与必要假设|25 分|预计 5 分钟|单选
设 (f:\mathbb R^n\to\mathbb R) 的梯度全局 (L)-Lipschitz,(L>0),且 (f) 下有界。每一步在 (g_k\ne0) 时选 (d_k=-g_k),采用固定 (c\in(0,1),\beta\in(0,1),\alpha_0>0) 的 Armijo 回溯搜索;若梯度为零则停止。以下哪项由这些假设严格保证?
A. 每一步接受的步长一定不超过 (1/L)。
B. 即使目标非凸,迭代也一定收敛到全局最优点。
| C. 若算法持续迭代,则存在统一正步长下界,并有 (min_{0le k<K} | |
| abla f(x_k) | ^2=O(1/K));这并非全局最优值误差保证。 |
| D. 只要函数值单调下降,就能推出 ( | x_k-x^* | ) 线性收敛。 |
提示:先利用回溯终止阈值得到 α_min>0,再对 Armijo 下降量望远镜求和。
Lv4|回溯终止、收敛证明、数值执行与反例|40 分|预计 12 分钟|开放证明
考虑无约束优化 (\min_{x\in\mathbb R^n}f(x)),其中 (f) 可微、梯度全局 (L)-Lipschitz((L>0)),且函数值下有界。采用 (d_k=-\nabla f(x_k)),回溯候选 (\alpha_0,\beta\alpha_0,\beta^2\alpha_0,\ldots),其中 (c\in(0,1),\beta\in(0,1))。
A(12 分)从下降引理逐项推导 Armijo 条件 (f(x_k-\alpha g_k)\le f(x_k)-c\alpha|g_k|^2) 的一个充分步长阈值;证明当 (g_k\ne0) 时回溯有限终止,并给出被接受步长的统一正下界。
B(12 分)利用 A 的步长下界和 (f_{\inf}>-\infty),推导前 (K) 次中最佳梯度范数平方的 (O(1/K)) 上界;再额外假设 (f) 为 (\mu)-强凸,推导一个基于 Armijo 下降与 (|\nabla f(x)|^2\ge2\mu(f(x)-f^*)) 的几何收敛界。
C(10 分)对 (f(x,y)=\tfrac12(x^2+4y^2)),初值 ((2,1)),采用 (c=1/4,\beta=1/2,\alpha_0=1),每轮重新从 (\alpha_0) 回溯。逐项列出第一轮各候选是否通过,算出前两轮接受的步长及 (x_1,x_2,f(x_1),f(x_2))。
D(6 分)给一个全局 Smooth、下有界、但梯度为零的点并非全局最优的非凸反例;说明为何只给 Nesterov 动量步添加 Armijo 检查,不能直接沿用固定参数 AGD 的 (O(1/k^2)) 势函数证明。
提示:A 用 L-Smooth 的二次上界;B 对下降量求和,再用强凸的梯度主导不等式;C 要在每一轮从初始试探步长重新开始;D 区分驻点、全局最优与算法势函数。
十、下一讲与自测反馈
第19课|2026年11月7日:随机线搜索、非精确梯度与 Wolfe 条件(第三周第5天)。 下一讲将从 Armijo 的单侧充分下降转向曲率条件:为何 BFGS 等拟牛顿方法常使用 Wolfe 或 Strong Wolfe 条件,为什么仅满足充分下降不一定足够,以及如何区分精确线搜索与近似线搜索。
四道题分别为 15、20、25、40 分。作答后逐题评分:总分 80 分及以上正常继续;60–79 分补充针对性例题;低于 60 分先复习下降引理、负梯度方向和梯度范数收敛。测试结果不改变日期课号。