对应 note_9_subgradient.pdf。这一章从 smooth optimization 进入 nonsmooth convex optimization：函数不可微时，梯度被替换为次梯度；最优性条件从 $\mathrm{\nabla }f(x^{\ast })=0$ 变成 $0\in \partial f(x^{\ast })$；算法从 GD 变成投影次梯度法。

0. 一句话理解这一章

次梯度是不可微凸函数的“全局支撑斜率”；次梯度法每一步沿某个次梯度走，但因为方向不一定下降，所以收敛慢，通常只有 $O(1/\sqrt{k})$，强凸时可到 $O(1/k)$。

1. 知识地图

            不可微凸函数
              |x|, ||x||, max_i f_i(x), indicator/normal cone
                          │
                          ▼
            次梯度
              f(y) ≥ f(x)+g^T(y-x), ∀y
              ∂f(x)=所有次梯度的集合
                          │
                          ▼
            最优性条件
              x* 最优 ⇔ 0 ∈ ∂f(x*)
              nonsmooth KKT：0 ∈ ∂L_x
                          │
                          ▼
            投影次梯度法
              y_{k+1}=x_k-α_k g_k
              x_{k+1}=Π_X(y_{k+1})
                          │
                          ▼
            收敛率
              一般凸：O(1/√k)
              强凸：O(1/k)
                          │
                          ▼
            扩展
              Polyak step / alternating projections / mirror descent

2. 次梯度定义

向量 $g$ 是 $f$ 在 $x$ 处的次梯度，若

$$f(y)\ge f(x)+g^T(y-x),\mathrm{\forall }y\in \mathrm{dom}f.$$

次微分：

$$\partial f(x)=\{g:f(y)\ge f(x)+g^T(y-x),\mathrm{\forall }y\}.$$

几何理解：

• $f(x)+g^T(y-x)$ 是 $f$ 的全局仿射下界；
• $(g,-1)$ 给出了 $\mathrm{epi}(f)$ 在 $(x,f(x))$ 处的非垂直支撑超平面；
• 可微凸函数时 $\partial f(x)=\{\mathrm{\nabla }f(x)\}$。

3. 常见次微分

3.1 绝对值

