第 19 课|Wolfe 条件、曲率控制与非精确线搜索

2026 年 11 月 7 日|第三周·第 5 天|讲授约 18 分钟(自测另计)

上一课证明了 Armijo 回溯线搜索:即使不知道精确的全局 Smooth 常数 (L),也可以用函数值检查,保证沿下降方向获得充分下降。

今天更进一步:函数值下降够多,是不是就代表选到了适合拟牛顿法的步长? 答案是否定的。对 BFGS 一类方法而言,还需要控制新点的方向导数,以避免新旧梯度差产生不正确的曲率。

本课将推导 Wolfe / Strong Wolfe 条件、证明它们和 BFGS 正定性的关系、手算一次非精确线搜索,并说明它们究竟能保证什么收敛结论。

一、问题、符号与假设

考虑无约束最小化 ( \min_{x\in\mathbb R^n}f(x) )。在点 (x_k) 处取方向 (p_k),要求

[ g_k=\nabla f(x_k),\qquad g_k^Tp_k<0. ]

这是严格下降方向条件,若 (g_k=0),需要单独按驻点停止或采取其他策略。沿搜索射线定义一维函数

[ \phi(\alpha)=f(x_k+\alpha p_k),\quad \phi’(0)=g_k^Tp_k<0. ]

我们的任务不是精确求 (\arg\min_{\alpha>0}\phi(\alpha)),而是找到满足可验证条件的某个步长,称为非精确线搜索。以下讨论假定沿射线连续可微;存在性证明还要求 (\phi) 在 ([0,\infty)) 上有有限下界。分析收敛速率时再额外增加梯度 Lipschitz 与函数下界等条件。

二、为什么仅靠 Armijo 还不够?

Armijo 条件要求:对 (c_1\in(0,1)),

[ \boxed{\phi(\alpha)\le\phi(0)+c_1\alpha\phi’(0).} \tag{1} ]

因为 (\phi’(0)<0),右侧小于 (\phi(0)),因此确实有充分下降。

但是,当 (\alpha\to0^+) 时,利用 (\phi(\alpha)=\phi(0)+\alpha\phi’(0)+o(\alpha)),可知所有足够小的正步长都满足 Armijo。仅靠它无法排除过小的步长。

对拟牛顿法还存在更深层问题:BFGS 试图从移动量

[ s_k=x_{k+1}-x_k=\alpha_kp_k ]

和梯度变化

[ y_k=g_{k+1}-g_k ]

中学习曲率。保持更新正定所需的关键条件为

[ \boxed{s_k^Ty_k>0.} \tag{2} ]

Armijo 只约束两个点的函数值,并不直接约束梯度变化,所以不足以保证式 (2)。

三、弱 Wolfe 与 Strong Wolfe 条件

选取两个固定参数

[ \boxed{0<c_1<c_2<1.} ]

弱 Wolfe 条件同时要求 Armijo (1) 和

[ \boxed{\phi’(\alpha)\ge c_2\phi’(0).} \tag{3} ]

由于 (\phi’(0)<0),右侧仍为负数,但比初始方向导数更接近零。直观上:既要目标值降得足够多,也不能在坡度仍然很陡时过早停止。

Strong Wolfe 条件将曲率条件改为

[ \boxed{|\phi’(\alpha)|\le c_2|\phi’(0)|.} \tag{4} ]

它限制了新点方向导数的绝对值,不但阻止过早停步,也限制越过谷底后产生过大的反向斜率。

检查 数学条件 主要防止        
Armijo (\phi(\alpha)\le\phi(0)+c_1\alpha\phi’(0)) 函数值下降不足        
弱 Wolfe 曲率 (\phi’(\alpha)\ge c_2\phi’(0)) 仍在陡坡上就停步        
Strong Wolfe 曲率 ( \phi’(\alpha) \le c_2 \phi’(0) ) 陡坡停步,也控制越过谷底的过冲

关系辨析:Strong Wolfe 必然蕴含弱 Wolfe;反过来不成立。 弱 Wolfe 允许新点方向导数很大且为正,只要 Armijo 仍成立;Strong Wolfe 不允许这种幅度过大的导数。

3.1 为什么合法 Wolfe 步长确实存在?

假设 (\phi\in C^1([0,\infty)))、(\phi’(0)<0)、且 (\phi) 沿射线下有界。证明甚至存在满足 Strong Wolfe 的正步长。

如果对每个 (\alpha>0) 都有 (\phi’(\alpha)<c_2\phi’(0)<0),积分得到

