数学优化理论·第20课:PL 条件、梯度主导与非强凸线性收敛

2026-11-08|第3周·第6天|约18分钟(自测另计)

本课先独立做题:标准答案和开放题评分细则只放在独立 JSON,课堂讲义不包含答案。

1. 今天的问题:强凸真的是线性收敛的必要条件吗?

第15课证明:对于无约束、(\mu)-强凸且 (L)-Smooth 的目标,以步长 (1/L) 做梯度下降(GD),函数值误差满足 [ f(x_k)-f^\le(1-\mu/L)^k[f(x_0)-f^]. ] 第18—19课又看到:线搜索能控制下降,但“梯度小”在一般非凸问题上只意味着接近驻点,不一定全局最优。

现在问:如果函数不强凸、最优解也不唯一,仍能得到这种几何收敛吗?甚至函数非凸也行吗? 答案是:在满足一种更弱的“梯度主导”条件时,可以。该条件称为 Polyak–Łojasiewicz(PL)条件。

2. 定义、假设与三个容易混淆的概念

设 (f:\mathbb R^n\to\mathbb R) 可微,最优值 (f^=\min_x f(x)) 有限且可达到。称 (f) 满足常数 (\mu>0) 的 PL 不等式,如果对所有 (x) 都有 [ \boxed{\frac12|\nabla f(x)|^2\ge\mu[f(x)-f^].}\tag{PL} ] 其中 (f(x)-f^\ge0) 是函数值误差;PL 说:远离最优值时,梯度不能太小。注意这是关于函数值和梯度范数的关系,而不是直接关于 (x-x^) 的距离界。

条件 直接限制的对象 是否要求凸性 是否保证最优点唯一
(L)-Smooth 梯度变化上界 否 否
(\mu)-强凸 目标的一阶全局二次下界 是 是(存在极小点时)
PL((\mu>0)) 梯度平方与最优函数值误差 否 否

PL 立刻排除非最优驻点。 若 (\nabla f(\bar x)=0),则由 PL: [ 0\ge\mu[f(\bar x)-f^]\ge0, ] 从而 (f(\bar x)=f^)。因此 PL 意味着每个驻点都是全局最优点,但不要求只有一个最优点。

3. 强凸为什么能推出 PL?严格推导

假设 (f) 是无约束、可微的 (\mu)-强凸函数: [ f(y)\ge f(x)+g^T(y-x)+\frac\mu2|y-x|^2,\quad g=\nabla f(x). ] 右边关于 (d=y-x) 的最小值可通过配方得到: [ g^Td+\frac\mu2|d|^2 =\frac\mu2|d+g/\mu|^2-\frac{|g|^2}{2\mu} \ge-\frac{|g|^2}{2\mu}. ] 由于不等式对任意 (y) 成立,取 (y=x^): [ f^\ge f(x)-\frac{|\nabla f(x)|^2}{2\mu}. ] 移项即 [ \boxed{\frac12|\nabla f(x)|^2\ge\mu[f(x)-f^*].} ] 所以 强凸 (\Rightarrow) PL;下一节的反例会说明逆命题不成立。

4. 只有 Smooth + PL,也能证明 GD 几何收敛

假设:(f) 的梯度全局 (L)-Lipschitz,(f^) 有限可达到,且满足参数 (\mu>0) 的 PL;不要求凸。固定步长 (\eta=1/L): [ x_{k+1}=x_k-\frac1L\nabla f(x_k). ] 下降引理(不需要凸性): [ f(x_{k+1})\le f(x_k)-\frac1{2L}|\nabla f(x_k)|^2. ] 由 PL: [ |\nabla f(x_k)|^2\ge2\mu[f(x_k)-f^]. ] 因此 [ \begin{aligned} f(x_{k+1})-f^* &\le f(x_k)-f^-\frac\mu L[f(x_k)-f^]
&=\left(1-\frac\mu L\right)[f(x_k)-f^]. \end{aligned} ] 迭代递推: [ \boxed{f(x_k)-f^\le(1-\mu/L)^k[f(x_0)-f^*].}\tag{1} ] 这就是不依赖凸性的函数值几何收敛。如果目标并非恒为常数,Smooth 下降引理与 PL 合用还能推出 (0<\mu\le L),故收缩因子位于 ([0,1))。

