数学优化理论 · 第 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 $,因此上述条件也充分。于是
\[\boxed{\partial|x|(0)=[-1,1].}\]

在 $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 求和。