数学优化理论 · 第28课

四周阶段测验与综合复盘:从凸性到近端分裂

2026-11-16|第4周·第7天|讲授与复盘约18分钟,自测另计

今天是前四周的阶段测验,不引入新的算法家族。目标是检查能否把一个优化问题完整地连接起来:

几何与函数假设 → 最优性条件 → 算法迭代 → 收敛不等式 → 可验证的最优性证书。

这五步不能互相替代:凸性不等于光滑性,KKT 必要性不等于充分性,算法残差趋零不自动等于全局最优,强对偶也不自动代表对偶最优乘子一定达到。

一、四周知识地图

周次 核心主题 必须能独立写出的结论
第1周 凸集、分离、凸函数、严格/强凸、Smooth 凸函数一阶下界;L-Smooth 二次上界;强凸给出二次增长
第2周 约束资格条件、KKT、拉格朗日对偶、鞍点与灵敏度 活跃集与互补松弛;Slater/LICQ/MFCQ 的不同角色;弱对偶与 KKT 证书
第3周 GD、AGD、PL、线搜索 GD 的 O(1/K);AGD 的 O(1/K²);步长和曲率假设不可省略
第4周 投影、Prox、Moreau、PGD/FISTA、FB/DRS 近端最优性包含式;投影与法锥;固定点和 averaged 算子收敛

复盘时,先判断问题属于哪一类,再选择可用定理:

  • 几何: 可行域是否凸?分离超平面或法锥能否描述边界?
  • 函数: 是否凸、μ-强凸、L-Smooth?目标是否下有界?
  • 约束: 哪些约束活跃?是否有 Slater、LICQ 或 MFCQ?
  • 算法: 是梯度步、加速步、Prox、投影,还是算子分裂?
  • 结论: 证明的是点收敛、函数值收敛、残差收敛,还是原始—对偶间隙?

二、统一不等式:凸性、Smooth 与强凸

对可微凸函数 f,任意 x,y 满足全局切线下界:

[ f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle. \tag{1} ]

若梯度是 L-Lipschitz,则有下降引理:

[ f(y)\le f(x)+\langle\nabla f(x),y-x\rangle +\frac L2|y-x|^2. \tag{2} ]

若 f 还具有 μ-强凸性,则:

[ f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle +\frac\mu2|y-x|^2. \tag{3} ]

式 (1) 是凸性给出的下界,式 (2) 是 Smooth 给出的上界,式 (3) 是强凸给出的更强下界。它们承担不同任务:

  • 凸性把一阶驻点转成全局最优性;
  • Smooth 控制一步移动时函数值最多上升多少;
  • 强凸给出唯一最优点和二次增长,并支持更快的收敛率。

不要混淆严格凸与强凸。 例如 (f(x)=x^4) 在实数轴严格凸,但 (f’‘(0)=0),不存在全局正的强凸模量 (\mu)。

三、GD 与 AGD:速度结论从哪里来?

设 f 凸、L-Smooth,且最优点 (x^*) 存在。梯度下降取

[ x_{k+1}=x_k-\frac1L\nabla f(x_k). \tag{4} ]

3.1 一步下降

把 (y=x-\nabla f(x)/L) 代入式 (2):

[ \begin{aligned} f(x_{k+1}) &\le f(x_k) -\frac1L|\nabla f(x_k)|^2 +\frac L2\frac1{L^2}|\nabla f(x_k)|^2
&=f(x_k)-\frac1{2L}|\nabla f(x_k)|^2. \end{aligned} \tag{5} ]

所以函数值单调不增。但要得到全局最优值误差,还需要凸性。将凸性不等式与式 (2) 合并,可得

[ f(x_{k+1})-f^* \le \frac L2 \left(|x_k-x^|^2-|x_{k+1}-x^|^2\right). \tag{6} ]

对 (k=0,\ldots,K-1) 求和,右侧望远镜消去。又因为 (f(x_k)) 单调不增,

[ \boxed{ f(x_K)-f^* \le \frac{L|x_0-x^*|^2}{2K}. } \tag{7} ]

这就是凸光滑 GD 的 (O(1/K)) 函数值误差界。它不是只靠“梯度步长足够小”就能得到的:证明同时用了 Smooth、凸性、步长 (1/L) 和最优点存在。

3.2 加速为什么能到 O(1/K²)?

Nesterov/FISTA 类方法引入外推点与辅助序列。典型参数递推为

[ t_0=1,\qquad t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}2, ]