更一般地,固定 (0<\eta<2/L) 时: [ f(x_{k+1})-f^\le \underbrace{[1-2\mu\eta(1-L\eta/2)]}_{\text{收缩因子}} [f(x_k)-f^]. ] 这不表示任意正步长都收敛;步长合法性仍须检查。

停止准则的含义。 PL 给出 (0\le f(x)-f^*\le|\nabla f(x)|^2/(2\mu))。当 (\mu) 已知且 PL 全局成立时,小梯度确实提供函数值误差证书;但它不是一般非凸优化普遍成立的结论。

5. 数值迭代:目标不强凸,GD 依旧线性收敛

考虑 [ \boxed{f(x,y,z)=\tfrac12(x^2+4y^2).} ] Hessian: [ \nabla^2f=\operatorname{diag}(1,4,0). ] 存在零特征值,所以目标不是强凸;全局最优点是 ((0,0,z)),任意 (z\in\mathbb R),最优点不唯一。

但 (L=4) 合法,且 [ \frac12|\nabla f|^2 =\tfrac12(x^2+16y^2) \ge\tfrac12(x^2+4y^2)=f(x,y,z)-f^*. ] 所以 PL 常数 (\mu=1) 合法。

从 ((4,2,5)) 开始,步长 (\eta=1/4): [ (x_{k+1},y_{k+1},z_{k+1}) =(3x_k/4,\,0,\,z_k). ]

(k) 当前点 ((x_k,y_k,z_k)) (f_k) PL 理论上界 (16(3/4)^k)
0 ((4,2,5)) 16 16
1 ((3,0,5)) 4.5 12
2 ((2.25,0,5)) 2.53125 9
3 ((1.6875,0,5)) 1.423828125 6.75

我们甚至可以写出 (k\ge1) 的精确形式: [ f_k=\frac92\left(\frac9{16}\right)^{k-1}. ] 这是几何衰减;第三个坐标一直保持为 5。由此看出:函数值收敛不要求最优点唯一,也不是说各坐标必须收敛到预先指定的某一个最优点。 最终得到的是 ((0,0,5)),属于整个最优解集合。

6. 更意外的例子:非凸函数也能满足 PL

考虑一维 [ \boxed{h(t)=\tfrac12t^2+2(1-\cos t).} ] 有 (h(t)\ge0=h(0)=h^*),且 [ h’(t)=t+2\sin t,\qquad h’‘(t)=1+2\cos t. ] 由于 (h’’(\pi)=-1<0),函数不是凸的;但 (|h’‘(t)|\le3),所以 (L=3) 合法。

令 (c=1-2/\pi>0)。当 (|t|\le\pi),(\sin t) 与 (t) 同号,因此 (|h’(t)|\ge|t|)。当 (|t|\ge\pi),由反三角不等式 [ |h’(t)|\ge |t|-2\ge(1-2/\pi)|t|=c|t|. ] 合并:(|h’(t)|\ge c|t|) 对所有 (t) 成立。

利用 (1-\cos t\le t^2/2): [ 0\le h(t)\le\tfrac32t^2. ] 于是 [ \frac12|h’(t)|^2\ge\frac{c^2}{2}t^2 \ge\underbrace{\frac{c^2}{3}}_{\mu>0}h(t). ] 故非凸的 (h) 满足全局 PL,可取 [ \boxed{\mu=(1-2/\pi)^2/3\approx0.044.} ] 结合上一节定理,步长 (1/3) 的 GD 对其函数值也有几何收敛保证。这里并未声称所有非凸函数都满足 PL,更未声称任意步长可用。