[ \phi(\alpha)-\phi(0)<c_2\alpha\phi’(0)\to-\infty, ]

与下有界矛盾。因此方向导数必在某处达到或超过 (c_2\phi’(0))。由连续性,存在首次穿过该水平的 (\alpha_*>0),满足

[ \phi’(\alpha_*)=c_2\phi’(0), ]

并且对 (0\le t\le\alpha_*) 有 (\phi’(t)\le c_2\phi’(0))。积分给出

[ \phi(\alpha_)-\phi(0) \le c_2\alpha_\phi’(0) \le c_1\alpha_*\phi’(0), ]

最后一步因为 (c_2>c_1) 且 (\phi’(0)<0)。所以 Armijo 成立,而 ( \phi’(\alpha_*) =c_2 \phi’(0) ),Strong Wolfe 也成立。

这证明的是符合条件的步长存在,并非“任意缩步程序”都能找到它。 Wolfe 实现往往需要扩大候选步长、构造区间,再用 bracket/zoom 搜索。

四、关键定理:Wolfe 如何保证 BFGS 曲率为正?

用弱 Wolfe (3):

[ g_{k+1}^Tp_k\ge c_2g_k^Tp_k. ]

两边减 (g_k^Tp_k):

[ (g_{k+1}-g_k)^Tp_k \ge(c_2-1)g_k^Tp_k. ]

两边乘正的 (\alpha_k):

[ \begin{aligned} s_k^Ty_k &=\alpha_kp_k^T(g_{k+1}-g_k)
&\ge\alpha_k(c_2-1)g_k^Tp_k. \end{aligned} ]

注意 (c_2-1<0) 且 (g_k^Tp_k<0),所以

[ \boxed{s_k^Ty_k\ge\alpha_k(1-c_2)(-g_k^Tp_k)>0.} \tag{5} ]

这不需要 (f) 凸!只要步长满足 Wolfe,且方向严格下降,曲率内积就为正。

BFGS 近似逆 Hessian 常记为 (H_k\succ0),更新式:

[ \boxed{ H_{k+1}=(I-\rho s_ky_k^T)H_k(I-\rho y_ks_k^T)+\rho s_ks_k^T,\quad \rho=\frac1{s_k^Ty_k}>0. } \tag{6} ]

对任意非零向量 (v),令 (w=(I-\rho y_ks_k^T)v),则

[ v^TH_{k+1}v=w^TH_kw+\rho(s_k^Tv)^2. ]

两项非负;若第二项为零,则 (s_k^Tv=0),故 (w=v\ne0),第一项严格为正。因此

[ \boxed{H_k\succ0,\ s_k^Ty_k>0\ \Rightarrow\ H_{k+1}\succ0.} ]

但保持正定不等于无条件全局收敛;BFGS 的收敛定理仍要求合适的函数、方向和矩阵控制假设。

五、完整数值例题:同时检查三个条件

取

[ f(x)=\frac12x^2,\quad x_0=2,\quad g_0=2,\quad p_0=-2,\quad c_1=0.1,\quad c_2=0.5. ]

则

[ \phi(\alpha)=\frac12(2-2\alpha)^2=2(1-\alpha)^2,\quad \phi’(\alpha)=-4+4\alpha,\quad \phi’(0)=-4. ]

逐个解三组不等式。

Armijo:

[ 2(1-\alpha)^2\le2-0.4\alpha \iff 0<\alpha\le1.8. ]

弱 Wolfe 曲率:

[ -4+4\alpha\ge-2 \iff\alpha\ge0.5. ]

Strong Wolfe 曲率:

[ |-4+4\alpha|\le2 \iff0.5\le\alpha\le1.5. ]

因此单独满足 Armijo 的步长区间很宽,但Strong Wolfe 的合法区间为 ([0.5,1.5])。

候选 (\alpha) (f(x_0+\alpha p_0)) (\phi’(\alpha)) Armijo 弱 Wolfe Strong Wolfe
0.25 1.125 −3 ✓ ✗ ✗
0.50 0.500 −2 ✓ ✓ ✓
1.00 0 0 ✓ ✓ ✓
1.75 1.125 3 ✓ ✓ ✗

假设我们的试探顺序是 (0.25\to0.5),则第一个通过 Strong Wolfe 的候选是 (0.5)。注意:如果只是纯 Armijo Backtracking,从 (0.25) 开始只会继续变小,根本无法进入这个例子要求的 Wolfe 合法区间!

取 (\alpha=0.5),则

[ x_1=2-0.5\times2=1,\quad s_0=x_1-x_0=-1,\quad y_0=g_1-g_0=1-2=-1, ]