并有 (t_k) 约按 (k/2) 增长。通过构造势函数,将函数值误差乘以 (t_k^2),再与一个距离平方相加,证明势函数不增,最终得到

[ \boxed{ f(x_K)-f^* \le \frac{2L|x_0-x^*|^2}{(K+1)^2}. } \tag{8} ]

复合问题 (F=f+h) 中,若 f 凸且 L-Smooth、h 真下半连续凸、最优点存在、近端步精确计算,则 FISTA 对应得到 (O(1/K^2)) 函数值界。回溯版本还需要遵守已经证明的曲率更新规则,例如非递减且有统一上界的接受曲率。

重要边界: FISTA 的加速界不代表原始目标值每一步都单调下降;也不能把凸情形的 (O(1/K^2)) 直接搬到非凸目标。

四、KKT 与对偶:最优性证书如何闭合?

考虑

[ \min_x f(x),\qquad g_i(x)\le0,\quad Ax=b. ]

拉格朗日函数为

[ L(x,\lambda,\nu) =f(x)+\sum_i\lambda_i g_i(x)+\nu^\top(Ax-b). ]

KKT 条件包括:

[ \begin{cases} g_i(x^)\le0,\quad Ax^=b & \text{原始可行},
\lambda_i^\ge0 & \text{对偶可行},
\nabla f(x^
)+\sum_i\lambda_i^\nabla g_i(x^)+A^\top\nu^=0 & \text{驻点},
\lambda_i^
g_i(x^*)=0 & \text{互补松弛}. \end{cases} \tag{9} ]

定义活跃集

[ \mathcal A(x^)={i:g_i(x^)=0}. ]

互补松弛给出两个不同方向:

  • 若 (g_i(x^)<0),则 (\lambda_i^=0);
  • 若 (g_i(x^)=0),只能推出乘子允许非零,不能推出 (\lambda_i^>0)。

4.1 必要性与充分性不能混为一谈

  • 在光滑非线性规划中,局部最优点满足 LICQ 或 MFCQ 等适当资格条件时,可保证 KKT 乘子存在。LICQ 还给出乘子唯一性。
  • 在标准凸优化中,Slater 严格可行条件通常用于保证强对偶与最优乘子存在。
  • 若一个凸问题的候选点和乘子已经满足 KKT,则 KKT 是全局最优的充分证书;这一步充分性证明本身不需要先假设 Slater。

4.2 弱对偶的一行证明

对任意对偶可行 (\lambda\ge0,\nu) 定义

[ q(\lambda,\nu)=\inf_x L(x,\lambda,\nu). ]

对任意原始可行 x:

[ \boxed{ q(\lambda,\nu) \le L(x,\lambda,\nu) =f(x)+\sum_i\lambda_i g_i(x) \le f(x). } \tag{10} ]

因此 (q(\lambda,\nu)\le p^*)。如果同时有原始可行上界 (f(\hat x)) 与对偶下界 q,就能用 (f(\hat x)-q) 认证最优值间隙。若 (\hat x) 不可行,就不能把这个差当作有效的原始—对偶证书。

五、Prox、投影与 Moreau:把约束和非光滑性放进一个算子

对真、下半连续、凸函数 h:

[ \operatorname{prox}_{\gamma h}(v) =\arg\min_z\left{h(z)+\frac1{2\gamma}|z-v|^2\right}. ]

其最优性包含式为

[ \boxed{ 0\in\partial h(p)+\frac{p-v}{\gamma}, \qquad p=\operatorname{prox}_{\gamma h}(v). } \tag{11} ]

若 (h=\delta_C),即 h 是闭凸集 C 的指标函数,则

[ \operatorname{prox}_{\gamma\delta_C}(v)=\Pi_C(v), \qquad v-\Pi_C(v)\in N_C(\Pi_C(v)). \tag{12} ]

这里的法锥使用约定

[ N_C(p)={u:\langle u,z-p\rangle\le0,\ \forall z\in C}. ]

所以投影不是另一个孤立技巧,而是 Prox 在集合指标函数上的特例。

Moreau envelope 定义为

[ e_\gamma h(v)= \min_z\left{h(z)+\frac1{2\gamma}|z-v|^2\right}, ]

并且即使 h 不可微,(e_\gamma h) 仍可微:

[ \boxed{ \nabla e_\gamma h(v) =\frac{v-\operatorname{prox}_{\gamma h}(v)}{\gamma}. } \tag{13} ]

对复合目标 (F=f+h),近端梯度迭代为

[ x_{k+1}=\operatorname{prox}_{\eta h} (x_k-\eta\nabla f(x_k)). \tag{14} ]

