数学优化理论 · 第 3 课
次梯度:不可微的凸函数为什么仍能优化?
2026 年 10 月 22 日|第一周|约 18 分钟
归档说明: 这是根据当日课程主题重构并补全的完整教学讲义,而不是历史消息逐字转录。参考答案只在独立 JSON 中保存。
学习目标
从可微凸函数的一阶支撑不等式自然推广到次梯度与次微分;计算绝对值函数在尖点的所有支撑斜率;证明投影次梯度法的 $O(1/\sqrt T)$ 收敛界,并理解固定步长可能无法精确收敛。
一、不可微为什么不是最优性条件的终点?
我们之前对凸可微函数使用
\[f(y)\ge f(x)+\nabla f(x)^\top(y-x).\]| 这表明在 x 处存在一条“切平面”始终位于函数下方。问题是,有些凸函数存在尖点,普通梯度不存在,但仍可能存在很多条合法的支撑直线。例如 $f(x)= | x | $ 在原点左斜率为 −1、右斜率为 +1,无法找到唯一普通导数。 |
因此不要强行让左导数等于右导数,而是直接寻找所有满足全局支撑下界的向量。定义:
\[\boxed{\partial f(x)=\{g:\ f(y)\ge f(x)+g^\top(y-x),\ \forall y\}.}\]集合 $\partial f(x)$ 就叫次微分,集合内每个向量叫次梯度(Subgradient)。
二、严格求 ∂|x|(0)
在原点,$f(0)=0$。一个数 g 是次梯度,当且仅当对所有实数 y,
\[|y|\ge gy.\]如果 $y>0$,两边除以正数 y,得到 $1\ge g$。如果 $y<0$,两边除以负数会反转不等号,得到 $-1\le g$。所以必要条件为 $-1\le g\le1$。
| 反过来,如果 $g\in[-1,1]$,对 $y>0$ 有 $gy\le y= | y | $,对 $y<0$ 有 $gy\le -y= | y | $,因此上述条件也充分。于是 |
在 $x>0$ 的光滑区域只有斜率 1,在 $x<0$ 只有斜率 −1。
最优性:对凸函数,如果 $0\in\partial f(x^)$,定义立刻给出 $f(y)\ge f(x^)$ 对任意 y 成立,故 x* 为全局最优。这比“普通梯度为零”适用范围更广。
三、先做一个数值例子
| 考虑 $f(x)= | x | +\tfrac12(x-2)^2$。当 x>0 时 $g(x)=1+(x-2)=x-1$,在正半轴其零点为 x=1;当 x<0 时 $g(x)=-1+(x-2)=x-3$,在负半轴无法为零;在 x=0 时,次微分是 $[-1,1]-2=[-3,-1]$,不包含0。因此唯一全局最优点是 x=1。 |
也可以直接比较数值 $f(0)=2$,$f(1)=1+0.5=1.5$,但只比较有限个点不是全局最优证明;次梯度零条件与凸性才构成完整证书。
证明依赖关系图
flowchart TD
A[凸函数全局支撑不等式] --> B[次微分 ∂f(x)]
B --> C[0 属于 ∂f(x*) 则全局最优]
B --> D[选择 g_t 属于 ∂f(x_t)]
D --> E[投影次梯度更新]
E --> F[平方距离下降不等式]
F --> G[望远镜求和 + Jensen]
G --> H[平均函数值误差 O(1/√T)]
四、次梯度下降不等于可微梯度下降
无约束更新为 $x_{t+1}=x_t-\eta_t g_t$,其中 $g_t\in\partial f(x_t)$。有凸约束 C 时,为保持可行,用欧氏投影:
\[x_{t+1}=\Pi_C(x_t-\eta_t g_t).\]假设 C 非空闭凸、f 凸、最优点 $x^*\in C$ 存在,次梯度范数有界 $|g_t|\le G$。欧氏投影非扩张:
\[\|\Pi_C(u)-\Pi_C(v)\|\le\|u-v\|.\]因为 $x^\in C$,有 $\Pi_C(x^)=x^*$,所以
\[\|x_{t+1}-x^*\|^2\le\|x_t-\eta g_t-x^*\|^2.\]展开平方,逐项得到
\[\|x_{t+1}-x^*\|^2\le\|x_t-x^*\|^2-2\eta g_t^\top(x_t-x^*)+\eta^2\|g_t\|^2.\]次梯度定义应用于 $y=x^*$:
\[g_t^\top(x_t-x^*)\ge f(x_t)-f(x^*).\]代入并使用 $|g_t|^2\le G^2$:
\[2\eta(f(x_t)-f^*)\le\|x_t-x^*\|^2-\|x_{t+1}-x^*\|^2+\eta^2G^2.\]这里每个不等式都有来源:投影非扩张、平方展开、次梯度下界和范数约束,不能只报收敛阶。
五、望远镜相消与 O(1/√T)
取固定 T 步内的统一步长 η>0,并设 $|x_0-x^*|\le R$。把上式从 t=0 到 T−1 求和;中间的距离平方项相消,末项距离平方非负,可以丢掉:
\[2\eta\sum_{t=0}^{T-1}(f(x_t)-f^*)\le R^2+T\eta^2G^2.\]除以 $2\eta T$:
\[\frac1T\sum_t(f(x_t)-f^*)\le\frac{R^2}{2\eta T}+\frac{\eta G^2}2.\]凸性允许对平均迭代点 $\bar x_T=\tfrac1T\sum_t x_t$ 使用 Jensen:
\[f(\bar x_T)-f^*\le\frac{R^2}{2\eta T}+\frac{\eta G^2}2.\]选择令两项同阶的 $\eta=R/(G\sqrt T)$(R,G>0),得到
\[\boxed{f(\bar x_T)-f^*\le RG/\sqrt T.}\]于是要保证该上界不超过 ε,足够取 $T\ge(RG/\epsilon)^2$。这是平均迭代点的函数值误差上界,不是说任意最后一个迭代点都有相同结论。
[[viz:subgradient]]
六、执行 Trace:常数步长可能振荡
| 以 $f(x)= | x | $ 为例,取 η=1、初始 $x_0=0.5$。在正半轴唯一次梯度为 +1,故下一步 $x_1=0.5-1=-0.5$;在负半轴唯一次梯度为 −1,再下一步 $x_2=-0.5-(-1)=0.5$。此后永远重复,目标值都等于0.5,无法精确收敛至最优值0。 |
| 迭代 t | 当前 x | 选定次梯度 g | 下一个 x |
|---|---|---|---|
| 0 | 0.5 | +1 | −0.5 |
| 1 | −0.5 | −1 | 0.5 |
| 2 | 0.5 | +1 | −0.5 |
这说明选择步长必须和理论假设匹配。上面 $O(1/\sqrt T)$ 的步长依赖预设迭代次数 T,并不等于“永远保持 η=1”。
七、适用边界与下节预告
次微分的全局支撑定义建立在凸函数上,非凸临界点不能得到相同的全局证书;有界次梯度、最优解存在、可计算投影等条件也要逐一核对。若投影自身很贵,就需要把投影算法时间纳入总复杂度。
第 4 课将进一步研究投影、法锥、线性约束的 KKT 与投影梯度法,并把“零次梯度”改写为有约束情形的一阶条件。
四级分级测评(100 分;首次不含答案)
前三题客观判分;第四题证明与建模需按评分点自评或由人工/ChatGPT 批改。
Lv1|非光滑最优性|15 分|约 2 分钟
对于定义域为凸集的适当凸函数 f 和内部可行点 x,以下哪种说法最严谨?
A. 函数在 x 不可微时不存在任何一阶最优性条件
B. 如果 0∈∂f(x),则 x 为无约束全局最小点;非光滑点可有多个次梯度
C. 任何被称为“次梯度”的向量都必须等于唯一的普通梯度
D. 非空次微分意味着函数值必定严格递减
可选提示:使用 f(y)≥f(x)+gᵀ(y−x);把 g=0 代入检查。
Lv2|一步次梯度计算|20 分|约 4 分钟
| 令 f(x)= | x−1 | +x²/2,起点 x₀=2,取步长 η=0.25,执行一次无约束次梯度下降 x₁=x₀−ηg₀(此点可微,g₀ 唯一)。求 x₁ 的数值。 |
| *可选提示:x₀>1 时 | x−1 | 的导数为 +1;再加二次项导数。* |
Lv3|收敛假设与失败反例|25 分|约 5 分钟
关于次梯度下降的适用条件和理论边界,哪些判断正确?(多选)
| A. 对于 f(x)= | x | ,在 x=0 处的次微分是 [-1,1] |
B. 每步固定步长 η>0 即可保证任意凸 Lipschitz 函数的次梯度下降必然精确收敛到最优点
C. 在凸集投影、次梯度范数有界且初始与最优点距离有界等条件下,取合适的 η=O(1/√T) 可使平均函数误差得到 O(1/√T) 界
D. 对非凸函数,任取一个向量并叫作次梯度,就能照搬本节凸次梯度下降的全局最优证明
可选提示:逐项核对凸函数的全局下界、固定步长振荡反例以及收敛界需要的假设。
Lv4|完整收敛界证明|40 分|约 12 分钟
| A(10分)从次梯度定义证明 ∂ | x | (0)=[−1,1],写出其他 x 的次微分并给出 0∈∂f(x*) 的凸全局最优性解释。B(14分)对闭凸集合 C 的投影次梯度迭代 x_{t+1}=Π_C(x_t−ηg_t),设 f 凸、g_t∈∂f(x_t)、 | g_t | ≤G、 | x₀−x* | ≤R,推导 f(x̄_T)−f*≤R²/(2ηT)+ηG²/2,明确何处使用非扩张与凸性。C(8分)选定 η=R/(G√T)(R,G>0)求最终上界和迭代复杂度。D(8分)用 f(x)= | x | 给出固定步长可能持续振荡的数值反例。 |
可选提示:先平方展开投影点到最优点的距离;用次梯度不等式把内积换成函数值差;最后对 t 求和。