所以

[ s_0y_0=1>0. ]

若起始 Hessian 近似 (B_0=2),一维 BFGS Hessian 更新为

[ B_1=B_0-\frac{B_0^2s_0^2}{s_0^2B_0}+\frac{y_0^2}{s_0y_0} =2-2+1=1>0. ]

这说明 Wolfe 与 BFGS 曲率条件之间不是经验相关性,而是严格的不等式保证。

5.1 再进行一次实际迭代

仍使用负梯度方向。在 (x_1=1) 处 (p_1=-1)。若仍从 (\alpha=0.25) 试探,则 Wolfe 曲率尚未达到;扩大到 (\alpha=0.5) 就接受,得到

[ x_2=1-0.5=\frac12,\qquad f(x_2)=\frac18. ]

迭代 (x_k) 接受步长 (f(x_k))
0 2 — 2
1 1 0.5 0.5
2 0.5 0.5 0.125

本例的最速下降方向与固定比例迭代很简单,不能据此认为 Wolfe 或 BFGS 总是线性收敛。

六、收敛理论:Wolfe 对下降方向能保证什么?

这部分连接第 15 课的下降引理与第 18 课的 Armijo 收敛证明。

再假设 (f) 下有界:(f(x)\ge f_{\inf}>-\infty),并且所有搜索线段上梯度都满足统一的 (L)-Lipschitz 条件。沿严格下降方向 (p_k) 使用满足弱 Wolfe 的 (\alpha_k)。

由式 (5):

[ (1-c_2)(-g_k^Tp_k)\le (g_{k+1}-g_k)^Tp_k. ]

Cauchy–Schwarz 与 Smooth 给出

[ (g_{k+1}-g_k)^Tp_k \le|g_{k+1}-g_k||p_k| \le L\alpha_k|p_k|^2. ]

所以

[ \boxed{ \alpha_k\ge \frac{(1-c_2)(-g_k^Tp_k)} {L|p_k|^2}. } \tag{7} ]

代入 Armijo:

[ \begin{aligned} f(x_k)-f(x_{k+1}) &\ge c_1\alpha_k(-g_k^Tp_k)
&\ge\frac{c_1(1-c_2)}L \frac{(g_k^Tp_k)^2}{|p_k|^2}. \end{aligned} ]

定义方向与负梯度方向的夹角 (\theta_k):

[ \cos\theta_k= \frac{-g_k^Tp_k}{|g_k||p_k|}>0. ]

于是

[ \boxed{ f(x_k)-f(x_{k+1}) \ge \frac{c_1(1-c_2)}L\cos^2\theta_k|g_k|^2. } \tag{8} ]

求和并利用函数下界:

[ \boxed{ \sum_{k=0}^{\infty}\cos^2\theta_k|g_k|^2 \le \frac{L[f(x_0)-f_{\inf}]}{c_1(1-c_2)}<\infty. } \tag{9} ]

这就是常称的 Zoutendijk 型条件。

还不能仅凭式 (9) 得到 (|g_k|\to0):如果方向与负梯度越来越接近垂直,(\cos\theta_k\to0),它可能掩盖较大的梯度。

若再假设统一角度下界 (\cos\theta_k\ge\delta>0),则

[ \sum_k|g_k|^2<\infty \quad\Rightarrow\quad \boxed{|g_k|\to0.} ]

并有

[ \boxed{ \min_{0\le k<K}|g_k|^2 \le \frac{L[f(x_0)-f_{\inf}]} {c_1(1-c_2)\delta^2K}. } \tag{10} ]

对于最速下降方向 (p_k=-g_k),有 (\cos\theta_k=1),所以这个附加角度条件自动成立。但一般 BFGS 即使保持 (H_k\succ0),也不自动得到统一的角度下界;需要控制近似矩阵的条件数等额外性质。这里的结论也只是梯度趋零,非凸函数不保证全局最优。

七、失败反例:Armijo 通过,但 BFGS 曲率为负

取非凸但下有界的函数

[ f(t)=(t^2-1)^2,\qquad f’(t)=4t(t^2-1). ]

从 (t_0=0.1) 出发:

[ f(t_0)=0.9801,\qquad g_0=-0.396. ]

选下降方向 (p_0=-g_0=0.396),步长 (\alpha=0.1/0.396),得到 (t_1=0.2)。

这时

[ f(t_1)=0.9216,\quad f’(t_1)=-0.768. ]

取 (c_1=0.1)。Armijo 的右侧为

