对应 note_10_pgm.pdf。这一章解决 composite optimization：目标 $f(x)=g(x)+h(x)$，其中 $g$ 光滑、$h$ 凸但可能不可微。核心算法是 proximal gradient method (PGM)：对 $g$ 线性化，对 $h$ 保留原样，再加一个二次 proximal 项。

0. 一句话理解这一章

近端梯度法 = 梯度下降 + prox。它比普通次梯度法快，因为没有把不可微项粗暴地用一个次梯度代替，而是把 $h$ 的结构通过 ${\mathrm{prox}}_h$ 精确保留下来。

1. 知识地图

            composite model
              min f(x)=g(x)+h(x)
              g smooth, h closed convex/simple
                          │
                          ▼
            proximal mapping
              prox_h(x)=argmin_u h(u)+1/2||u-x||²
                          │
                          ▼
            PGM update
              x+ = prox_{t h}(x-t∇g(x))
                          │
                          ▼
            gradient mapping
              G_t(x)=1/t (x-prox_{t h}(x-t∇g(x)))
              x+ = x-tG_t(x)
                          │
                          ▼
            convergence
              convex: O(1/k)
              strongly convex: linear in distance
              line search: same order with t_min
              nonconvex*: stationarity via G_t → 0

2. Composite model

本章考虑：

$$\underset{x}{min}f(x)=g(x)+h(x),$$

其中：

• $g$：凸、可微，$\mathrm{\nabla }g$ Lipschitz；
• $h$：closed convex，可以不可微；
• $h$ 要“simple”：${\mathrm{prox}}_{th}$ 容易算。

典型例子：

问题	$g(x)$	$h(x)$
约束光滑优化	光滑目标	$I_C(x)$
LASSO	$\frac{1}{2}|Ax-b{|}^2$	$\lambda |x{|}_1$
box constrained QP	$\frac{1}{2}{x}^{T}Ax+b^{T}x$	$I_{[0,1{]}^n}(x)$
稀疏正则化	loss	${\ell }_1$、group lasso 等

3. Proximal mapping

定义：

$${\mathrm{prox}}_h(x)=\arg \underset{u}{min}\{h(u)+\frac{1}{2}\parallel u-x{\parallel }^2\}.$$

带步长：

$${\mathrm{prox}}_{th}(x)=\arg \underset{u}{min}\{h(u)+\frac{1}{2t}\parallel u-x{\parallel }^2\}.$$

常见 prox

$h$	${\mathrm{prox}}_h(x)$
$0$	$x$
$I_C$	${\mathrm{\Pi }}_C(x)$
$\lambda |x{|}_1$	soft-thresholding

Soft-thresholding：