若 f 凸且 L-Smooth、h 真下半连续凸、最优点存在、精确 Prox 且 (0<\eta\le1/L),则有

[ F(x_K)-F^* \le\frac{|x_0-x^*|^2}{2\eta K}. \tag{15} ]

FISTA 在相应凸复合假设下将函数值界加速到 (O(1/K^2))。Forward–Backward 与 Douglas–Rachford 则把这些更新写成 resolvent/averaged 算子的不动点迭代;固定点非空是相应收敛结论不可省略的条件。

六、两步数值演算:复合目标的近端梯度

考虑

[ F(x)=\frac12(x-5)^2+2|x|+\delta_{[0,4]}(x). ]

平滑部分 (f(x)=\frac12(x-5)^2),所以 (L=1)。非光滑部分的近端算子为截断软阈值。取 (\eta=1/4,x_0=0):

[ x_{k+1}= \min\left{4,\max\left{0, x_k-\frac14(x_k-5)-\frac12\right}\right}. ]

步 梯度步输入 v Prox 输出 (x_k) 目标值 (F(x_k))
0 — 0 12.5000
1 1.2500 0.7500 10.5313
2 1.8125 1.3125 9.4238
最优 — 3.0000 8.0000

最优点可直接由正半轴上的一阶条件 (x-5+2=0) 得到 (x^*=3)。本例展示的是算法如何逐步逼近最优点,不应把两步迭代误当成已经收敛。

七、典型失败边界

错误推断 反例或正确边界
严格凸就一定强凸 (x^4) 严格凸,但不存在全局正强凸模量
步长取到 (2/L) 仍保证 GD 收敛 (f(x)=x^2/2,L=1,\eta=2) 时 (x_{k+1}=-x_k),目标值不降
活跃约束就必须有正乘子 本课 Lv4 的 KKT 综合题会检验这一边界,但课堂不提前公布解答
非凸问题的一阶驻点就是全局最优 (f(x)=1-\cos x) 在 (x=\pi) 梯度为零,却是极大点
凸性自动保证有限 KKT 乘子存在 (\min_x x) s.t. (x^2\le0) 的唯一可行最优点为 0,但驻点式变成 (1+2\lambda\cdot0=0),无有限乘子;Slater 失败
DRS 两个 Prox 可计算就必然收敛 还需相应最优性分解/固定点存在;两个互不相交闭凸集的指标函数会使 DRS 主变量线性漂移

八、四周关系图

flowchart TD
  A["凸集与分离"] --> B["凸性 / 强凸 / Smooth"]
  B --> C["一阶不等式与下降引理"]
  C --> D["GD: O(1/K)"]
  C --> E["AGD/FISTA: O(1/K²)"]
  A --> F["法锥 / 支撑超平面"]
  F --> G["KKT 与活跃集"]
  G --> H["资格条件: Slater / LICQ / MFCQ"]
  G --> I["拉格朗日对偶与弱对偶"]
  B --> J["Prox / Moreau"]
  J --> K["指标函数 = 投影"]
  K --> L["PGD / Forward–Backward"]
  J --> M["Resolvent / DRS"]
  L --> N["固定点与收敛证书"]
  M --> N

九、四级阶段测验(总分 100)

前三题为客观题,第四题为开放证明与建模题。请先独立作答;本课不附标准答案,独立 JSON 中的答案与解析不要提前查看。 每题标题注明等级、知识点与预计耗时。

Lv1|概念辨析:凸性、Smooth 与 KKT|15 分|预计 2 分钟

在下列陈述中,哪一项在其所述假设下必然成立?

  • A. 对任意闭凸集 C 上的约束最优点 x^,必有 \nabla f(x^)=0。
  • B. 若 f 可微且 \nabla f 为 L-Lipschitz,则对任意 x,y 有 f(y)\le f(x)+\langle\nabla f(x),y-x\rangle+\frac L2|y-x|^2。
  • C. 严格凸必推出存在全局 \mu>0 的强凸常数。
  • D. KKT 中 g_i(x^)=0 必推出对应乘子 \lambda_i^>0。

提示:区分约束最优性、Smooth 的二次上界、严格凸与强凸,以及互补松弛的逻辑方向。

Lv2|数值计算:两步近端梯度|20 分|预计 4 分钟