[ 0.9801+0.1\alpha(g_0p_0) =0.9801-0.00396=0.97614. ]

显然 (0.9216<0.97614),所以 Armijo 通过。

但

[ s=t_1-t_0=0.1,\quad y=g_1-g_0=-0.372, ]

因此

[ \boxed{sy=-0.0372<0.} ]

这时若不加检查地直接进行标准 BFGS 更新,就不能沿用保持正定的证明。

另外,强 Wolfe 可能允许新点方向导数为正,只要绝对值仍足够小;所以“新方向导数必须为负”也不是 Strong Wolfe 的定义。

八、实际 Wolfe 线搜索流程及限制

从试探步长开始,沿 (p_k) 评价 (\phi) 和 (\phi’)。若函数下降不足,说明候选可能过大,应缩小或建立上界;若下降充分但方向导数仍过于负(弱 Wolfe 失败),说明步长可能太小,应尝试增大;当区间已包围合适步长时,可通过插值或二分进行 zoom,检查是否同时满足两条条件。

这解释了为什么 Wolfe 搜索不能简单等价为“Armijo Backtracking 再加一个判断”:只会缩小步长的搜索可能永远到不了曲率条件所要求的区间。实际实现还需要处理数值精度、函数或梯度求值成本与最大尝试次数。理论上的存在性不等于带有限预算的每次软件调用必然成功。

对 BFGS 而言,Wolfe 的重要意义是提供 (s_k^Ty_k>0);对一般下降方向而言,Wolfe 还提供式 (9) 的全局梯度分析基础。两种保证都不等于无条件全局最优。

九、知识关系图

flowchart TD
    A["下降方向 gᵀp<0"] --> B["Armijo:足够下降"]
    B --> C["Wolfe:方向导数不再太负"]
    C --> D["sᵀy>0"]
    D --> E["BFGS 正定性保持"]
    C --> F["下有界 + 统一梯度 Lipschitz"]
    F --> G["Zoutendijk 求和界"]
    G --> H["再加统一方向角度下界"]
    H --> I["梯度范数趋零"]
    C --> J["Strong Wolfe 进一步限制绝对导数"]

十、课堂总结与下一讲

结论 成立条件 不能误推的结论
Armijo 充分下降 严格下降方向及通过检查的步长 曲率 (s^Ty>0)
弱 Wolfe (\Rightarrow s^Ty>0) (\alpha>0)、严格下降方向、(0<c_2<1) 无需其他假设的 BFGS 全局收敛
Strong Wolfe (\Rightarrow) 弱 Wolfe (0<c_1<c_2<1) 新方向导数必须仍为负
Zoutendijk 型求和界 下有界 + 统一 Lipschitz 梯度 + Wolfe 单靠求和界就有梯度收敛
(|g_k|\to0) 上述条件 + 统一角度下界 非凸全局最优

今天的三个核心公式:

[ \boxed{\phi’(\alpha)\ge c_2\phi’(0)} \qquad \boxed{|\phi’(\alpha)|\le c_2|\phi’(0)|} ]

[ \boxed{s_k^Ty_k\ge\alpha_k(1-c_2)(-g_k^Tp_k)>0} ]

[ \boxed{\sum_k\cos^2\theta_k|g_k|^2<\infty.} ]

下一讲:第 20 课(2026 年 11 月 8 日)——PL 条件、梯度主导与非强凸函数的线性收敛。 将比较强凸、PL 与梯度主导性质,证明为什么有些非凸问题也能获得函数值的几何收敛保证,以及为什么这一结论不自动包含最优解唯一性。

第 21 课(11 月 9 日)为第三周复盘。今日四级自测总分 100 分,作答后按 80 分及以上正常推进、60–79 分补例子、低于 60 分重点复习;测评不改变日期课号。


十一、今日四级自测(100 分)

首次课堂不附标准答案、正确选项、开放题评分要点;独立测验 JSON 含答案,作答前请勿查看,以免泄题。

Lv1|Wolfe 曲率条件与正定性|预计 2 分钟|15 分|单选

设当前方向 (p) 满足 (\nabla f(x)^Tp<0),步长 (\alpha>0),记 (s=\alpha p,\ y=\nabla f(x+\alpha p)-\nabla f(x))。下列哪项一定正确?

A. 只要满足 Armijo 充分下降,就必然有 (s^Ty>0)。

B. 若满足弱 Wolfe 曲率条件 (\nabla f(x+\alpha p)^Tp\ge c_2\nabla f(x)^Tp) 且 (0<c_2<1),就有 (s^Ty>0)。

