数学优化理论 · 第 6 课
强凸性、Smooth 与梯度映射:如何把 KKT 变成收敛保证?
2026 年 10 月 25 日|第 1 周第 6 课|预计 18 分钟
核心问题: 强凸(Strong Convexity)和光滑(Smoothness)分别保证什么?有约束最优点的梯度往往不为零,那么优化算法究竟应该让什么量趋近于零?
前五课已经建立凸性、次梯度、欧氏投影、法锥、KKT 和 Slater。今天将它们连成一条更实用的路径:曲率假设 → 合法的下降步骤 → 可计算的最优性残差 → 收敛速度。本课不重新推导 Slater,而是重点填补“最优性条件”和“算法真正收敛”之间的空白。
学习目标: 区分 μ-强凸与 L-Smooth;推导无约束 GD 的线性函数值收敛;用投影梯度映射检验边界最优性;证明 PGD 的下降性质与在更强条件下的距离线性收缩;手算二维实例并核对 KKT。
一、问题、符号与假设
考虑约束优化
[ \min_{x\in C}f(x),\qquad C\subseteq\mathbb R^d. ]
默认 C 非空、闭、凸,投影为 (\Pi_C)。设 (f) 在包含 C 的凸开集上二阶连续可微,且存在常数 (0<\mu\le L),满足
[ \boxed{\mu I\preceq\nabla^2f(x)\preceq LI.}\tag{1} ]
这是本课用于证明线性收缩的较强假设。证明某些单步下降结论时,只需要梯度 L-Lipschitz,不要求强凸;证明一般凸 PGD 的函数值界时需要凸性、L-Smooth、最优解存在以及合适步长。
为避免混淆:(\mu) 描述曲率下界;(L) 描述曲率上界。条件数 (\kappa=L/\mu\ge1),越大通常意味着问题越病态。
二、从 Hessian 推出两条关键不等式
令 (d=y-x)。沿直线 (x+td) 对目标做积分形式的二阶展开:
[ f(x+d)=f(x)+\nabla f(x)^\top d+ \int_0^1(1-t)d^\top\nabla^2f(x+td)d\,dt. ]
因为式 (1) 意味着
[ \mu|d|^2\le d^\top\nabla^2 f(x+td)d\le L|d|^2, ]
又有 (\int_0^1(1-t)dt=1/2),得到
[ \boxed{f(y)\ge f(x)+\nabla f(x)^\top(y-x)+\frac\mu2|y-x|^2,}\tag{2} ]
[ \boxed{f(y)\le f(x)+\nabla f(x)^\top(y-x)+\frac L2|y-x|^2.}\tag{3} ]
式 (2) 是强凸下界:函数不能比指定二次曲面更平。式 (3) 是 Descent Lemma 的上界:梯度的一阶预测不会偏差得太夸张。它们作用不同,不能互相替代。
强凸的一个结论是最优解唯一。 假设两个不同的可行点 (x_1,x_2) 都最优。对中点使用强凸不等式,会得到函数值严格低于共同最优值,产生矛盾。因而 C 上最多一个最优解。在本课全局强凸、C 闭非空的条件下,最优解也存在。
两个反例帮助记忆: (f(t)=t^4+\tfrac12t^2) 的二阶导数 (12t^2+1\ge1),所以强凸,但梯度不是全局 Lipschitz;而 (f(x,y)=\tfrac12x^2) 是 L-Smooth 凸函数,却不强凸,因为 y 方向完全平坦。单有 L-Smooth 甚至不能保证凸,例如 (f(t)=-t^2/2)。
| 性质 | 控制什么 | 不自动保证什么 |
|---|---|---|
| (\mu>0) 强凸 | 最优解唯一、曲率正下界 | 梯度全局 Lipschitz |
| (L)-Smooth | 梯度变化速度、下降步的上界 | 凸性、最优解唯一 |
| 二者同时成立 | 有条件的线性收敛分析 | 任意步长都稳定 |
三、先看无约束 GD:线性收敛从哪里来?
暂时令 (C=\mathbb R^d),取梯度下降步长 (\eta=1/L):
[ x_{k+1}=x_k-\frac1L\nabla f(x_k). ]
用式 (3),记 (g=\nabla f(x_k)),立刻得到
[ f(x_{k+1})\le f(x_k)-\frac1{2L}|g|^2.\tag{4} ]
还差一步:怎样把梯度范数和函数值误差联系起来?令无约束最优点为 (x^*),由式 (2):
[ f(x^)\ge f(x)+g^\top(x^-x)+\frac\mu2|x^*-x|^2. ]
右侧关于 (u=x^*-x) 的后两项不小于其在所有 u 上的最小值 (-|g|^2/(2\mu))。故
[ \boxed{|g|^2\ge2\mu[f(x)-f(x^*)].}\tag{5} ]
将式 (5) 代入式 (4):
[ f(x_{k+1})-f^\le(1-\mu/L)[f(x_k)-f^]. ]
逐次应用:
[ \boxed{f(x_k)-f^\le(1-1/\kappa)^k[f(x_0)-f^].}\tag{6} ]
这就是线性(几何)收敛:误差每一步至多乘固定的、严格小于 1 的因子。它不是说计算时间与 k 呈线性关系。
但这里有一个不容忽略的前提:梯度步 (x-\nabla f(x)/L) 是可执行的无约束点。 有约束时它可能离开 C,不能把上述证明不加修改地搬过去。
四、约束最优点:梯度不必为零,梯度映射应为零
设一步投影梯度下降(PGD)为
[ x^+=\Pi_C(x-\eta\nabla f(x)). ]
定义梯度映射(gradient mapping)
[ \boxed{G_\eta(x)=\frac{x-\Pi_C(x-\eta\nabla f(x))}{\eta} =\frac{x-x^+}{\eta}.}\tag{7} ]
对固定 (\eta>0),有 (|G_\eta(x)|=|x-x^+|/\eta);它衡量在投影保护下这一步还想移动多少。无约束时 (\Pi_C) 为恒等映射,(G_\eta(x)=\nabla f(x))。
回忆投影定理:当 (p=\Pi_C(z)) 时,
[ (z-p)^\top(y-p)\le0,\qquad\forall y\in C. ]
把 (p=x)、(z=x-\eta\nabla f(x)) 代入,可得
[ G_\eta(x)=0 \iff \nabla f(x)^\top(y-x)\ge0,\quad\forall y\in C. ]
对于凸可微 f,右侧就是 C 上全局最优的充要条件,因此
[ \boxed{x=x^*\iff G_\eta(x)=0\quad(x\in C,\ \eta>0).}\tag{8} ]
更一般的非凸可微 f 中,(G_\eta(x)=0) 只能当作一阶驻点条件,不能当作全局最优证书。
与 KKT 衔接: 若 C 由仿射不等式 (a_i^\top x-b_i\le0) 给出,则 (-\nabla f(x^)\in N_C(x^)) 等价于存在非负活跃约束乘子,使
[ \nabla f(x^)+\sum_i\lambda_i a_i=0,\quad \lambda_i(a_i^\top x^-b_i)=0. ]
严格不活跃的约束乘子为零;活跃约束的乘子可以为零。这也是上一课 Slater 与乘子讨论的落脚点。
五、PGD 为什么下降?为什么仍要检查步长?
记 (d=x^+-x=-\eta G_\eta(x))。因为 x 可行,在投影不等式中选 (y=x),整理得到
[ \boxed{\nabla f(x)^\top d\le-\frac1\eta|d|^2.}\tag{9} ]
再使用式 (3) 的光滑上界:
[
\begin{aligned}
f(x^+)
&\le f(x)+\nabla f(x)^\top d+\frac L2|d|^2
&\le f(x)-\left(\frac1\eta-\frac L2\right)|d|^2.
\end{aligned}
]
所以
[ \boxed{f(x^+)\le f(x)-\eta(1-L\eta/2)|G_\eta(x)|^2.}\tag{10} ]
当 (0<\eta<2/L) 且梯度映射非零时,函数值严格下降;通常取更保守的 (\eta\le1/L),得到至少 (\eta|G_\eta(x)|^2/2) 的下降量。
这里的下降证明只用 L-Smooth 和闭凸 C,并没有用强凸。 即使 f 非凸,在这些前提下仍可保证单步下降;但不能因此保证找到全局最优点。
当 f 凸、最优解存在且 (0<\eta\le1/L) 时,还可以把投影定理应用于 (y=x^*),结合凸性得到
[ f(x^+)-f^* \le \frac{|x-x^|^2-|x^+-x^|^2}{2\eta} -\frac{1-\eta L}{2\eta}|d|^2. ]
对迭代求和,利用右侧平方距离的望远镜相消与函数值单调性:
[ \boxed{f(x_T)-f^\le\frac{|x_0-x^|^2}{2\eta T}.}\tag{11} ]
这是一般凸 PGD 的 (O(1/T)) 末次迭代函数值界,还不是强凸带来的更快收敛结论。
六、为什么强凸 + Smooth 会带来 PGD 线性收缩?
先证投影的非扩张性。令 (p=\Pi_C(u))、(q=\Pi_C(v))。两次投影最优性不等式合并后有
[ |p-q|^2\le(p-q)^\top(u-v) \le|p-q|\,|u-v|. ]
所以
[ \boxed{|\Pi_C(u)-\Pi_C(v)|\le|u-v|.}\tag{12} ]
这句话很直观:投影到同一个闭凸集合,不会把两点拉得比投影前更远。
现在利用式 (1) 的 Hessian 界。对任意 (x,y\in C),沿线段积分:
[ \nabla f(x)-\nabla f(y)=A(x-y),\qquad A=\int_0^1\nabla^2f(y+t(x-y))dt. ]
因为 (\mu I\preceq A\preceq LI),矩阵 (I-\eta A) 的特征值落在 ([1-\eta L,\ 1-\eta\mu]),故
[ |(x-\eta\nabla f(x))-(y-\eta\nabla f(y))| \le\rho|x-y|, ]
其中
[ \boxed{\rho=\max{|1-\eta\mu|,\ |1-\eta L|}.}\tag{13} ]
再应用投影非扩张性。最优点 (x^*) 满足投影不动点式,所以
[ \boxed{|x_{k+1}-x^|\le\rho|x_k-x^|.}\tag{14} ]
当 (0<\eta<2/L) 时 (\rho<1),于是有距离意义下的线性收敛:
[ |x_k-x^|\le\rho^k|x_0-x^|. ]
取 (\eta=1/L) 可得 (\rho=1-\mu/L);对于本节的二阶光滑 Hessian 界,取 (\eta=2/(L+\mu)) 可得更小的上界 ((L-\mu)/(L+\mu))。
边界说明: 式 (14) 给的是迭代点距离的收缩因子,不应不经证明就把它写成完全相同因子的函数值误差收缩。在一般约束最优点,(\nabla f(x^*)) 可能非零。这里的简洁谱证明也明确使用了 C² 与 Hessian 上下界,不能原样套用于不满足这些假设的目标。
七、二维完整数值例题:两步 PGD + KKT
考虑三角形可行域
[ C={(x,y):x\ge0,\ y\ge0,\ x+y\le1} ]
和目标
[ f(x,y)=\tfrac12[(x-1.2)^2+4(y-0.8)^2]. ]
(\nabla f=(x-1.2,\ 4(y-0.8))^\top),Hessian 为 (\operatorname{diag}(1,4)),所以 (\mu=1,L=4,\kappa=4)。从 (x_0=(0,0)) 开始,用 (\eta=1/4)。
第一步: 梯度 ((-1.2,-3.2)),未投影点 (z_0=(0.3,0.8))。因为两坐标正、但和为 1.1,将其正交投影到斜边 (x+y=1):每个坐标减 (0.1/2),得到 (x_1=(0.25,0.75))。
第二步: 梯度 ((-0.95,-0.20)),未投影点 (z_1=(0.4875,0.8))。其坐标和为 1.2875,减去 (0.2875/2),得到 (x_2=(0.34375,0.65625))。
| 迭代点 | 坐标 | f(迭代点) | 是否可行 |
|---|---|---|---|
| (x_0) | (0, 0) | 2.000000 | 是 |
| (x_1) | (0.25, 0.75) | 0.456250 | 是 |
| (x_2) | (0.34375, 0.65625) | 0.407910 | 是 |
此题的最优点为 ((0.4,0.6)),函数值 0.4。如何核验?斜边约束 (x+y-1\le0) 的外法向量为 ((1,1));此点梯度为 ((-0.8,-0.8))。选择斜边的非负乘子 (\lambda=0.8),其余非负坐标约束均严格不活跃、乘子为零,便有
[ (-0.8,-0.8)+0.8(1,1)=(0,0). ]
因此 KKT 成立。由于目标强凸且约束凸,最优点唯一。
关键观察:最优点梯度不为零,但 (G_\eta(x^*)=0)。沿负梯度走会越过斜边,投影会将它拉回同一个点。这正是梯度映射比梯度范数更适合约束优化的原因。
本课关系示意图(按证明依赖顺序)
Hessian 下界 μI ──→ 强凸 ───────→ 唯一最优解
│ │
│ ▼
Hessian 上界 LI ──→ Smooth ──→ GD/PGD 下降不等式
│ │
▼ ▼
梯度步谱收缩 ──→ 投影非扩张 ──→ PGD 距离线性收缩
▲
法锥 / KKT ──→ 投影不动点 ──→ 梯度映射 Gη(x*)=0
八、失败反例与实际使用边界
反例 1:步长过大。 对无约束 (f(t)=t^2/2),有 (L=\mu=1)。若选 (\eta=3),则 (t_{k+1}=-2t_k),函数值变为原来的 4 倍。强凸也救不了任意步长。
反例 2:边界最优的梯度不为零。 对 (C=[0,\infty))、(f(t)=(t+1)^2),最优 (t^*=0),却有 (f’(0)=2)。判断约束最优要看投影不动点或法锥条件,不能单独检查 (\nabla f=0)。
反例 3:没有强凸不等于无法优化。 凸且 Smooth 的问题仍可有 (O(1/T)) 的 PGD 函数值保证;只是不能仅凭这两个前提宣称本节的统一线性收缩因子。
反例 4:投影可能很贵。 在盒、球、半空间等简单集合上可有闭式投影;对复杂约束集合,计算 (\Pi_C) 本身可能是一个大型优化问题。本课的迭代复杂度不等于真实硬件上的运行时间,必须把每步梯度和投影成本一并考虑。
另一个重要边界: 小的 (|G_\eta(x)|) 只是一个可计算的近似驻点信号,其与函数值误差/距离的定量关系仍需额外的凸性、曲率或误差界假设;非凸目标尤其不能把一阶驻点误判为全局最优。
九、四级自测|满分 100 分
首次授课不提供标准答案与解析。 前三题可以客观判分,第四题为开放证明,按推导步骤自评或交由人工、ChatGPT 批改;不能将其声称为可靠的机器自动评分。
Lv1|最优性判据与梯度映射(15 分|预计 2 分钟|单选)
考点:约束最优性、必要条件与充分条件。
设 C 是非空闭凸集,f 是凸可微函数,η>0,定义 Gη(x)=[x−Π_C(x−η∇f(x))]/η。以下哪项一定正确?
A. 如果 f 强凸,那么 C 的边界最优点必定满足 ∇f(x*)=0。
B. 对 x∈C,Gη(x)=0 当且仅当 x* 是 C 上的全局最优点。
C. 只要 f 的梯度是 Lipschitz 连续的,f 就一定是凸函数。
D. 对于任意非凸闭集,欧氏投影总是唯一且非扩张的。
可选中立提示:分别辨析约束最优点、梯度为零与投影不动点的关系;注意集合的凸性。
Lv2|三角形可行域的一步 PGD(20 分|预计 4 分钟|数值)
考点:实际梯度、欧氏投影与迭代数值。
令 f(x,y)=½[(x−1.6)²+4(y−0.9)²],C={(x,y):x≥0,y≥0,x+y≤1}。从 (x₀,y₀)=(0.2,0.2) 出发,取 η=1/4,执行一次 (x₁,y₁)=Π_C((x₀,y₀)−η∇f(x₀,y₀))。求更新后 x₁ 的数值(保留三位小数),并写出未投影点与投影约束。
可选中立提示:先由目标函数求两个梯度分量,再判断未投影点是否落在单纯形内部;检查投影是否在斜边内部。
Lv3|定理边界与线性收敛(25 分|预计 5 分钟|多选)
考点:强凸和 Smooth 的逻辑关系、PGD 收敛前提。
以下哪些判断正确?(多选;所有陈述均讨论欧氏范数,涉及投影时可行集非空、闭且凸。)
A. f(t)=t⁴+½t² 在实数轴上是强凸函数,但其梯度不是全局 Lipschitz 连续的。
B. 若 f 二阶连续可微,且在包含 C 的凸区域内 μI≼∇²f≼LI(0<μ≤L),则 η=1/L 的 PGD 迭代对最优点的距离收缩因子至多为 1−μ/L。
C. 任何凸且 L-Smooth 的目标,无须强凸或其他附加条件,PGD 都保证以全局几何速度收敛到唯一最优点。
D. 只要一个约束在最优点活跃,它的 KKT 乘子必定严格大于零。
可选中立提示:可以用 Hessian 的特征值判断光滑性和强凸性;线性收敛、最优解唯一性与互补松弛各有不同的前提。
Lv4|PGD 的最优性证书与收敛证明(40 分|预计 12–15 分钟|开放推导)
考点:不等式推导、投影不变量、线性收缩、KKT 建模。
设 C⊂Rᵈ 为非空闭凸集,f 在包含 C 的凸开集上二阶连续可微,且 μI≼∇²f(x)≼LI,0<μ≤L。定义 x⁺=Π_C(x−η∇f(x)) 和 Gη(x)=(x−x⁺)/η。完成下列四项:
A(8 分)从沿线段的二阶积分公式推导 μ-强凸下界和 L-Smooth 上界,并解释为什么 C 上最优点唯一。
B(12 分)利用投影变分不等式证明 Gη(x)=0 与 C 上全局最优等价;再推出 f(x⁺)≤f(x)−η(1−Lη/2)‖Gη(x)‖²,说明步长范围。
| C(12 分)先证明欧氏投影非扩张,再用平均 Hessian 证明 ‖x⁺−x‖≤ρ‖x−x‖,ρ=max{ | 1−ημ | , | 1−ηL | };指出保证 ρ<1 的步长区间。 |
D(8 分)对 f(x,y)=½[(x−1.5)²+4(y−1)²],C={(x,y):x≥0,y≥0,x+y≤1},求最优解、活跃约束、KKT 乘子,并说明为何最优点的梯度未必为零。
可选中立提示:使用 p=Π_C(z) 时的 (z−p)ᵀ(y−p)≤0;投影非扩张需要把两次投影不等式相加;D 部分先假设斜边活跃再检查坐标非负。
十、总结与下一课
今天真正需要记住的是四条有适用条件的结论:
- 曲率上下界: 强凸给出二次下界,Smooth 给出二次上界,它们分别解决不同问题。
- 无约束 GD: (\mu)-强凸且 (L)-Smooth、步长 (1/L) 时,函数值误差至多按 (1-\mu/L) 的比例逐步下降。
- 约束 PGD: (G_\eta(x)=0) 在凸问题中才是全局最优的充要判据;梯度不必为零。(0<\eta<2/L) 可保证非驻点的下降。
- 线性收缩: 若进一步满足本文的 Hessian 上下界与闭凸投影条件,则 PGD 距离满足 (|x_k-x^|\le\rho^k|x_0-x^|)。
下一讲:2026 年 10 月 26 日,第 7 课进行第一周系统复盘:将凸性、投影、法锥、Slater、KKT、强凸与 Smooth 放在同一道综合模型中,重点检查“什么时候是充要条件、什么时候需要资格条件、什么时候才有收敛率”,不引入重复新专题。第 8 课按计划开始第二周 KKT 与对偶的系统深化。
作答后会按 Lv1–Lv4 逐题反馈、总分 100:80 分以上继续;60–79 分补针对性数值例子;低于 60 分先回顾薄弱概念再练。课程日期编号不因测评结果改变。