考虑 [ f(x)=\frac12(x-5)^2,\qquad h(x)=2|x|+\delta_{[0,4]}(x), ] 其中 \delta_{[0,4]} 在区间 [0,4] 上为 0、区间外为 +\infty。已知 L=1,取近端梯度步长 \eta=\frac14、初值 x_0=0: [ x_{k+1}=\operatorname{prox}{\eta h}\bigl(x_k-\eta f’(x_k)\bigr). ] 对 v\ge0,有 [ \operatorname{prox}{\eta h}(v)=\min{4,\max{0,v-2\eta}}. ] 连续执行两步,求 x_2。只填写数值,保留四位小数。

提示:先算 v_k=x_k−η(x_k−5),再减去 2η,并检查结果是否落在 [0,4]。

Lv3|反例判断:梯度下降步长边界|25 分|预计 3 分钟

考虑 f(x)=\frac12x^2(其梯度 Lipschitz 常数 L=1),从 x_0=1 使用普通梯度下降 [ x_{k+1}=x_k-\eta\nabla f(x_k) ] 并取 \eta=2。哪一项正确?

  • A. x_k 线性收敛到 0,因为 η=2/L 是允许的严格收敛步长。
  • B. x_k=(-1)^k,目标值恒为 1/2;迭代不收敛,说明端点 η=2/L 不能被误当成一般收敛保证。
  • C. x_1=0,因此一步到达全局最优点。
  • D. x_k 每步严格增大并趋于无穷。

提示:先把梯度写成 x_k,得到一个标量线性递推;注意端点与开区间步长条件的区别。

Lv4|综合证明与建模:GD、Prox、KKT、对偶|40 分|预计 13 分钟

设所有变量属于有限维欧氏空间。完成 A—D,写出关键假设与推导步骤。

A(10 分):Smooth 与 GD。 设 f 凸、可微且 L-Smooth,最优点 x^* 存在。由下降引理证明 [ f(x-\nabla f(x)/L)\le f(x)-\frac{1}{2L}|\nabla f(x)|^2. ] 进一步利用凸性和平方距离恒等式证明 [ f(x_K)-f^\le\frac{L|x_0-x^|^2}{2K}. ]

B(10 分):Prox、投影与 Moreau。 对真、下半连续、凸函数 h,令 p=\operatorname{prox}{\gamma h}(v)。从近端子问题的一阶最优性写出包含式。再令 h=\delta_C,其中 C 为非空闭凸集,推导投影条件 v-p\in N_C(p),并写出 Moreau envelope [ e\gamma h(v)=\min_z\left{h(z)+\frac{1}{2\gamma}|z-v|^2\right} ] 的梯度公式。

C(12 分):KKT、活跃约束与零乘子。 求解 [ \begin{aligned} \min_{x_1,x_2}\quad& \frac12[(x_1-3)^2+(x_2-2)^2]+|x_1|+2|x_2|
\text{s.t.}\quad&x_1+x_2\le2. \end{aligned} ] 给出最优点、活跃集、一个合法的非光滑 KKT 次梯度与乘子,并验证驻点、原始/对偶可行及互补松弛。解释本例为何说明“活跃不必对应正乘子”。

D(8 分):对偶与理论边界。 写出拉格朗日对偶函数 q(\lambda,\nu),用不等式证明弱对偶 q(\lambda,\nu)\le p^*。说明 Slater、LICQ、MFCQ 各自主要保证什么;最后比较凸 L-Smooth 情形下 GD 的 O(1/K) 与 AGD/FISTA 的 O(1/K^2) 保证,并写明不能省略的关键假设。

提示:A:把 x^+=x−∇f(x)/L 代入下降引理,再将目标差改写成相邻平方距离之差。B:使用 0∈∂h(p)+(p−v)/γ;指标函数的次微分就是法锥。C:先求可分目标的无约束最优点,再检查耦合约束;在 x_2=0 处使用区间次微分。D:从 q=inf L≤L(可行点)≤f(可行点) 出发,分清凸问题的 Slater 与局部非线性规划的 LICQ/MFCQ。

十、下一讲与评分规则

第29课|2026-11-17|第5周第1天:坐标下降——循环、随机与 Gauss–Southwell 选择。 从单坐标子问题出发,比较循环坐标、随机坐标与最大残差/最大梯度分量选择,重点区分可分强凸目标下的线性收敛定理与一般非凸情形中的驻点保证。

作答后按 15/20/25/40 分逐题评分并给出错因。总分 80 分及以上:进入第5周;60–79 分:补充最薄弱模块的推导例题;低于60分:优先复习凸性/Smooth 不等式、KKT 互补松弛与近端最优性,再做针对性训练。阶段测验成绩不改变日期与课号。