数学优化理论 · 第25课:FISTA与加速近端梯度法
2026年11月13日(北京时间),第4周第4天;讲授约18分钟,自测另计。
问题:上节课投影梯度法、前面近端梯度法(ISTA)在凸复合优化中给出函数值误差 $O(1/K)$。在每步仍只计算一次光滑梯度和一次 Prox 的前提下,可以提高到 $O(1/K^2)$ 吗?
本课路线:模型与假设 → ISTA对照 → FISTA更新 → 三点不等式 → 势函数严格证明 → 具体数值迭代 → 失败反例与KKT → 四级自测。
一、模型、假设和收敛指标
考虑 [ \boxed{\min_{x\in\mathbb R^n}F(x)=f(x)+h(x)}. ] 在本课所有全局函数值收敛定理中,明确假设:
- $f:\mathbb R^n\to\mathbb R$ 凸、可微,$\nabla f$ 是 $L$-Lipschitz 连续,$L>0$;
- $h:\mathbb R^n\to(-\infty,+\infty]$ 真、下半连续、凸,可以不可微,也可以用 $+\infty$ 表示约束;
- 至少有一个最优点 $x^\in\arg\min F$,$F^=F(x^*)$;
- 使用欧氏范数、精确计算梯度与Prox、采用固定步长 $\eta=1/L$;
- $x_0\in\operatorname{dom}h$,并设第一轮的外推点为 $y_0=x_0$。
在这种记号下: [ \operatorname{prox}_{h/L}(v) =\arg\min_z\left[h(z)+\frac L2|z-v|^2\right]. ] 如果 $L$ 仅是一个有效但不紧的 Smooth 上界,仍可以使用;步长会偏保守。
收敛量是最后一步函数值差 $F(x_K)-F^*$,不是梯度范数、也不是与某个选定最优点的距离。
二、ISTA为什么只有标准 $O(1/K)$ 界
普通近端梯度(ISTA): [ x_{k+1}=\operatorname{prox}{h/L}\left(x_k-\frac1L\nabla f(x_k)\right). ] 它在当前点 $x_k$ 处线性化 $f$,精确最小化 [ Q_L(z;y)=f(y)+\langle\nabla f(y),z-y\rangle +\frac L2|z-y|^2+h(z). ] 取 $y=x_k$,可推导三点不等式 [ F(x{k+1})-F(z) \le\frac L2\left(|x_k-z|^2-|x_{k+1}-z|^2\right) \quad(\forall z). ] 对 $z=x^$ 求和,再使用 ISTA 目标值单调不增: [ \boxed{F(x_K)-F^\le \frac{L|x_0-x^*|^2}{2K}}. ] 这是标准上界,不是说 ISTA 的每个实例都只能以这个速度下降。
三、FISTA算法:外推点不是简单地“再走一大步”
令 $t_0=1,\ y_0=x_0$。对 $k=0,1,\ldots$ 重复:
[
\begin{aligned}
x_{k+1}
&=\operatorname{prox}{h/L}\left(y_k-\frac1L\nabla f(y_k)\right),
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}\tag{1}
]
算法每轮使用一次新的梯度、一次精确Prox;$y_k$ 用来计算下一步,而 $x_k$ 是实际输出。$t_0=1$ 意味着第一次更新无动量,前两次更新和同样步长的 ISTA 相同;第三次更新开始出现非零外推。
参数满足关键恒等式 [ \boxed{t_{k+1}^2-t_{k+1}=t_k^2}.\tag{2} ] 这个代数关系不是装饰,它使下一节势函数中相邻迭代的权重恰好衔接。任意替换外推系数,不能直接继承加速证明。
四、基本引理:复合目标的三点不等式
设 [ p=\operatorname{prox}_{h/L}\left(y-\frac1L\nabla f(y)\right). ] 要证明:对任何 $z\in\operatorname{dom}h$, [ \boxed{F(p)-F(z)\le\frac L2\left(|y-z|^2-|p-z|^2\right).}\tag{3} ]
第一步:Prox最优性。 定义 $g=\nabla f(y)$。由 [ p=\arg\min_u\left[h(u)+\langle g,u-y\rangle+\frac L2|u-y|^2\right] ] 及该子问题的 $L$-强凸性,对任何 $z$: [ h(p)+\langle g,p-y\rangle+\frac L2|p-y|^2 +\frac L2|p-z|^2 \le h(z)+\langle g,z-y\rangle+\frac L2|z-y|^2. ] 该不等式也可由 $0\in\partial h(p)+g+L(p-y)$ 与强凸次梯度条件逐项推得。
第二步:凸性与Smooth。 [ f(p)\le f(y)+\langle g,p-y\rangle+\frac L2|p-y|^2 ] 以及 [ f(z)\ge f(y)+\langle g,z-y\rangle. ] 两者分别代入前述近端最优性关系,消去 $g$ 内积、合并 $f+h$,即得到式(3)。注意:需要 $f$ 凸以对任意 $z$ 给出下界;Smooth本身只给二次上界。
五、FISTA加速证明:把函数值误差放入势函数
记 $\Delta_k=F(x_k)-F^*\ge0$,引入辅助点 [ z_0=x_0,\quad z_{k+1}=t_kx_{k+1}-(t_k-1)x_k. ] 由FISTA外推定义,对所有 $k\ge0$: [ z_k=t_ky_k-(t_k-1)x_k. ] 因此 [ \boxed{t_k(x_{k+1}-y_k)=z_{k+1}-z_k.}\tag{4} ]
第一步:构造用于三点引理的比较点。 令 [ w_k=(1-1/t_k)x_k+(1/t_k)x^. ] 由上面两个恒等式: [ t_k(y_k-w_k)=z_k-x^, \quad t_k(x_{k+1}-w_k)=z_{k+1}-x^. ] 代入式(3)并乘以 $t_k^2$: [ t_k^2[F(x_{k+1})-F(w_k)] \le\frac L2\left(|z_k-x^|^2-|z_{k+1}-x^*|^2\right). ]
第二步:使用 $F$ 的凸性。 $t_k\ge1$,故 $w_k$ 是合法凸组合: [ F(w_k)\le (1-1/t_k)F(x_k)+(1/t_k)F^. ] 从而 [ \boxed{ t_k^2\Delta_{k+1}-(t_k^2-t_k)\Delta_k \le\frac L2\left(|z_k-x^|^2-|z_{k+1}-x^*|^2\right). }\tag{5} ]
第三步:观察望远镜势函数。 当 $k\ge1$ 时, [ t_k^2-t_k=t_{k-1}^2. ] 于是定义 [ E_{k+1}=t_k^2\Delta_{k+1}+\frac L2|z_{k+1}-x^|^2. ] 由式(5),$E_{k+1}\le E_k$。对 $k=0$,由于 $t_0=1$: [ E_1\le\frac L2|x_0-x^|^2. ] 故对任意 $K\ge1$: [ \boxed{t_{K-1}^2\Delta_K\le\frac L2|x_0-x^*|^2.}\tag{6} ]
第四步:证明权重二次增长。 [ t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}2\ge t_k+\frac12. ] 由于 $t_0=1$,归纳得 [ t_k\ge\frac{k+2}{2}. ] 在式(6)中代入 $t_{K-1}\ge(K+1)/2$,得到 [ \boxed{ F(x_K)-F^* \le\frac{2L|x_0-x^*|^2}{(K+1)^2}, \qquad K\ge1. }\tag{7} ]
因此 $F(x_K)-F^=O(1/K^2)$。要使误差不超过 $\varepsilon$,梯度/Prox迭代复杂度的典型上界为 $O(\sqrt{L}\,|x_0-x^|/\sqrt{\varepsilon})$。
请区分:证明了势函数递减,没有证明 $F(x_{k+1})\le F(x_k)$ 每一步成立,也没有证明最优解唯一或变量距离按 $O(1/K^2)$ 收敛。
六、具体数值迭代:FISTA和ISTA何时出现差别?
取一维复合目标 [ F(x)=\frac12(x-4)^2+|x|,\qquad x_0=0. ] 真实Smooth常数为1,但取有效保守上界 $L=4$,所以 $\eta=1/4$。Prox是阈值 $\eta=0.25$ 的软阈值 [ S_{0.25}(v)=\operatorname{sign}(v)\max(|v|-0.25,0). ] 当外推点为正且本例迭代在正区间时: [ x_{k+1}=S_{0.25}\big(y_k-\tfrac14(y_k-4)\big) =S_{0.25}(0.75y_k+1)=0.75y_k+0.75. ]
- 第1步:$y_0=0$,$x_1=0.75$,$t_1=(1+\sqrt5)/2\approx1.618034$,$y_1=x_1$。
- 第2步:$x_2=0.75(0.75)+0.75=1.3125$,$t_2\approx2.193527$。
- 第3步:$y_2=x_2+\frac{t_1-1}{t_2}(x_2-x_1)\approx1.470986$,故 $x_3\approx1.853240$。
由于正区间 $F(x)=\frac12(x-3)^2+3.5$,全局最优点 $x^=3$,$F^=3.5$。
| 迭代 | ISTA输出 | FISTA输出 | ISTA函数值 | FISTA函数值 |
|---|---|---|---|---|
| 0 | 0 | 0 | 8.000000 | 8.000000 |
| 1 | 0.750000 | 0.750000 | 6.031250 | 6.031250 |
| 2 | 1.312500 | 1.312500 | 4.923828 | 4.923828 |
| 3 | 1.734375 | 1.853240 | 4.300903 | 4.157530 |
第三步FISTA有优势,但这只是具体数据;不意味着任何函数、任何迭代都比ISTA更低。上面的理论保证的是最坏情况的整体误差上界。
七、失败反例:加速不等于每步单调
考虑 $f(x)=\frac12x^2$、$h=0$。虽然其真实Smooth常数为1,选择保守上界 $L=4$ 完全合法,从 $x_0=1$ 运行上述标准FISTA。
数值递推可得到:$x_7\approx-0.017473$,$F(x_7)\approx0.00015265$;而 $x_8\approx-0.037069$,$F(x_8)\approx0.00068707$。函数值在第8步反而上升,没有违反式(7),因为FISTA控制的是势函数以及整个序列的误差界,而非逐步目标值单调性。
进一步,如果任意改变外推系数、将 $h$ 换成一般非凸函数、或选用不合法的大步长,式(3)或式(5)可能失效。例如 $h=0,f(x)=x^2/2,\eta=3$ 时第一步就有 $x_1=-2x_0$,从 $x_0=1$ 出发函数值由0.5增至2。不能把启发式动量或非凸Prox称为有本课的全局 $O(1/K^2)$ 保证。
如果工程上希望函数值单调,可以考虑专门的单调FISTA变体或有证明的重启策略;它们的更新与证明不能直接用“每次升高就重启”这一经验规则替代。
八、与KKT、投影梯度的联系
若 $h=\delta_C$,其中 $C$ 非空闭凸,则 [ \operatorname{prox}_{h/L}(v)=\Pi_C(v), ] FISTA变为加速投影梯度。不动点最优性为 [ 0\in\nabla f(x^)+N_C(x^). ] 在适当约束资格条件下,它可写成活跃约束的KKT乘子表达式;不要误以为边界最优点必须满足 $\nabla f=0$。
例如 [ \min_{x\le1}\tfrac12(x-2)^2: \quad x^=1,\quad f’(1)=-1. ] 写 $g(x)=x-1\le0$,驻点条件 $f’(x^)+\lambda^=0$ 得到 $\lambda^=1$,且 $\lambda^g(x^)=0$。但对 [ \min_{x\le0}\tfrac12x^2 ] 最优点$x^*=0$、约束也活跃,乘子却是0。因此活跃不意味着乘子严格正。
九、方法对照与数学关系图
| 方法 | 一轮主操作 | 凸复合问题函数值界 | 必须注意 |
|---|---|---|---|
| ISTA | 在 $x_k$ 计算梯度与Prox | $O(1/K)$ | 合法步长、凸性 |
| FISTA | 在 $y_k$ 计算梯度与Prox、外推 | $O(1/K^2)$ | 专门的$t_k$参数、函数值可非单调 |
| 投影梯度 | $h=\delta_C$ 时的ISTA | $O(1/K)$ | 投影集合须非空闭凸 |
| 加速投影梯度 | $h=\delta_C$ 时的FISTA | $O(1/K^2)$ | 与KKT的法锥条件相联系 |
flowchart TD
A["凸且L-Smooth的f + 闭凸h"] --> B["复合二次模型 + Prox"]
B --> C["三点不等式"]
C --> D["ISTA:距离平方望远镜求和"]
D --> E["函数值 O(1/K)"]
C --> F["FISTA:特殊外推权重t"]
F --> G["势函数递减 + t²增长"]
G --> H["函数值 O(1/K²)"]
B --> I["h=指标函数"]
I --> J["投影 / 法锥 / KKT"]
F --> K["函数值可能非单调"]
十、四级自测(总分100)
课程首次发送不公布正确选项、数值答案和开放题评分要点。独立quiz JSON包含答案,请作答前不要打开。
【Lv1|FISTA的定理假设与充分结论|预计2分钟】设 $F=f+h$,按本课标准FISTA公式更新。以下哪项在所述假设下必然正确?
A. 只要 f 的梯度Lipschitz,即使 h 是任意非凸函数,也有全局 O(1/K²) 函数值误差保证。
B. 若 f 凸且L-Smooth、h真下半连续凸、最优解存在,按给定权重和步长运行,可保证最后一步函数值误差 O(1/K²),但目标值不必每步下降。
C. FISTA的外推系数可以任意更改,原势函数证明仍自动成立。
D. FISTA每一轮的函数值都不大于相同步长的ISTA。
提示:检查凸性、权重恒等式和势函数所控制的量。
【Lv2|两次近端梯度数值计算|预计3分钟】考虑 $F(x)=\frac12(x-6)^2+2|x|$,从 $x_0=0$ 开始,采用有效但保守的Smooth上界 $L=4$、步长 $\eta=1/4$ 和标准FISTA($t_0=1,y_0=x_0$)。求两次更新后的输出 $x_2$(只填数值,保留三位小数)。
请仅填写数值,允许绝对误差0.001。
提示:前两次更新的外推系数为零;先做梯度步再做阈值为0.5的软阈值。
【Lv3|第三步FISTA与ISTA比较|预计5分钟】设 $F(x)=\frac12(x-5)^2+|x|$,采用有效Smooth上界 $L=5$、步长 $1/5$,从 $x_0=0$ 出发。FISTA使用 $t_0=1$ 和 $t_{k+1}=(1+\sqrt{1+4t_k^2})/2$,ISTA使用相同步长。比较两种方法第3次更新后的输出,以下哪一项正确?
A. FISTA与ISTA均得到x3=4,因为Prox第一步就消除正则化影响。
B. FISTA的x3约为2.096258,ISTA的x3=1.952;第三步外推开始改变迭代点。
C. FISTA的x3=1.952,ISTA的x3约为2.096258;FISTA第三步一定更慢。
D. 两者始终相同,因为t0=1导致所有动量系数永久为零。
提示:先算x1=0.8、x2=1.44,再求t1、t2和y2;FISTA第三步在y2而不是x2计算Prox。
【Lv4|FISTA势函数证明、复杂度与KKT|预计14分钟】设 $F=f+h$,$f$ 凸且 $L$-Smooth,$h$ 真、下半连续、凸,最优点 $x^$ 存在。用本课FISTA更新,$t_0=1,y_0=x_0$。(A,10分) 对 $p=\operatorname{prox}_{h/L}(y-\nabla f(y)/L)$,从近端最优性、凸性和Smooth推导 $F(p)-F(z)\le\frac L2(|y-z|^2-|p-z|^2)$。(B,14分) 定义 $z_0=x_0,\ z_{k+1}=t_kx_{k+1}-(t_k-1)x_k$ 和 $\Delta_k=F(x_k)-F^$,构造 $w_k=(1-1/t_k)x_k+x^/t_k$,证明 $t_k^2\Delta_{k+1}-(t_k^2-t_k)\Delta_k\le\frac L2(|z_k-x^|^2-|z_{k+1}-x^|^2)$。(C,10分) 用$t_{k+1}^2-t_{k+1}=t_k^2$证明 $F(x_K)-F^\le2L|x_0-x^*|^2/(K+1)^2$,解释为何不能据此断言每步函数值下降。(D,6分) 若$h=\delta_C$,解释最优点的法锥/KKT条件;分别求$\min_{x\le0}\frac12(x-3)^2$和$\min_{x\ge1}\frac12(x-1)^2$的活跃约束及乘子,说明活跃并不必然意味着正乘子。
请分A、B、C、D逐项写出推导过程。
提示:B中利用t_k(y_k-w_k)=z_k-x及t_k(x_{k+1}-w_k)=z_{k+1}-x;C构造势函数并证明t_k≥(k+2)/2;D写成g(x)≤0。
十一、复盘要点与下一讲
今日关键不是“动量能提速”这句直觉,而是:在凸复合模型下,Prox三点不等式配合特定的$t_k$恒等式,构造了能望远镜收缩的势函数,由$t_k=\Omega(k)$得到最后一步函数值$O(1/K^2)$。它不保证每一步的目标值都下降,也不能直接用于非凸问题或任意动量。
下一讲(第26课,2026年11月14日):近端梯度映射与复合驻点、回溯FISTA及单调加速的保证边界。我们将检查未知$L$时如何用局部二次模型测试合法步长、为什么要同步更新加速权重,以及非凸复合目标时可证明的驻点性与凸情形$O(1/K^2)$的区别。
首次课堂不披露答案;请作答后按Lv1=15、Lv2=20、Lv3=25、Lv4=40逐题评分。80分及以上正常继续;60–79分补充外推权重与势函数例题;低于60分复习Prox三点不等式、凸性及活跃约束KKT。成绩不改变课程日期与编号。