第26课:近端梯度映射、回溯 FISTA 与单调加速
2026-11-14|第4周·第5天|18分钟(自测另计)
第25课证明了固定 (L) 的 FISTA 在凸复合问题中有 (O(1/K^2)) 的函数值误差保证。今天解决三个问题:不知道 (L) 如何回溯?非光滑目标的驻点应如何衡量?加速迭代的函数值能否单调下降?
一、问题、假设与两种收敛指标
研究 (F(x)=f(x)+h(x))。主要定理假设 (f) 凸、可微且 (L)-Smooth,(h) 真、下半连续、凸,最优解 (x^*) 存在;近端子问题精确求解。非凸扩展部分单独去掉 (f) 的凸性,但保留其 (L)-Smooth、(h) 的凸性和 (F_{\inf}>-\infty)。
定义给定局部曲率 (M>0) 的近端梯度步与映射: [ T_M(y)=\operatorname{prox}_{h/M}!\left(y-\frac{\nabla f(y)}M\right), \qquad G_M(y)=M[y-T_M(y)]. ] 若 (h=0),则 (G_M(y)=\nabla f(y));若 (h=\delta_C),则 (G_M(y)=M[y-\Pi_C(y-\nabla f(y)/M)]),是投影梯度映射。
由近端最优性: [ 0\in\partial h(T_M(y))+\nabla f(y)+M(T_M(y)-y). ] 所以 (G_M(y)=0) 当且仅当 (0\in\nabla f(y)+\partial h(y))。凸时这是全局最优性的充要条件;非凸时仅为一阶驻点条件。 还可得到 [ \operatorname{dist}(0,\nabla f(p)+\partial h(p)) \le (1+L/M)|G_M(y)|,\quad p=T_M(y), ] 由 (\nabla f(p)-\nabla f(y)+G_M(y)\in\nabla f(p)+\partial h(p)) 和 Lipschitz 梯度推出;它解释了映射范数为什么是合理的残差。
二、局部二次上界回溯:不知道 L 也可以选步长
设 (g=\nabla f(y)),定义二次上界模型 [ Q_M(u;y)=f(y)+g^T(u-y)+\frac M2|u-y|^2+h(u). ] 对某个 (M) 算出 (p=T_M(y)=\arg\min_u Q_M(u;y)),检查 [ \boxed{f(p)\le f(y)+g^T(p-y)+\frac M2|p-y|^2.}\tag{1} ] 不满足则 (M\leftarrow\gamma M)(例如 (\gamma=2)),重算近端步,再检查。实际无需知道 (L)。因为下降引理保证 (M\ge L) 时式(1)对所有 (p) 成立,所以每轮从正试探值开始有限终止。固定初始试探 (M_{\rm init}>0)、倍率 (\gamma>1) 时,接受值有统一上界 [ M_k\le \overline M=\max{M_{\rm init},\gamma L}. ] 若 FISTA 每轮从上轮接受的 (M_{k-1}) 继续试探,则 (M_k) 非递减,仍有上述上界。
注意式(1)是局部二次模型接受条件,不同于直接要求 (F(p)\le F(x_k)) 的 Armijo 检查。在 FISTA 中梯度点 (y_k) 是外推点,不一定等于 (x_k)。
三、严格推导:被接受的近端步满足什么不等式?
记 (p=T_M(y)),并假设局部二次测试通过。因为 (h) 凸,(Q_M(\cdot;y)) 关于 (u) 为 (M)-强凸,所以对任何 (z\in\operatorname{dom}h): [ Q_M(p;y)+\frac M2|p-z|^2\le Q_M(z;y). ] 接受测试意味着 (F(p)\le Q_M(p;y))。由 (f) 凸, [ F(z)\ge f(y)+g^T(z-y)+h(z) =Q_M(z;y)-\frac M2|z-y|^2. ] 合并: [ \boxed{F(p)-F(z)\le\frac M2(|y-z|^2-|p-z|^2).}\tag{2} ] 三点不等式所需的是实际接受的模型测试和凸性;并不强制 (M) 精确等于全局 (L)。
如果取 (z=y),即使 (f) 非凸,仍可单独利用 (Q_M) 的强凸性和测试,得到 [ \boxed{F(p)\le F(y)-\frac M2|p-y|^2 =F(y)-\frac{|G_M(y)|^2}{2M}.}\tag{3} ] 这一式对未外推的非凸近端梯度法特别重要。对外推 FISTA,它比较的是 (F(y_k)),不能直接说明 (F(x_{k+1})\le F(x_k))。
四、回溯 FISTA:非递减 M 与 O(1/K²)
初始化 (t_0=1,\ y_0=x_0)。对 (k=0,1,\ldots):
[
\begin{aligned}
&M_k\ge M_{k-1}\text{(从上轮接受值起回溯)},
&x_{k+1}=T_{M_k}(y_k),
&t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}2,
&y_{k+1}=x_{k+1}+\frac{t_k-1}{t_{k+1}}(x_{k+1}-x_k).
\end{aligned}
]
第一轮 (M_0) 从 (M_{\rm init}) 开始。记 (\Delta_k=F(x_k)-F^),辅助变量
[
z_0=x_0,\quad z_{k+1}=t_kx_{k+1}-(t_k-1)x_k.
]
令比较点 (w_k=(1-1/t_k)x_k+x^/t_k)。由外推公式:
[
t_k(y_k-w_k)=z_k-x^,\quad
t_k(x_{k+1}-w_k)=z_{k+1}-x^.
]
对 (w_k) 用式(2),并用 (F(w_k)\le(1-1/t_k)F(x_k)+F^/t_k),得
[
t_k^2\Delta_{k+1}-(t_k^2-t_k)\Delta_k
\le\frac{M_k}2(|z_k-x^|^2-|z_{k+1}-x^|^2).
]
除以 (M_k),利用 (t_k^2-t_k=t_{k-1}^2)、(M_k\ge M_{k-1})、(\Delta_k\ge0),得
[
\boxed{E_{k+1}\le E_k},\quad
E_{k+1}:=\frac{t_k^2}{M_k}\Delta_{k+1}+\frac12|z_{k+1}-x^|^2.
]
首步 (E_1\le|x_0-x^|^2/2)。再用 (t_{K-1}\ge(K+1)/2) 及 (M_{K-1}\le\overline M),得到
[
\boxed{F(x_K)-F^\le\frac{2\overline M|x_0-x^*|^2}{(K+1)^2},\quad K\ge1.}\tag{4}
]
这是对具体的非递减回溯 FISTA 的证明,不能直接声称任意调节步长的实现都满足同一个势函数不等式。
五、数值演示:实际如何测试并更新?
取 [ f(x)=\tfrac12(x-4)^2,\quad h(x)=|x|,\quad x_0=y_0=0. ] 真实 (L=1),但算法不知道它。取初始试探 (M=0.75)、回溯倍率 (\gamma=2)。软阈值为 (S_{1/M})。
- 试探 (M=0.75):(p=S_{4/3}(16/3)=4)。此时 (f(p)=0),而式(1)右端为 (8-16+6=-2),测试失败。
- 令 (M=1.5):(p=S_{2/3}(8/3)=2)。此时 (f(p)=2),式(1)右端为 (8-8+3=3),测试通过。
所以 (x_1=2),(F(x_0)=8),(F(x_1)=4),且 [ G_{1.5}(0)=1.5(0-2)=-3,\qquad |G_{1.5}(0)|^2=9. ] 第二轮从 (M=1.5) 起步,(y_1=x_1=2),梯度 (f’(2)=-2),故 (x_2=S_{2/3}(2+2/1.5)=8/3),目标值 (F(x_2)=32/9\approx3.556)。本题实际最优点 (x^*=3),最优值 (3.5)。
| 轮次 | 尝试 M | 局部检查 | 接受输出 | 目标值 |
|---|---|---|---|---|
| 初始 | — | — | 0 | 8 |
| 1(首次) | 0.75 | 失败 | — | — |
| 1(回溯) | 1.5 | 通过 | 2 | 4 |
| 2 | 1.5 | 通过 | 8/3 | 32/9 |
六、“单调加速”有哪些不同含义?
标准 FISTA 不保证 (F(x_{k+1})\le F(x_k))。可采用一种不改变任何内部状态的安全做法:正常运行有加速保证的 FISTA,并仅在报告输出时保存 [ b_K\in\arg\min_{0\le j\le K} F(x_j). ] 那么 (F(b_K)) 单调不增,且 (F(b_K)\le F(x_K)),所以同样满足式(4)。这叫“历史最好值的单调报告”,不是修改内部外推步骤的单调 FISTA(MFISTA)。
MFISTA 等真正改变迭代的单调加速方案需要专门设计和证明。不能将 (b_K) 擅自当作下一轮内部 (x_K),然后无条件沿用标准 FISTA 势函数。
七、非凸时能保证什么?失败反例
若 (f) 仅 (L)-Smooth、(h) 仍凸、(F_{\inf}>-\infty),不用外推,从 (x_k) 做回溯近端梯度并得到 (M_k\le\overline M)。式(3)给出 [ F(x_{k+1})\le F(x_k)-\frac{|G_{M_k}(x_k)|^2}{2M_k}. ] 望远镜求和: [ \boxed{ \min_{0\le k<K}|G_{M_k}(x_k)|^2 \le\frac{2\overline M[F(x_0)-F_{\inf}]}K. }\tag{5} ] 这保证的是最佳近端梯度映射平方 (O(1/K)),而非全局函数值误差 (O(1/K^2))。
失败反例:(f(x)=1-\cos x,\ h=0)。它全局 (1)-Smooth,(x=\pi) 处 (\nabla f=0),因此 (G_M(\pi)=0);但 (f(\pi)=2>f(0)=0)。所以非凸驻点不一定全局最优。另一个风险是任意减小 (M_k) 或修改外推公式,前面 (E_{k+1}\le E_k) 所依赖的参数关系可能失效。
八、KKT 补强:活跃约束不一定有正乘子
当 (h=\delta_C) 时,近端更新变为投影,(G_M(x)=0) 等价于 (0\in\nabla f(x)+N_C(x))。适当资格条件下,可写成 KKT 驻点与互补松弛。
例如 (\min_{x\le1}\tfrac12(x-3)^2) 在 (x^=1) 处约束活跃,(f’(1)=-2),乘子 (\lambda^=2);而 (\min_{x\ge0}\tfrac12 x^2) 在 (x^=0) 处同样活跃,但乘子为 0。两者均满足 (\lambda g(x^)=0)。切记:活跃只意味着 (g(x^*)=0),不意味着 (\lambda>0)。
九、知识关系图
flowchart TD
A["复合目标 F=f+h"] --> B["近端映射 G_M"]
B --> C["局部二次上界测试"]
C --> D["增大 M:有限回溯"]
D --> E["凸 + 非递减 M"]
E --> F["FISTA 势函数"]
F --> G["函数值 O(1/K²)"]
G --> H["历史最优报告:单调且保留加速界"]
D --> I["非凸 f + 无外推"]
I --> J["最佳 G_M 平方 O(1/K)"]
B --> K["h 为指标函数"]
K --> L["法锥、KKT、互补松弛"]
| 版本 | 主要假设 | 严格结论 |
|---|---|---|
| 近端梯度 + 回溯 | 凸复合、M 有统一上界 | 最后一步函数值 (O(1/K)) |
| FISTA + 非递减回溯 | 凸复合、M 非递减有界 | 最后一步函数值 (O(1/K^2)) |
| FISTA + 历史最佳报告 | 不改变内部 FISTA | 报告值单调且继承 (O(1/K^2)) |
| 非凸 f 的近端梯度 + 回溯 | h 凸、F 下有界、无外推 | 最佳近端梯度映射平方 (O(1/K)) |
参考:Beck & Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems, 2009, https://doi.org/10.1137/080716542;Beck & Teboulle, Fast Gradient-Based Algorithms for Constrained Total Variation Image Denoising and Deblurring Problems, 2009, https://doi.org/10.1109/TIP.2009.2028250。这里的证明只针对本文明确给出的算法与假设。
十、今日四级自测(100 分)
首次课堂不附标准答案、正确选项或开放题评分细则。不要提前打开独立 JSON,以免泄题。
Lv1|回溯近端更新的充分条件|15 分|预计 2 分钟
设 (F=f+h),其中 (f) 凸且 (L)-Smooth,(h) 真、下半连续、凸。给定 (M>0),在点 (y) 计算 (p=\operatorname{prox}_{h/M}(y-\nabla f(y)/M))。下面哪一项是正确的?
- A. 只有准确知道全局最小的 (L),才能测试并运行回溯近端算法。
- B. 若 (f(p)\le f(y)+\langle\nabla f(y),p-y\rangle+\frac M2|p-y|^2),即可用这一接受条件建立近端三点不等式;但 (y) 为 FISTA 外推点时,不代表 (F(p)\le F(x_k))。
- C. 局部二次上界检查通过就说明 (p) 是整个复合优化问题的全局最优点。
- D. 只要某轮 (M) 变小,普通 FISTA 的同一个加速势函数证明就无条件保持成立。
提示:区分在外推点 y 处的二次模型上界与上一输出 x_k 的目标值单调性。
Lv2|回溯步长与近端梯度映射|20 分|预计 3 分钟
| 令 (f(x)=\tfrac12(x-5)^2,\ h(x)=1.5 | x | ),起点 (y=0)。从试探曲率 (M=0.5) 开始,若局部二次上界检查未通过,就令 (M\leftarrow 2M),重新计算 (p=\operatorname{prox}_{h/M}(y-f’(y)/M)),直至首次通过。求首次接受时的 (\boxed{ | G_M(y) | ^2}),其中 (G_M(y)=M(y-p))。只填写数值,保留三位小数。 |
提示:先用软阈值公式求每次的 p,并检查 smooth 项的局部二次上界;注意 G_M(y)=M(y-p)。
Lv3|自适应加速与单调输出的理论边界|25 分|预计 5 分钟
设 (F=f+h) 满足凸复合优化假设,最优点存在。FISTA 在每个外推点用回溯找到满足局部二次上界的 (M_k),且实现规定 (M_{k+1}\ge M_k)、(M_k\le\overline M<\infty),并使用标准 (t_k) 递推。关于理论保证和“单调化”,哪项正确?
- A. 原始 FISTA 输出 (F(x_k)) 一定逐步不增,因为每轮都检查了局部二次上界。
- B. 任意把本轮 (x_{k+1}) 替换成历史最优点、然后继续用它计算下一轮外推,都可以不改证明直接继承 (O(1/k^2))。
- C. 未改变内部 FISTA 迭代时,单独报告历史最佳点 (b_k\in\arg\min_{0\le j\le k}F(x_j)),可使报告值单调不增且继承 (O(1/k^2)) 上界;但不能把这一输出包装与修改内部迭代的单调 FISTA 混为一谈。
- D. 对任意非凸 (f) 加上凸 (h),只要回溯成功,就有全局函数值 (O(1/k^2)) 保证。
提示:区分外部报告最优值与更改算法内部状态;注意加速证明需要凸性和参数关系。
Lv4|回溯 FISTA 势函数、非凸驻点与 KKT|40 分|预计 14 分钟
完成以下四部分,写明假设和主要不等式。
A(10 分) 设 (f) 凸、(L)-Smooth,(h) 真、下半连续、凸,令 (p=\operatorname{prox}_{h/M}(y-\nabla f(y)/M)),且该点通过局部二次上界检查。证明任意 (z\in\operatorname{dom}h) 满足 [ F(p)-F(z)\le\frac M2\left(|y-z|^2-|p-z|^2\right). ] 说明当 (M\ge L) 时检查必通过,以及按倍数回溯为何有限终止。
B(14 分) 标准 FISTA 采用 (t_0=1),(t_{k+1}=(1+\sqrt{1+4t_k^2})/2),在外推点 (y_k) 用非递减且有上界的 (M_k) 计算 (x_{k+1})。定义 (\Delta_k=F(x_k)-F^),(z_0=x_0),(z_{k+1}=t_kx_{k+1}-(t_k-1)x_k)。利用比较点 (w_k=(1-1/t_k)x_k+x^/t_k),证明 [ \frac{t_k^2}{M_k}\Delta_{k+1}+\frac12|z_{k+1}-x^|^2 \le \frac{t_{k-1}^2}{M_{k-1}}\Delta_k+\frac12|z_k-x^|^2 \quad(k\ge1), ] 并推出 (F(x_K)-F^\le 2\overline M|x_0-x^|^2/(K+1)^2)。
C(10 分) 去掉 (f) 的凸性,但保留 (L)-Smooth、(h) 凸、(F) 下有界,考虑从当前点 (x_k) 做回溯近端梯度(不外推),设 (M_k\le\overline M)。证明 [ \min_{0\le k<K}|G_{M_k}(x_k)|^2 \le\frac{2\overline M(F(x_0)-F_{\inf})}{K}. ] 解释 (G_M(x)=0) 与 (0\in\nabla f(x)+\partial h(x)) 的联系,以及为何它不保证非凸全局最优。
D(6 分) 对 (\min_{x\le2}\tfrac12(x-6)^2) 与 (\min_{x\ge-1}\tfrac12(x+1)^2),分别求解最优点、活跃约束、KKT 乘子和互补松弛,说明活跃不一定意味着正乘子。
提示:A 用强凸的近端二次模型和凸性;B 用 t_k(y_k−w_k)=z_k−x、t_k(x_{k+1}−w_k)=z_{k+1}−x,再利用 M_k 非递减;C 从模型的充分下降和望远镜求和入手;D 统一写成 g(x)≤0。
十一、下一讲
第27课|2026年11月15日(第4周·第6天):算子分裂初步:Forward–Backward、Douglas–Rachford 与非扩张算子。重点讨论 Prox 的不动点理论和何时能够将单一 Prox 扩展成多算子迭代。11月16日第28课为第四周阶段测验,按日期推进,不因自测成绩改变课号。
自测评分:Lv1 15、Lv2 20、Lv3 25、Lv4 40 分,总计100分。作答后逐题评分,80分及以上正常继续;60–79分补充针对性例题;低于60分复习近端最优性、二次模型接受条件和 KKT。