7. 两个失败反例:Smooth 不够,凸 + Smooth 也未必够

失败反例一:全局 Smooth,但存在非最优驻点。 [ f(t)=1-\cos t,\quad f’(t)=\sin t,\quad |f’‘(t)|\le1. ] 它是全局 (1)-Smooth,且 (f^*=0)。但 (t=\pi) 处 (f’(\pi)=0)、(f(\pi)=2>0)。若满足任何 (\mu>0) 的 PL,代入会得到 (0\ge2\mu),矛盾。故 Smooth (\not\Rightarrow) PL。

失败反例二:凸、全局 Smooth,也可能不满足 PL。 令 [ F(t)=t^2-\log(1+t^2). ] 可以计算 [ F’(t)=\frac{2t^3}{1+t^2},\qquad F’‘(t)=\frac{2t^2(t^2+3)}{(1+t^2)^2}. ] 它的 Hessian 始终非负且不超过 (9/4),所以凸且 (9/4)-Smooth;(F^=F(0)=0)。然而 (t\to0) 时, [ F(t)\sim\tfrac12t^4,\qquad F’(t)\sim2t^3, ] 因此 [ \frac{\tfrac12|F’(t)|^2}{F(t)-F^}\sim4t^2\longrightarrow0. ] 所以不存在正的全局 PL 常数。凸 + Smooth 也不能自动获得本课的几何收敛界。

8. 与 Armijo 和 KKT 的联系:不要跨越问题类别

第18课 Armijo + Backtracking 在全局 Smooth 下给出充分下降: [ f(x_{k+1})\le f(x_k)-c\underline\alpha|\nabla f(x_k)|^2. ] 如果再满足 PL,则同理可推得 [ f(x_{k+1})-f^\le (1-2c\mu\underline\alpha)[f(x_k)-f^], ] 故不仅强凸、满足 PL 的函数也可得到相应几何收敛。必须保持原来 Armijo 的统一正步长下界等假设。

但 PL 和本课 GD 都针对无约束目标。对于 [ \min_{x\le1}\tfrac12(x-2)^2, ] 最优点 (x^=1) 的目标梯度 (f’(1)=-1\ne0)。约束 (g(x)=x-1\le0) 活跃,乘子 (\lambda^=1),满足 [ f’(1)+\lambda^g’(1)=-1+1=0,\quad \lambda^g(1)=0. ] 所以不能将“无约束最优点梯度为零”强加给约束最优点。约束问题需要 KKT 残差、投影梯度映射或适当的原始—对偶证书。

9. 知识关系图

flowchart TD
  A["L-Smooth:控制单步下降"] --> D["GD 下降引理"]
  B["μ-强凸"] --> C["PL:梯度主导"]
  C --> E["PL + L-Smooth"]
  D --> E
  E --> F["函数值几何收敛"]
  G["秩亏二次目标:非强凸"] --> C
  H["特定非凸目标"] --> C
  I["一般 Smooth 非凸"] -. "不必满足" .-> C
  J["约束最优性"] --> K["KKT/投影残差,不可直接用 ∇f=0"]

本课总结: 强凸 (\Rightarrow) PL;PL 不要求凸性或唯一最优点;L-Smooth + PL + 合法步长 (\Rightarrow) 函数值几何收敛;一般 Smooth 仅能保证近似驻点,不能擅自声称全局最优。

10. 今日四级自测(100 分)

首次发送不公布标准答案和开放题评分要点;请不要在作答前打开独立 JSON,避免泄题。

Lv1|PL 条件的充分结论|15 分|预计 2 分钟|单选

设可微函数 (f) 在全空间满足 PL 不等式 (\frac12|\nabla f(x)|^2\ge\mu(f(x)-f^)),其中 (\mu>0),且全局最小值 (f^) 可达到。以下哪项必然成立?

A. (f) 必须是强凸函数。