C. Strong Wolfe 要求新位置沿 (p) 的方向导数必须仍为负。

D. 目标函数可微且下有界时,任意正步长都满足 Wolfe 条件。

提示:将弱 Wolfe 两边减去旧的方向导数,再乘以正步长 α;注意旧方向导数为负。


Lv2|强 Wolfe 的数值步长筛选|预计 3 分钟|20 分|数值

取 (f(x)=\frac12x^2),当前 (x=3),搜索方向 (p=-3),参数 (c_1=0.1,\ c_2=0.6)。依次测试候选步长 (\alpha=0.2,\ 0.4,\ 0.8),找出第一个同时满足 Armijo 与 Strong Wolfe 的步长。只填写数值,保留三位小数。

提示:写出 φ(α)=f(2−2α) 与 φ′(α),逐个判断函数值充分下降和方向导数绝对值条件。


Lv3|非凸函数中 Armijo 与 BFGS 曲率的反例|预计 5 分钟|25 分|单选

考虑非凸但下有界的 (f(t)=(t^2-1)^2)。从 (t_0=0.05) 取最速下降方向 (p=-f’(t_0)=0.1995),选择步长 (\alpha=0.05/0.1995),使 (t_1=0.1)。设 (c_1=0.1,\ c_2=0.5),并记 (s=t_1-t_0,\ y=f’(t_1)-f’(t_0))。以下哪项正确?

A. 该步通过 Armijo,但 (s y<0),说明 Armijo 本身不能保证 BFGS 的正定曲率条件。

B. 该步同时满足弱 Wolfe,因此 (s y>0)。

C. 由于目标函数下有界,(f’(t_1)) 必比 (f’(t_0)) 更接近零。

D. 只要沿负梯度方向且函数下降,任何 BFGS 近似 Hessian 都自动保持正定。

提示:计算 f(0.1)、f(0.2)、f′(0.1)、f′(0.2),分别检验 Armijo 和 s·y。


Lv4|曲率证明、全局收敛界与线搜索设计|预计 12 分钟|40 分|开放证明

设 (f:\mathbb R^n\to\mathbb R) 连续可微,方向 (p_k) 严格下降:(g_k^Tp_k<0),(g_k=\nabla f(x_k))。取 (0<c_1<c_2<1),步长 (\alpha_k>0) 同时满足 Armijo 与弱 Wolfe;定义 (s_k=\alpha_kp_k,\ y_k=g_{k+1}-g_k)。

A(12 分) 从弱 Wolfe 曲率条件严格证明 (s_k^Ty_k>0)。写出 BFGS 逆 Hessian 更新 [ H_{k+1}=(I-\rho s_ky_k^T)H_k(I-\rho y_ks_k^T)+\rho s_ks_k^T,\qquad \rho=(s_k^Ty_k)^{-1}, ] 并证明当 (H_k\succ0) 时 (H_{k+1}\succ0)。

B(12 分) 再假设 (f) 下有界、梯度在所有迭代线段上满足统一 (L)-Lipschitz 条件。定义 (\cos\theta_k=-g_k^Tp_k/(|g_k||p_k|))。利用弱 Wolfe、Lipschitz 梯度和 Armijo 依次导出对 (\alpha_k) 的下界,以及 [ \sum_{k=0}^{\infty}\cos^2\theta_k|g_k|^2<\infty. ] 解释:如果再有 (\cos\theta_k\ge\delta>0),能对梯度范数得出什么结论?为什么仅有 BFGS 正定性不足以直接宣称该角度下界?

C(10 分) 对 (f(x)=x^2/2,\ x_0=4,\ p_0=-2,\ c_1=0.1,\ c_2=0.5),比较 (\alpha=0.25) 与 (\alpha=1.0) 是否满足 Armijo、弱 Wolfe、Strong Wolfe;对被接受的 (\alpha=1.0) 计算 (s_0,y_0,s_0^Ty_0),并以一维 Hessian 近似 (B_0=2) 做一次 BFGS Hessian 更新。

D(6 分) 给出一个非精确 Wolfe 线搜索的合理流程:分别说明“下降不足”和“曲率尚未达到”的试探步长应朝什么方向调整;解释为什么只会缩步的 Armijo Backtracking 不能普遍保证 Wolfe 曲率条件。

提示:A 用弱 Wolfe 减去旧方向导数,并用向量二次型证明逆 BFGS 正定;B 用梯度 Lipschitz 推出 α 的下界,再对充分下降望远镜求和;D 关注小步长处方向导数仍过于负的现象。