数学优化理论 · 第 23 课

Moreau Envelope 与 Moreau 分解:用 Prox 为非光滑函数构造光滑梯度

2026 年 11 月 11 日|第 4 周·第 2 天|讲授约 18 分钟(自测另计)

上一课我们将投影看作指标函数的 Prox,推导了软阈值与近端梯度法。今天回答一个更深的问题:如果 $h(x)$ 不可微,能否构造一个与它有相同最优解、但梯度 Lipschitz 连续的函数? 答案是 Moreau 包络。我们还将解释为什么 Prox、凸共轭、投影与 KKT 实际上是同一套最优性条件的不同表达。

一、问题与假设:平滑究竟要保留什么?

令 $h:\mathbb R^n\to(-\infty,+\infty]$ 为真、下半连续、凸函数,$\eta>0$。允许 $h$ 不可微,也允许它在可行域外取 $+\infty$。定义 \(\boxed{e_\eta h(v)=\min_z\left\{h(z)+\frac{1}{2\eta}\|z-v\|^2\right\}},\qquad \boxed{P_\eta(v)=\operatorname{prox}_{\eta h}(v)=\arg\min_z\left\{h(z)+\frac{1}{2\eta}\|z-v\|^2\right\}}.\) 二次项提供 $1/\eta$-强凸性;目标下半连续且水平有界,因此极小点存在且唯一。故 $P_\eta(v)$ 是一个单值映射,$e_\eta h(v)$ 是一个有限实数。

包络等于“最优 Prox 子问题的目标值”,而 Prox 是“该子问题的最优位置”。两者绝不能混淆。

由 $z=v$ 是候选点,可得在 $h(v)<+\infty$ 时 $e_\eta h(v)\le h(v)$;若 $h_{\min}=\min h$ 存在,则 $h_{\min}\le e_\eta h(v)$。在 $x^\in\arg\min h$ 处,选择 $z=x^$ 得 $e_\eta h(x^*)=h_{\min}$;反过来,若 $e_\eta h(v)=h_{\min}$,其唯一近端点 $p$ 必满足 $h(p)=h_{\min}$ 且 $p=v$。因此 \(\boxed{\arg\min e_\eta h=\arg\min h}\qquad(\text{当最优值达到时}).\) 平滑保留了原问题的最优点集合,但并不承诺保留每个位置的函数值或曲率。

二、从 Prox 最优性到 Firm Nonexpansiveness

记 $p=P_\eta(u)$、$q=P_\eta(v)$。近端最优性条件为 \(\frac{u-p}{\eta}\in\partial h(p),\qquad \frac{v-q}{\eta}\in\partial h(q).\) 凸函数的次梯度是单调算子。为什么?若 $a\in\partial h(p)$、$b\in\partial h(q)$,由两条次梯度不等式 \(h(q)\ge h(p)+a^T(q-p),\qquad h(p)\ge h(q)+b^T(p-q)\) 相加可得 $(a-b)^T(p-q)\ge0$。代入上述两组次梯度: \(\left[(u-p)-(v-q)\right]^T(p-q)\ge0.\) 整理得到 \(\boxed{\|p-q\|^2\le(u-v)^T(p-q).}\tag{1}\) 这叫坚固非扩张性(firm nonexpansiveness)。由 Cauchy–Schwarz 立即得 \(\|P_\eta(u)-P_\eta(v)\|\le\|u-v\|.\) 更关键的是,$I-P_\eta$ 也不会放大距离。令 $d=u-v$、$r=p-q$,由式 (1): \(\begin{aligned} \|(I-P_\eta)u-(I-P_\eta)v\|^2 &=\|d-r\|^2\\ &=\|d\|^2+\|r\|^2-2d^Tr\\ &\le\|d\|^2-\|r\|^2 \le\|d\|^2. \end{aligned}\) 因此 \(\boxed{\|(I-P_\eta)u-(I-P_\eta)v\|\le\|u-v\|.}\tag{2}\)

三、为什么 Moreau 包络可微?梯度是什么?