$$[{\mathrm{prox}}_{\lambda \parallel \cdot {\parallel }_1}(x){]}_i=\{\begin{array}{ll}{x}_i-\lambda ,& x_i\ge \lambda ,\\ 0,& |x_i|\le \lambda ,\\ x_i+\lambda ,& x_i\le -\lambda .\end{array}$$

带步长 $t$ 时阈值变成 $t\lambda$。

4. PGM 更新

从 projected gradient 的模型出发：

$$x_{k+1}=\arg \underset{u}{min}\{g(x_k)+\mathrm{\nabla }g(x_k{)}^T(u-x_k)+h(u)+\frac{1}{2t_k}\parallel u-x_k{\parallel }^2\}.$$

等价写法：

$$x_{k+1}={\mathrm{prox}}_{t_{k}h}(x_k-t_k\mathrm{\nabla }g(x_k)).$$

特殊情况：

• $h=0$：PGM 退化为普通梯度下降；
• $h=I_C$：PGM 退化为 projected gradient；
• $h=\lambda \parallel x{\parallel }_1$：PGM 变成 ISTA / soft-thresholding 迭代。

5. Gradient mapping

定义：

$$G_t(x)=\frac{1}{t}(x-{\mathrm{prox}}_{th}(x-t\mathrm{\nabla }g(x))).$$

于是

$$x^{+}={\mathrm{prox}}_{th}(x-t\mathrm{\nabla }g(x))=x-t{G}_t(x).$$

注意：$G_t(x)$ 不是 $\mathrm{\nabla }f(x)$，也不一定是 $f$ 的次梯度。但它扮演“站点残差”的角色：

$$G_t(x)=0⟺x\in \arg min(g+h).$$

并且

$$G_t(x)\in \mathrm{\nabla }g(x)+\partial h(x-t{G}_t(x)).$$

这条包含式是 PGM 收敛分析的入口。

6. 一步下降引理

若 $\mathrm{\nabla }g$ 是 $L$-Lipschitz 且 $0<t\le 1/L$，则

$$g(x-t{G}_t(x))\le g(x)-t\mathrm{\nabla }g(x{)}^T{G}_t(x)+\frac{t}{2}\parallel G_t(x){\parallel }^2.$$

进一步可得对任意 $z$：

$$f(x-t{G}_t(x))\le f(z)+G_t(x{)}^T(x-z)-\frac{t}{2}\parallel G_t(x){\parallel }^2-\frac{m}{2}\parallel x-z{\parallel }^2.$$

令 $x^{+}=x-t{G}_t(x)$，得到两个最常用结论：

$$f(x^{+})\le f(x)-\frac{t}{2}\parallel G_t(x){\parallel }^2,$$$$f(x^{+})-f^{\ast }\le \frac{1}{2t}(\parallel x-x^{\ast }{\parallel }^2-\parallel x^{+}-x^{\ast }{\parallel }^2).$$

这和 GD 的收敛证明非常像，只是把 $\mathrm{\nabla }f$ 换成 $G_t$。

7. 收敛率

7.1 固定步长 $t=1/L$

凸情形：

$$f(x_k)-f^{\ast }\le \frac{1}{2kt}\parallel x_0-x^{\ast }{\parallel }^2.$$

即 $O(1/k)$，和 smooth GD 同阶，明显好于普通次梯度法的 $O(1/\sqrt{k})$。

7.2 强凸情形

若 $g$ 是 $m$-强凸，$t=1/L$，则距离有线性收敛：

$$\parallel x_k-x^{\ast }{\parallel }^2\le {(1-\frac{m}{L})}^k\parallel x_0-x^{\ast }{\parallel }^2.$$

注意讲义这里强调的是 distance to optimal set；函数值也可通过额外条件得到对应线性界。

7.3 Backtracking line search

如果不知道 $L$，从 $\hat{t}$ 开始回溯 $t\leftarrow \beta t$，直到

$$g(x-t{G}_t(x))\le g(x)-t\mathrm{\nabla }g(x{)}^T{G}_t(x)+\frac{t}{2}\parallel G_t(x){\parallel }^2.$$

线搜索选出的步长满足

$$t\ge t_{min}=min\{\hat{t},\beta /L\}.$$

于是仍有

$$f(x_k)-f^{\ast }\le \frac{1}{2k{t}_{min}}\parallel x_0-x^{\ast }{\parallel }^2,$$

强凸时

$$\parallel x_k-x^{\ast }{\parallel }^2\le (1-m{t}_{min}{)}^k\parallel x_0-x^{\ast }{\parallel }^2.$$

8. Fast PGM / FISTA

基础 PGM 的函数值收敛率是 $O(1/k)$。A12 开始要求比较 basic PGM 与 fast proximal gradient method，也就是常见的 FISTA。对

$$\underset{x}{min}F(x)=g(x)+h(x)$$

其中 $g$ convex differentiable 且 $\mathrm{\nabla }g$ 为 $L$-Lipschitz，FISTA 的固定步长版本常写为：

$$x_{k+1}={\mathrm{prox}}_{h/L}(y_k-\frac{1}{L}\mathrm{\nabla }g(y_k)),$$$${\theta }_{k+1}=\frac{1+\sqrt{1+4{\theta }_k^2}}{2},y_{k+1}=x_{k+1}+\frac{{\theta }_k-1}{{\theta }_{k+1}}(x_{k+1}-x_k),$$

其中 ${\theta }_0=1,y_0=x_0$。

关键结论：

方法	典型函数值收敛率	特点
PGM / ISTA	$O(1/k)$	单步稳，证明直接
FPGM / FISTA	$O(1/k^2)$	用 momentum 加速，函数值可能非单调

A12.5 的图像比较应当看到：FISTA 前期通常明显快于 basic PGM，但曲线可能有轻微振荡；PGM 更稳定但下降慢。

9. 典型例子

9.1 Box constrained QP

$$min\frac{1}{2}{x}^{T}Ax+b^{T}x\text{s.t.}0\le x\le 1.$$

写成

$$g(x)=\frac{1}{2}{x}^{T}Ax+b^{T}x,h(x)=I_{[0,1{]}^n}(x).$$

PGM 更新：

$$x_{k+1}={\mathrm{\Pi }}_{[0,1{]}^n}(x_k-t_k(A{x}_k+b)).$$

投影就是逐坐标截断到 $[0,1]$。

9.2 LASSO

$$\underset{x}{min}\frac{1}{2}\parallel Ax-b{\parallel }^2+\lambda \parallel x{\parallel }_1.$$

取

$$g(x)=\frac{1}{2}\parallel Ax-b{\parallel }^2,h(x)=\lambda \parallel x{\parallel }_1.$$$$\mathrm{\nabla }g(x)=A^T(Ax-b).$$

PGM / ISTA 更新：

$$x_{k+1}={\mathrm{soft}}_{t_k\lambda }(x_k-t_k{A}^T(A{x}_k-b)).$$

其中

$$[{\mathrm{soft}}_{\tau }(z){]}_i=\mathrm{sign}(z_i)max\{|z_i|-\tau ,0\}.$$

9.3 线性绝对值项的 prox

A12.4 里有

$$g(x)=|x_1+x_2|=|a^{T}x|,a=(1,1{)}^T.$$

通用公式是

$${\mathrm{prox}}_{t|a^T\cdot |}(z)=z-ta\mathrm{clip}(\frac{a^{T}z}{t\parallel a{\parallel }^2},-1,1).$$

因此这类题按三步算：

1. 先算梯度步 $z=x-t\mathrm{\nabla }f(x)$；
2. 再算 $a^{T}z$ 和 $\parallel a{\parallel }^2$；
3. 最后套上面的 clip 公式。

对 A12.4，$f$ 的 Hessian 最大特征值小于 1，所以 $t=1$ 合法；从 $x_0=(1,0{)}^T$ 出发，$z=x_0-\mathrm{\nabla }f(x_0)=(2.6,-0.2{)}^T$，从而

$$x_1={\mathrm{prox}}_{|x_1+x_2|}(z)=(1.6,-1.2{)}^T.$$

10. Nonconvex PGM（了解）

若 $g$ 非凸但 $\mathrm{\nabla }g$ 仍 Lipschitz，$h$ closed convex，PGM 仍可用于找 stationarity。

讲义结论：

• $f(x_k)$ 单调不增；
• 若 $x_k$ 不是 stationary point，则严格下降；
• $G_{t_k}(x_k)\to 0$；
• 有$$\underset{0\le i\le k}{min}\parallel G_{t_i}(x_i)\parallel \le O(1/\sqrt{k}).$$

这里的收敛目标不是全局最优，而是 stationarity。

11. 作业题型对照

作业/题型	典型问法	考点
prox 计算	求 $I_C$、$\lambda |x{|}_1$、box indicator 的 prox	投影、soft-thresholding
PGM 建模	把问题写成 $g+h$	区分 smooth part 和 simple nonsmooth part
写迭代	给 LASSO / box QP，写 $x_{k+1}$	${\mathrm{prox}}_{th}(x-t\mathrm{\nabla }g)$
最优性判据	证明 $G_t(x)=0⟺x$ 最优	prox 的一阶最优性 + $0\in \mathrm{\nabla }g+\partial h$
收敛率证明	推 $O(1/k)$	Lemma 2.6 的 telescoping
line search	不知道 $L$ 时如何回溯	验证 sufficient decrease inequality，得到 $t_{min}$
与次梯度比较	为什么 PGM 更快	PGM 利用 $h$ 的 prox 结构；次梯度只用一个 $g\in \partial h$
A12.1	证明 $u={\mathrm{prox}}_f(x)$、$x-u\in \partial f(u)$、变分不等式三者等价	prox 的一阶最优性条件；$x$ 是 minimizer iff $x={\mathrm{prox}}_f(x)$
A12.2	prox 运算规则：仿射缩放、尺度变换、加线性项	用变量替换和 prox 最优性条件推公式；特别是 $g(x)+a^{T}x$ 对应 ${\mathrm{prox}}_g(x-a)$
A12.3	证明 proximal mapping non-expansive	对两个 prox 点分别写最优性/单调性，推出 $|{\mathrm{prox}}_{th}(x)-{\mathrm{prox}}_{th}(y)|\le |x-y|$
A12.4	二维 $f+|x_1+x_2|$，验证 $t=1$ 并手算一步 PGM	检查 $L\le 1$；对 $|a^{T}x|$ 用 clip 形式 prox
A12.5	LASSO 上实现 PGM 与 FPGM/FISTA	$L={\lambda }_{max}(A^{T}A)$；PGM 用 soft-thresholding；FISTA 加 momentum；比较 $O(1/k)$ 与 $O(1/k^2)$

12. 解题招式

招式 1：先拆 $g+h$

问“能不能用 PGM”时，先检查：

• $g$ 是否可微且 $\mathrm{\nabla }g$ Lipschitz；
• $h$ 是否 closed convex；
• ${\mathrm{prox}}_{th}$ 是否容易计算。

如果 $h=I_C$，马上想到 projected gradient；如果 $h=\lambda \parallel x{\parallel }_1$，马上想到 soft-thresholding。

招式 2：写 prox 的最优性条件

$$x^{+}={\mathrm{prox}}_{th}(x-t\mathrm{\nabla }g(x))$$

等价于

$$0\in \partial h(x^{+})+\frac{1}{t}(x^{+}-x+t\mathrm{\nabla }g(x)).$$

整理得

$$G_t(x)\in \mathrm{\nabla }g(x)+\partial h(x^{+}).$$

这是证明 $G_t(x)=0$ 和下降引理的起点。

招式 3：PGM 收敛证明照搬 GD 框架

GD 里用

$$x^{+}=x-t\mathrm{\nabla }f(x)$$

PGM 里用

$$x^{+}=x-t{G}_t(x).$$

证明结构仍然是：

1. smooth $g$ 的二次上界；
2. $h$ 的次梯度不等式；
3. 配方成距离差；
4. telescoping。

招式 4：LASSO 更新不要写成普通梯度下降

错误写法：

$$x_{k+1}=x_k-t(A^T(A{x}_k-b)+\lambda s_k).$$

这只是次梯度法。

PGM 正确写法：

$$x_{k+1}={\mathrm{soft}}_{t\lambda }(x_k-t{A}^T(A{x}_k-b)).$$

区别很重要：前者慢，后者利用了 ${\ell }_1$ 的 prox。

招式 5：prox 性质题从最优性条件出发

证明 prox 相关性质时，先写

$$u={\mathrm{prox}}_f(x)⟺0\in \partial f(u)+u-x⟺x-u\in \partial f(u).$$

这一步能直接推出：

• 变分不等式：$⟨x-u,y-u⟩\le f(y)-f(u)$；
• minimizer fixed point：$0\in \partial f(x)⟺x={\mathrm{prox}}_f(x)$；
• non-expansiveness：对 $x,y$ 的两个 prox 点写两次并相加。

13. 自检清单

• [ ] ${\mathrm{prox}}_h$ 和 ${\mathrm{prox}}_{th}$ 的定义能写对吗？
• [ ] $u={\mathrm{prox}}_f(x)⟺x-u\in \partial f(u)$ 能证明吗？
• [ ] $h=I_C$ 时 prox 为什么是投影？
• [ ] $\lambda \parallel x{\parallel }_1$ 的 prox / soft-thresholding 能逐坐标写出吗？
• [ ] $|a^{T}x|$ 的 prox 能用 clip 公式手算吗？
• [ ] PGM 更新式能从模型最小化推出来吗？
• [ ] $G_t(x)$ 的定义能写出来吗？它为什么不是普通梯度？
• [ ] $G_t(x)=0⟺x$ 最优能证明吗？
• [ ] PGM 的 $O(1/k)$ 收敛证明和 GD 有什么对应关系？
• [ ] FISTA 的 momentum 参数和 $O(1/k^2)$ 结论能说清楚吗？
• [ ] Backtracking line search 检查的是 $g$ 的哪条二次上界？
• [ ] LASSO 的 ISTA 更新能不看书写出来吗？

14. 常见陷阱

1. 把 prox 的二次项系数写错：${\mathrm{prox}}_{th}$ 是 $\frac{1}{2t}\parallel u-x{\parallel }^2+h(u)$，不是 $\frac{t}{2}$。
2. 把 $G_t(x)$ 当作 $\mathrm{\nabla }f(x)$：它只是 gradient mapping，用于衡量 stationarity。
3. 对 $h$ 也线性化就退化成次梯度法：PGM 的关键恰恰是保留 $h(u)$。
4. LASSO 阈值忘记乘 $t$：阈值是 $t\lambda$，不是 $\lambda$。
5. line search 检查的是 $g$ 的上界：不是直接把 $f$ 当 smooth 函数套 GD。
6. 闭凸性很重要：closed convex 保证 prox well-defined 且通常唯一。
7. FISTA 不一定单调：图像比较时看到小幅上升/振荡不一定是代码错。

15. 最后的复习路线

1. 先把 9_次梯度与次梯度法.md 中的 $\partial f$ 和 $0\in \partial f$ 复习一遍。
2. 默写 prox 定义和三个基本 prox：$0$、indicator、${\ell }_1$。
3. 对 LASSO 手写一次 ISTA 更新，再写一次 FISTA 更新。
4. 复现 PGM 的 $O(1/k)$ 证明：一步下降引理 → 距离差 → telescoping。
5. 做 A12：先证明 prox 三件套，再手算 A12.4，最后实现 A12.5 的 PGM/FISTA 曲线。
6. 对比 GD / subgradient / PGM / FISTA：知道每个方法适合什么结构、收敛率为什么不同。