B. 每一个满足 ( abla f(x)=0) 的点都是全局最优点。

C. (f) 的全局最优点必然唯一。

D. 只要梯度 Lipschitz 连续,就必然满足某个正的 PL 常数。

提示:把梯度为零代入 PL 不等式;不要把强凸的唯一解性质误加给 PL。

Lv2|秩亏二次函数的两步 GD|20 分|预计 3 分钟|数值

考虑 (f(x,y,z)=\frac12(x^2+4y^2))。从 ((x_0,y_0,z_0)=(4,2,5)) 出发,用固定步长 (\eta=1/4) 执行两次梯度下降 (w_{k+1}=w_k-\eta\nabla f(w_k))。求 (f(x_2,y_2,z_2))。只填写数值,保留三位小数。

提示:梯度第三个分量为 0;更新两个坐标两次后再算目标值。

Lv3|非凸 PL 与非 PL 反例比较|25 分|预计 5 分钟|单选

比较两个全局 Smooth 函数 (f_1(t)=\frac12t^2+2(1-\cos t)) 与 (f_2(t)=1-\cos t)。下列哪项正确?

A. (f_1’‘(pi)<0),所以 (f_1) 不可能满足任何全局 PL 不等式。

B. (f_1) 虽然非凸,但满足某个正的全局 PL 常数;(f_2) 在 (t=pi) 有非最优驻点,因此不满足任何正的全局 PL 常数。

C. (f_2) 的梯度全局 Lipschitz,因此它自动满足 PL 条件。

D. 只要 (f_1) 满足 PL,梯度下降用任意正步长都必然收敛。

提示:检查二阶导数、驻点与全局最优值;PL 不要求凸,但排除非最优驻点。

Lv4|PL 线性收敛、非强凸与非凸建模证明|40 分|预计 12 分钟|开放题

请完成四部分证明与计算(总计 40 分)。

A(12 分):设 (f) 为 (L)-Smooth、下确界可达到,且满足 (\frac12|\nabla f(x)|^2\ge\mu(f(x)-f^)),其中 (0<\mu\le L)。对步长 (\eta=1/L) 的 GD,从下降引理推导 (f(x_k)-f^\le(1-\mu/L)^k[f(x_0)-f^*]),说明这个结论是否要求凸性。

B(10 分):对 (f(x,y,z)=\frac12(x^2+4y^2)),证明 (L=4) 合法、PL 常数 (\mu=1) 合法,但函数不强凸且最优点不唯一。取初值 ((4,2,5))、步长 (1/4),求前两步迭代点和函数值。

C(12 分):对 (h(t)=\frac12t^2+2(1-\cos t)),验证其 (L=3)-Smooth 但不是凸函数。利用 (1-\cos t\le t^2/2) 和 ( t+2\sin t \ge(1-2/\pi) t ) 推导一个正的全局 PL 常数,说明非凸也可能满足 PL。

D(6 分):考虑 (\min_{x\le1}\frac12(x-2)^2)。求最优点与一个 KKT 乘子,写出活跃性、驻点和互补松弛,并解释为什么不可以直接要求约束最优点满足 (\nabla f=0)。

*提示:A 从充分下降出发;B 看 Hessian 的零特征值;C 在 t ≤π 与 t ≥π 分别控制导数;D 把约束写成 x−1≤0。*

11. 下一讲与评分方式

第21课|2026-11-09|第三周复盘。 将 GD 的下降引理、凸/强凸/PL 的不同收敛指标、Nesterov 势函数、Restart、Armijo/Wolfe 放在同一张条件—结论对照表中,并重点纠正“梯度小 = 全局最优”“目标值下降 = 迭代点收敛”“动量一定加速”等误解。

自测共 (15+20+25+40=100) 分。提交答案后逐题评分与反馈:80 分及以上继续按日进度;60—79 分补充对应例子;低于60分优先复习相关定理。成绩不改变日期课号。