近端点 $p=P_\eta(v)$ 是唯一极小点。用 $p$ 作为 $v+d$ 处的候选点,得到 \(e_\eta h(v+d) \le e_\eta h(v)+\frac1\eta(v-p)^Td+\frac1{2\eta}\|d\|^2.\tag{3}\) 反向地,用 $p’=P_\eta(v+d)$ 作为 $v$ 处的候选点: \(e_\eta h(v+d) \ge e_\eta h(v)+\frac1\eta(v+d-p')^Td-\frac1{2\eta}\|d\|^2.\tag{4}\) 由式 (2),$(v+d-p’)-(v-p)=O(|d|)$。所以上下界都等于 \(e_\eta h(v)+\frac1\eta(v-p)^Td+O(\|d\|^2).\) 这证明了可微性与梯度公式: \(\boxed{\nabla e_\eta h(v)=\frac1\eta\left(v-P_\eta(v)\right).}\tag{5}\) 再由式 (2): \(\begin{aligned} \|\nabla e_\eta h(u)-\nabla e_\eta h(v)\| &=\frac1\eta\|(I-P_\eta)u-(I-P_\eta)v\|\\ &\le\frac1\eta\|u-v\|. \end{aligned}\) 因此 \(\boxed{e_\eta h\text{ 凸且 }1/\eta\text{-Smooth}.}\tag{6}\) 即使 $h$ 本身不可微,包络仍然拥有光滑梯度。$\eta$ 越大,梯度 Lipschitz 上界 $1/\eta$ 越小;但包络对原函数的改变也可能更大,不能无条件把“更光滑”等同于“更准确”。

四、例一:$L_1$ 的 Moreau 包络就是 Huber 型函数

取标量 $h(z)=\lambda|z|$($\lambda>0$)。上一课得到软阈值 \(P_\eta(v)=S_{\eta\lambda}(v) =\operatorname{sign}(v)\max\{|v|-\eta\lambda,0\}.\) 将 Prox 点代回包络定义:

当 $|v|\le\eta\lambda$,有 $P_\eta(v)=0$,所以 \(e_\eta h(v)=\frac{v^2}{2\eta}.\) 当 $|v|>\eta\lambda$,有 $P_\eta(v)=v-\eta\lambda\operatorname{sign}(v)$,所以 \(e_\eta h(v) =\lambda(|v|-\eta\lambda)+\frac{\eta\lambda^2}{2} =\lambda|v|-\frac{\eta\lambda^2}{2}.\) 合并: \(\boxed{ e_\eta(\lambda|\cdot|)(v)= \begin{cases} v^2/(2\eta),&|v|\le\eta\lambda,\\ \lambda|v|-\eta\lambda^2/2,&|v|>\eta\lambda. \end{cases}}\tag{7}\) 梯度为 \(\boxed{ \nabla e_\eta h(v)= \begin{cases} v/\eta,&|v|\le\eta\lambda,\\ \lambda\,\operatorname{sign}(v),&|v|>\eta\lambda. \end{cases}}\tag{8}\) 原本 $|v|$ 在零点有尖角;Moreau 包络在阈值范围内把尖角替换成一段二次曲线,两侧是线性段。阈值处一阶导数连续,但二阶导数可以跳变:$C^1$ 不等于 $C^2$。

五、Moreau 分解:Prox 与凸共轭如何互补?

定义凸共轭: \(\boxed{h^*(q)=\sup_z\{q^Tz-h(z)\}.}\) 其核心性质为 Fenchel 次梯度等价: \(q\in\partial h(p)\iff p\in\partial h^*(q).\) 令 $p=P_\eta(v)$、$q=(v-p)/\eta$。由 Prox 最优性,$q\in\partial h(p)$,所以 $p\in\partial h^(q)$。又因为 $p=v-\eta q$,得到 \(0\in\partial h^*(q)+\eta(q-v/\eta).\) 这恰好是 \(q=\operatorname{prox}_{h^*/\eta}(v/\eta)\) 的最优性条件。于是 \(\boxed{\operatorname{prox}_{\eta h}(v)+\eta\operatorname{prox}_{h^*/\eta}(v/\eta)=v.}\tag{9}\) 这就是 Moreau 分解。注意第二个 Prox 的参数是 $h^/\eta$,输入是 $v/\eta$;遗漏缩放会算错。

例子: $h(z)=2|z|$,$\eta=0.5$,$v=3$。共轭为 $h^*(q)=\delta_{[-2,2]}(q)$。于是 \(\operatorname{prox}_{0.5h}(3)=S_1(3)=2,\qquad \operatorname{prox}_{h^*/0.5}(6)=\Pi_{[-2,2]}(6)=2.\) 两项相加 $2+0.5\times2=3$,恰好还原输入。由式 (5)、(9) 还可得 \(\boxed{\nabla e_\eta h(v)=\operatorname{prox}_{h^*/\eta}(v/\eta).}\tag{10}\) 这将“梯度”直接表达为“对偶 Prox”。

六、例二:指标函数的包络与 KKT

若 $h=\delta_C$,其中 $C$ 非空、闭、凸,则 $P_\eta(v)=\Pi_C(v)$,从而 \(\boxed{e_\eta\delta_C(v)=\frac{\operatorname{dist}(v,C)^2}{2\eta},\qquad \nabla e_\eta\delta_C(v)=\frac{v-\Pi_C(v)}{\eta}.}\tag{11}\) 它把“必须在 $C$ 内”这一硬约束变成光滑的距离平方惩罚。但最小化 $f+\frac1{2\eta}\operatorname{dist}(\cdot,C)^2$ 不一般等价于原来的硬约束问题;只有单独最小化该包络时,其最优点集合才恰好为 $C$。

再联系第二周 KKT:取 $C=(-\infty,1]$,$v=2$,$\eta=0.5$。投影点 $p=1$;由式 (11),梯度为 $(2-1)/0.5=2$。相应投影子问题 \(\min_{z\le1}\frac{(z-2)^2}{2\eta}\) 的 KKT 驻点条件是 $(z-2)/\eta+\lambda=0$;在 $z=1$ 时 $\lambda=2\ge0$,且 $\lambda(z-1)=0$。当 $v=1$ 时同一个约束仍活跃,乘子却为 $0$。再次记住:活跃约束不强迫乘子严格为正。

七、把 Moreau 包络当作目标做梯度下降

由式 (5),如果对 $e_\eta h$ 使用步长 $\eta$ 的 GD: \(\begin{aligned} x_{k+1} &=x_k-\eta\nabla e_\eta h(x_k)\\ &=x_k-[x_k-P_\eta(x_k)]\\ &=\boxed{\operatorname{prox}_{\eta h}(x_k)}. \end{aligned}\) 这正是近端点算法(Proximal Point Algorithm, PPA)。Moreau 包络的光滑梯度下降和原函数的近端点迭代是同一回事。

假设进一步存在最优点 $x^*\in\arg\min h$。由近端最优性: \(g_{k+1}:=\frac{x_k-x_{k+1}}{\eta}\in\partial h(x_{k+1}).\) 次梯度不等式给出 \(h(x_{k+1})-h_{\min}\le \frac1\eta(x_k-x_{k+1})^T(x_{k+1}-x^*).\) 使用三点恒等式: \(2(a-b)^T(b-c)=\|a-c\|^2-\|b-c\|^2-\|a-b\|^2,\) 得到 \(\boxed{ h(x_{k+1})-h_{\min} \le\frac{\|x_k-x^*\|^2-\|x_{k+1}-x^*\|^2-\|x_k-x_{k+1}\|^2}{2\eta}. }\tag{12}\) 对 $k=0,\ldots,K-1$ 求和,右侧望远镜抵消: \(\sum_{k=0}^{K-1}[h(x_{k+1})-h_{\min}] \le\frac{\|x_0-x^*\|^2}{2\eta}.\) 而近端点更新保证 $h(x_1)\ge h(x_2)\ge\cdots$:使用 $x_k$ 作为下一次近端问题的候选点即可证明。因此 \(\boxed{h(x_K)-h_{\min}\le\frac{\|x_0-x^*\|^2}{2\eta K},\quad K\ge1.}\tag{13}\) 这是真、下半连续、凸且最优点存在时的最后一步函数值 $O(1/K)$ 界,并不是对任意非凸函数的保证。

计算成本警告: 上述更新每次需要求出 Prox。并不是说把目标换成包络就能免费求梯度;对一般 $h$,Prox 本身可能是一个昂贵的内层优化问题。

八、数值迭代:一组数字连接三种表示

取 $h(x)=2|x|$、$\eta=0.5$、$x_0=3$。阈值 $\eta\lambda=1$,因此 \(x_{k+1}=S_1(x_k).\)

$k$ $x_k$ $P_\eta(x_k)$ $\nabla e_\eta h(x_k)$ $e_\eta h(x_k)$
0 3 2 2 5
1 2 1 2 3
2 1 0 2 1
3 0 0 0 0
例如在 $x_0=3$ 时:$P_\eta(3)=2$,梯度 $(3-2)/0.5=2$,包络值 $2 2 +(2-3)^2/(2\times0.5)=5$。GD 对包络做一步:$3-0.5\times2=2$,恰好等于 Prox。再做两次就达到最优点 $0$。

这只是软阈值问题的特殊有限步收敛现象;一般 PPA 不保证有限步达到最优解。

九、失败反例:为什么不能省略凸性?

令 $C={-1,1}$,$h=\delta_C$。这个 $h$ 是闭集指标函数,但不是凸函数。

在 $v=0$ 时,两个候选点等距: \(P_\eta(0)=\{-1,1\},\) Prox 不是单值。

其包络为 \(e_\eta h(v)=\frac{\min\{(v-1)^2,(v+1)^2\}}{2\eta} =\frac{(|v|-1)^2}{2\eta}.\) 在 $v=0$ 的左导数为 $+1/\eta$,右导数为 $-1/\eta$;因此不可微。这直接否定了“任意非凸函数经过 Moreau 包络都会变得光滑”的说法。

另一个限制是:对 $h(z)=-z^2$、$\eta=1$,近端目标 $-z^2+(z-v)^2/2$ 关于 $z$ 无下界,Prox 甚至不存在。

十、知识关系图与方法边界

flowchart TD
 A["真 + 下半连续 + 凸 h"] --> B["Prox 唯一,次梯度最优性"]
 B --> C["Firm Nonexpansiveness"]
 C --> D["Moreau 包络梯度 1/η-Lipschitz"]
 B --> E["Fenchel 共轭 h*"]
 E --> F["Moreau 分解:原始 Prox + 对偶 Prox"]
 D --> G["对包络做 GD:步长 η"]
 G --> H["PPA:x_next = prox(x)"]
 H --> I["有最优点:最后一步函数值 O(1/K)"]
 J["非凸 h"] -. "上述光滑性和收敛保证不能直接套用" .-> D
对象 关键式子 保证范围
Prox $(v-P_\eta(v))/\eta\in\partial h(P_\eta(v))$ 真、下半连续、凸
Moreau 梯度 $\nabla e_\eta h=(I-P_\eta)/\eta$ 全局 $1/\eta$-Smooth
Moreau 分解 $P_\eta(v)+\eta\operatorname{prox}_{h^*/\eta}(v/\eta)=v$ 共轭与 Prox 缩放必须正确
PPA $x_{k+1}=P_\eta(x_k)$ 存在最优点时有 $O(1/K)$ 函数值界
约束指标函数 $e_\eta\delta_C=\operatorname{dist}(\cdot,C)^2/(2\eta)$ 仅闭凸 $C$ 保证投影单值及全局光滑性

最值得记住的三行: \(\boxed{\nabla e_\eta h(v)=\frac{v-\operatorname{prox}_{\eta h}(v)}{\eta}}\) \(\boxed{\operatorname{prox}_{\eta h}(v)+\eta\operatorname{prox}_{h^*/\eta}(v/\eta)=v}\) \(\boxed{x_{k+1}=x_k-\eta\nabla e_\eta h(x_k)=\operatorname{prox}_{\eta h}(x_k)}.\) 三式分别展示:光滑梯度、原始—对偶分解与近端点算法。

十一、今日四级自测(100 分)

首次课堂不提供正确选项、标准数值答案和开放题评分细则;不要先查看独立测验 JSON,以免泄题。

Lv1|Moreau 光滑性的必要假设与结论|15 分|预计 2 分钟

设 $h:\mathbb R^n\to(-\infty,+\infty]$ 为真、下半连续、凸函数,$\eta>0$。关于其 Moreau 包络 $e_\eta h$,哪项一定正确?

A. 如果 $h$ 在某点不可微,$e_\eta h$ 在该点也必不可微。
B. $e_\eta h$ 可微,且 $\nabla e_\eta h(v)=[v-\operatorname{prox}{\eta h}(v)]/\eta$,梯度是 $1/\eta$-Lipschitz 的。
C. 对任何这样的 $h$,Moreau 包络都必然强凸,最优点必然唯一。
D. $\operatorname{prox}
{\eta h}(v)=v+\eta\nabla e_\eta h(v)$。

提示:比较 Prox 的次梯度最优性条件与包络梯度公式;注意“光滑”和“强凸”不同。

Lv2|Moreau 包络的精确数值|20 分|预计 3 分钟

令 $h(z)=3 z $、$\eta=0.4$、$v=2.5$。计算 $$e_\eta h(v)=\min_z\left{3 z +\frac{(z-2.5)^2}{2(0.4)}\right}.$$ 只填写数值,保留三位小数。

提示:先算阈值 $\eta\lambda$ 和软阈值最优点,再将它代回包络目标。

Lv3|非凸投影与光滑性失效反例|25 分|预计 5 分钟

令 $C={-1,1}\subset\mathbb R$,$h=\delta_C$,$\eta>0$。关于 $\operatorname{prox}{\eta h}$ 与 $e\eta h$,下列哪项正确?

A. 因为 $C$ 是闭集,所以 $\operatorname{prox}{\eta h}(0)$ 一定是单个点。
B. 即使 $C$ 非凸,也必有 $e
\eta h$ 在所有位置可微且梯度 $1/\eta$-Lipschitz。
C. $\operatorname{prox}{\eta h}(0)={-1,1}$,且 $e\eta h(v)=(|v|-1)^2/(2\eta)$,所以包络在 $v=0$ 不可微。
D. 因为集合中有两个元素,所以 $e_\eta h(0)=0$。

提示:计算 $v$ 到集合中两点的距离平方,并比较包络在原点两侧的导数。

Lv4|Prox—包络—共轭—收敛的统一推导|40 分|预计 12 分钟

设 $h:\mathbb R^n\to(-\infty,+\infty]$ 真、下半连续、凸,$\eta>0$,且最优解集合 $\arg\min h$ 非空。记 $P(v)=\operatorname{prox}{\eta h}(v)$、$e\eta h(v)=\min_z{h(z)+|z-v|^2/(2\eta)}$。

A(10 分):由 Prox 的次梯度条件和凸次梯度单调性证明 \(\|P(u)-P(v)\|^2\le\langle P(u)-P(v),u-v\rangle.\) 解释为什么 $I-P$ 也非扩张。

B(10 分):证明或严谨说明包络可微,并推导 \(\nabla e_\eta h(v)=\frac{v-P(v)}{\eta},\qquad \|\nabla e_\eta h(u)-\nabla e_\eta h(v)\|\le\frac1\eta\|u-v\|.\) 指出这一结论依赖哪些假设。

C(10 分):写出凸共轭 $h^$,利用 $q\in\partial h(p)\iff p\in\partial h^(q)$,证明 Moreau 分解 \(P(v)+\eta\,\operatorname{prox}_{h^*/\eta}(v/\eta)=v.\) 对 $h(z)=2|z|$、$\eta=0.5$、$v=3$,验证等式两边。

D(10 分):把固定步长的 Moreau 包络 GD 写为近端点迭代 $x_{k+1}=P(x_k)$。由次梯度不等式推导 \(h(x_K)-h_{\min}\le\frac{\|x_0-x^*\|^2}{2\eta K},\quad K\ge1.\) 解释为什么这不能无条件推广到任意非凸 $h$。

提示:A 把两组 Prox 最优性条件相减;B 使用唯一极小点与 Danskin/上下界差商,并利用 A;C 令 $q=(v-P(v))/\eta$;D 用 $2\langle a-b,b-c\rangle=|a-c|^2-|b-c|^2-|a-b|^2$ 望远镜求和。

十二、下一讲

第 24 课|2026 年 11 月 12 日:投影梯度法与约束优化收敛。

从 $x_{k+1}=\Pi_C(x_k-\eta\nabla f(x_k))$ 出发,推导投影梯度映射、约束驻点性及 $O(1/K)$ 函数值界;重点区分普通梯度为零、投影梯度为零,以及 KKT 的活跃约束和互补松弛。

今日题目总分 15+20+25+40=100。提交答案后逐题评分:80 分及以上继续;60–79 分补充 Prox/共轭例子;低于 60 分优先复习凸次梯度、投影与 Moreau 缩放关系。成绩不改变后续日期和课号。