$$\partial |x|=\{\begin{array}{ll}\{1\},& x>0,\\ [-1,1],& x=0,\\ \{-1\},& x<0.\end{array}$$

3.2 欧氏范数

$$\partial \parallel x{\parallel }_2=\{\begin{array}{ll}\{x/\parallel x{\parallel }_2\},& x\ne 0,\\ \{g:\parallel g{\parallel }_2\le 1\},& x=0.\end{array}$$

3.3 有限点态最大值

若

$$f(x)=\underset{i=1,\dots ,m}{max}{f}_i(x),$$

且 $f_i$ 凸可微，则

$$\partial f(x)=\mathrm{conv}\{\mathrm{\nabla }{f}_i(x):i\in I(x)\},$$

其中 active set

$$I(x)=\{i:f_i(x)=f(x)\}.$$

这条是 piecewise linear / hinge loss / max-of-affine 问题的核心。

3.4 指示函数与 normal cone

闭凸集 $C$ 的 indicator：

$$I_C(x)=\{\begin{array}{ll}0,& x\in C,\\ +\mathrm{\infty },& x\notin C.\end{array}$$

其次微分是 normal cone：

$$\partial I_C(x)=N_C(x)=\{g:g^T(y-x)\le 0,\mathrm{\forall }y\in C\}.$$

投影问题的最优性条件也会用到它。

4. 次微分运算法则

常用规则：

规则	形式
非负数乘	$\partial (\alpha f)(x)=\alpha \partial f(x),\alpha >0$
加法	$\partial (f_1+f_2)(x)=\partial f_1(x)+\partial f_2(x)$（适当正则条件下）
仿射复合	$g(x)=f(Ax+b)\Rightarrow \partial g(x)=A^T\partial f(Ax+b)$
最大值	$\partial \underset{i}{max}{f}_i(x)=\mathrm{conv}\bigcup _{i\in I(x)}\partial f_i(x)$

做题时不要每次回到定义硬推；优先识别“范数、最大值、indicator、仿射复合、加法”。

5. 不可微最优性条件

5.1 无约束

若 $f$ 凸，则

$$x^{\ast }\in \arg minf⟺0\in \partial f(x^{\ast }).$$

这就是 $\mathrm{\nabla }f(x^{\ast })=0$ 的 nonsmooth 版本。

5.2 约束问题

若

$$min{f}_0(x)\text{s.t.}{f}_i(x)\le 0,i=1,\dots ,m,$$

其中 $f_i$ 凸且满足 Slater，则 KKT 写成：

$$f_i(x^{\ast })\le 0,{\lambda }_i^{\ast }\ge 0,{\lambda }_i^{\ast }{f}_i(x^{\ast })=0,$$$$0\in \partial f_0(x^{\ast })+\sum _i{\lambda }_i^{\ast }\partial f_i(x^{\ast }).$$

和 smooth KKT 的区别只有一处：梯度方程变成次微分包含式。

5.3 投影的最优性条件

投影

$${\mathrm{\Pi }}_C(x)=\arg \underset{y\in C}{min}\frac{1}{2}\parallel y-x{\parallel }^2$$

满足

$$x-{\mathrm{\Pi }}_C(x)\in N_C({\mathrm{\Pi }}_C(x)).$$

等价于

$$(x-{\mathrm{\Pi }}_C(x){)}^T(z-{\mathrm{\Pi }}_C(x))\le 0,\mathrm{\forall }z\in C.$$

这也是投影非扩张性和投影次梯度法收敛分析的基础。

6. 投影次梯度法

问题：

$$\underset{x\in X}{min}f(x),$$

其中 $X$ 闭凸，$f$ 凸但可能不可微。

算法：

$$y_{k+1}=x_k-{\alpha }_k{g}_k,g_k\in \partial f(x_k),$$$$x_{k+1}={\mathrm{\Pi }}_X(y_{k+1}).$$

若 $X={\mathbb{R}}^n$，投影步省略。

步长策略

步长	形式	结论
常数步长	${\alpha }_k=\alpha$	只能收敛到一个误差邻域
常数步长长度	${\alpha }_k=\gamma /|g_k|$	控制每步移动长度
diminishing	${\alpha }_k\to 0,\sum _k{\alpha }_k=\mathrm{\infty }$	可收敛，典型 $O(1/\sqrt{k})$
Polyak	${\alpha }_k=(f(x_k)-f^{\ast })/|g_k{|}^2$	若知道 $f^{\ast }$，理论上更好

关键认知：次梯度方向不一定是下降方向，所以不能像 GD 那样期待 $f(x_{k+1})\le f(x_k)$。

7. 收敛分析核心

讲义假设：

• $f$ 凸，$\mathrm{dom}f={\mathbb{R}}^n$；
• $f^{\ast }>-\mathrm{\infty }$，且存在最优解 $x^{\ast }$；
• $\parallel g\parallel \le G,\mathrm{\forall }g\in \partial f(x)$；
• $R=\parallel x_1-x^{\ast }\parallel$。

投影基本不等式：

$$\parallel {\mathrm{\Pi }}_X(y)-x{\parallel }^2+\parallel y-{\mathrm{\Pi }}_X(y){\parallel }^2\le \parallel y-x{\parallel }^2,\mathrm{\forall }x\in X.$$

次梯度法的主界：

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+\sum _{i=1}^k{\alpha }_i^2\parallel g_i{\parallel }^2}{2\sum _{i=1}^k{\alpha }_i}.$$

其中

$$f_{\mathrm{best}}^k=\underset{i=1,\dots ,k}{min}f(x_i).$$

7.1 一般凸：$O(1/\sqrt{k})$

若取 ${\alpha }_i=R/(G\sqrt{i})$，可得

$$f_{\mathrm{best}}^k-f^{\ast }=O\left(\frac{RG\log k}{\sqrt{k}}\right).$$

若用更精细的固定 horizon 步长，可得到

$$O\left(\frac{RG}{\sqrt{k}}\right).$$

7.2 强凸：$O(1/k)$

若 $f$ 是 $\mu$-强凸，取

$${\alpha }_s=\frac{2}{\mu (s+1)},$$

则

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{2G^2}{\mu (k+1)}.$$

这比一般凸情形快，但仍比 smooth 强凸 GD 的线性收敛慢。

8. Polyak 步长与交替投影

Polyak 步长：

$${\alpha }_k=\frac{f(x_k)-f^{\ast }}{\parallel g_k{\parallel }^2}.$$

它直接最小化距离递推中的右侧：

$$\parallel x_{k+1}-x^{\ast }{\parallel }^2\le \parallel x_k-x^{\ast }{\parallel }^2-2{\alpha }_k(f(x_k)-f^{\ast })+{\alpha }_k^2\parallel g_k{\parallel }^2.$$

缺点：通常不知道 $f^{\ast }$。

交替投影的联系：

若要找 $x\in {\cap }_{j=1}^m{C}_j$，可考虑

$$f(x)=\underset{j}{max}{d}_j(x),d_j(x)=\mathrm{dist}(x,C_j).$$

对最远集合 $C_j$ 的距离函数取次梯度，配 $f^{\ast }=0$ 的 Polyak 步长，会得到

$$x_{k+1}=P_{C_j}(x_k).$$

这就是“每次投影到最远集合”的 alternating projections 版本。

9. Mirror descent（了解）

投影次梯度法可写成

$$x_{t+1}=\arg \underset{x\in X}{min}\{\frac{1}{2}\parallel x-x_t{\parallel }^2+{\alpha }_t{g}_t^{T}x\}.$$

Mirror descent 把欧氏距离换成 Bregman distance：

$$D_h(y,x)=h(y)-h(x)-\mathrm{\nabla }h(x{)}^T(y-x).$$

更新：

$$x_{t+1}=\arg \underset{x\in X}{min}\{\frac{1}{{\alpha }_t}{D}_h(x,x_t)+g_t^{T}x\}.$$

在 simplex 上常用 negative entropy：

$$h(x)=\sum _i{x}_i\log x_i,$$

对应的 Bregman distance 是 KL divergence。它在概率单纯形、在线学习、稀疏分布优化中比欧氏投影更自然。

10. 作业题型对照

作业/题型	典型问法	考点
次微分计算	求 $|x|$、$\Vert x{\Vert }_2$、$\underset{i}{max}(a_i^{T}x+b_i)$、indicator 的 $\partial f$	直接套常见次微分和最大值规则
最优性条件	证明某点最优或求 minimizer	写 $0\in \partial f(x^{\ast })$
nonsmooth KKT	含不可微目标/约束的凸问题	把 stationarity 写成 $0\in \partial L_x$
投影性质	证明投影不等式或 normal cone 条件	用 $x-{\mathrm{\Pi }}_C(x)\in N_C({\mathrm{\Pi }}_C(x))$
次梯度法收敛	推 $O(1/\sqrt{k})$ 或 $O(1/k)$	距离递推 + telescoping
Polyak 步长	已知 $f^{\ast }$ 时选步长	代入距离递推并最小化右侧
Mirror descent	simplex / KL divergence	识别 Bregman distance，不要强行欧氏投影
A11.1(a)	$f(x)=|Ax-b{|}_2+|x{|}_2$，且 $A{x}_0-b=0,x_0\ne 0$	范数在 0 点的次微分 + 仿射复合 + 加法规则：$\partial |Ax-b|=A^T\{q:|q|\le 1\}$
A11.1(b)	$f(x)=\underset{y}{inf}|Ay-x{|}_{\mathrm{\infty }}$ 的次微分	把问题看成到 $\mathrm{range}(A)$ 的 ${\ell }_{\mathrm{\infty }}$ 距离；用 active set、$\partial |\cdot {|}_{\mathrm{\infty }}$ 和 $A^{T}s=0$
A11.2	复合函数 $f(x)=h(f_1(x),\dots ,f_m(x))$ 的次梯度	$h$ 对每个分量单调不减，取 $z\in \partial h$ 且 $z_i\ge 0$，构造 $g=\sum _i{z}_i{g}_i$
A11.3	Polyak 步长 + error bound	用 ${\alpha }_k=(f(x_k)-f^{\ast })/|g_k{|}^2$ 代入距离递推；若 $f(x)-f^{\ast }\ge \mu \mathrm{dist}(x,X^{\ast })$ 且 $|g_k|\le L$，得到线性距离收缩
A11.4	非负约束二次规划的投影梯度 support identification	投影到 ${\mathbb{R}}_{+}^n$；利用收敛 $x_n\to x^{\ast }$ 和严格互补，证明非支撑坐标有限步归零并保持为零

11. 解题招式

招式 1：求次微分先拆结构

例如

$$f(x)=\parallel Ax-b{\parallel }_1+\lambda \parallel x{\parallel }_2$$

先拆成：

• $\parallel Ax-b{\parallel }_1=\sum _i|a_i^{T}x-b_i|$：绝对值 + 仿射复合；
• $\lambda \parallel x{\parallel }_2$：范数；
• 最后用加法规则。

招式 2：证明最优只写包含式

不可微凸问题不要找 $\mathrm{\nabla }f=0$，而是写：

$$0\in \partial f(x^{\ast }).$$

如果有约束 $x\in C$，写成

$$0\in \partial f(x^{\ast })+N_C(x^{\ast }).$$

招式 3：收敛证明固定模板

1. 用投影非扩张性：$$\parallel x_{k+1}-x^{\ast }{\parallel }^2\le \parallel x_k-{\alpha }_k{g}_k-x^{\ast }{\parallel }^2.$$
2. 展开平方。
3. 用次梯度不等式：$$g_k^T(x_k-x^{\ast })\ge f(x_k)-f^{\ast }.$$
4. 累加 telescoping。
5. 用 $f_{\mathrm{best}}$ 把加权和变成最好函数值。

12. 自检清单

• [ ] 次梯度定义能不看书写出来吗？
• [ ] $\partial |x|$、$\partial \parallel x{\parallel }_2$ 在 0 点分别是什么？
• [ ] $\partial \parallel x{\parallel }_{\mathrm{\infty }}$ 如何用 active set 写？
• [ ] $\partial \underset{i}{max}{f}_i(x)$ 为什么只看 active indices？
• [ ] 仿射复合 $\partial \parallel Ax-b\parallel$ 的 $A^T$ 是从哪里来的？
• [ ] $x^{\ast }$ 最优的条件是 $0\in \partial f(x^{\ast })$，能用定义证明吗？
• [ ] nonsmooth KKT 的 stationarity 怎么写？
• [ ] 投影最优性条件和 normal cone 的关系能写出吗？
• [ ] 次梯度法为什么不保证每步下降？
• [ ] Polyak 步长在已知 $f^{\ast }$ 时为什么自然？
• [ ] error bound 如何把 Polyak 步长从次线性推到线性距离收缩？
• [ ] $O(1/\sqrt{k})$ 的主界能推出来吗？
• [ ] 强凸次梯度为什么能到 $O(1/k)$，但不是线性？

13. 常见陷阱

1. 次梯度不是唯一的：不可微点通常是一整个集合。
2. 次梯度方向不一定下降：这和梯度下降非常不同。
3. $\partial f(x)$ 可能为空：尤其在 domain 边界或非闭情形，要注意假设。
4. 最大值规则只取 active functions：非 active 的函数不参与当前次微分。
5. 约束问题别忘 normal cone：$\underset{x\in C}{min}f(x)$ 的条件是 $0\in \partial f(x)+N_C(x)$。
6. 常数步长不能保证精确收敛：通常只到误差邻域。
7. Mirror descent 的 $D_h$ 不是真正距离：一般不对称，也不满足三角不等式。

14. 接下来怎么学

次梯度法很通用但慢。下一章 10_近端梯度法 会利用 composite structure $f=g+h$：对 smooth 的 $g$ 用梯度，对 nonsmooth 但 simple 的 $h$ 用 prox，从而把速度提升回和梯度下降同阶。