数学优化理论 · 第22课:投影与近端算子——从 KKT 到非光滑优化
2026-11-10|第4周·第1天|讲授约18分钟(自测另计)
| 前三周我们研究了光滑目标的梯度下降与加速;现在进入第四周:投影、Prox、Moreau 及非光滑优化。核心问题是:**当函数含 ( | x | ) 或必须满足 (x\in C) 时,梯度下降该怎样改造?** |
一、问题与假设:光滑项 + 非光滑项
研究复合问题
[ \boxed{\min_{x\in\mathbb R^n} F(x)=f(x)+h(x).} ]
本课的收敛定理假设:(f) 凸、可微、梯度 (L)-Lipschitz((L>0));(h:\mathbb R^n\to(-\infty,+\infty]) 是真、下半连续、凸函数;全局最优点 (x^*) 存在。(h) 允许不可微,也允许取 (+\infty) 来编码约束。学习定义和投影的部分只需集合 (C) 非空、闭、凸。
例如 Lasso 的 (h(x)=\lambda|x|_1) 不可微;约束 (x\in C) 可写为 (h(x)=\delta_C(x)),其中指标函数在 (C) 内为 0、外部为 (+\infty)。不能直接对不可微的 (h) 写普通梯度 (\nabla h),但可以用次梯度或近端算子。
二、欧氏投影:一个优化问题
对于非空、闭、凸集合 (C),定义
[ \boxed{\Pi_C(v)=\arg\min_{z\in C}\tfrac12|z-v|^2.} ]
由于目标关于 (z) 严格凸且强制增长,且 (C) 闭非空,极小点存在并唯一。例如 (C=[0,2]\times[0,2]),则 (\Pi_C(3,-1)=(2,0))。
2.1 投影的最优性条件(严谨推导)
令 (p=\Pi_C(v))。任取 (z\in C),凸性保证 (p+t(z-p)\in C) 对 (t\in[0,1]) 成立。函数
[ \psi(t)=\tfrac12|p+t(z-p)-v|^2 ]
在 (t=0) 处达到单侧最小值,所以
[ \psi’(0)=(p-v)^T(z-p)\ge0. ]
即
[ \boxed{(v-p)^T(z-p)\le0,\quad\forall z\in C.}\tag{1} ]
反过来若式 (1) 成立,展开
[ |z-v|^2 =|z-p|^2+|p-v|^2+2(z-p)^T(p-v) \ge|p-v|^2, ]
故 (p) 的确是投影。于是式 (1) 是必要且充分条件。
定义凸集的法锥
[ N_C(p)={w:w^T(z-p)\le0\text{ 对所有 }z\in C}. ]
投影最优性简写为
[ \boxed{p=\Pi_C(v)\ \Longleftrightarrow\ v-p\in N_C(p).}\tag{2} ]
2.2 为什么投影不会放大距离?
设 (p=\Pi_C(u))、(q=\Pi_C(v))。式 (1) 分别应用于 (p) 和 (q):
[ (u-p)^T(q-p)\le0,\qquad(v-q)^T(p-q)\le0. ]
相加整理得
[ \boxed{|p-q|^2\le(p-q)^T(u-v).}\tag{3} ]
再用 Cauchy–Schwarz:
[ \boxed{|\Pi_C(u)-\Pi_C(v)|\le|u-v|.} ]
式 (3) 比普通 Lipschitz 更强,称为Firm Nonexpansiveness(坚固非扩张性)。这里凸性很关键。
三、连接前两周 KKT:边界最优不要求原梯度为零
设 (f) 可微凸,考虑 (\min_{x\in C}f(x))。凸函数一阶最优性条件为
[ \nabla f(x^)^T(z-x^)\ge0,\quad \forall z\in C, ]
即
[ -\nabla f(x^)\in N_C(x^). ]
利用式 (2),对任意 (\eta>0):
[ \boxed{x^=\Pi_C(x^-\eta\nabla f(x^*)).}\tag{4} ]
这称为投影不动点形式的最优性条件。它不是说任意步长的迭代都收敛;它只刻画最优点。
回顾例子:
[ \min_{x\le1}\tfrac12(x-2)^2. ]
最优点 (x^*=1),但 (f’(1)=-1\ne0)。写 (g(x)=x-1\le0),KKT:
[ x^-2+\lambda^=0,\quad \lambda^\ge0,\quad g(x^)\le0,\quad\lambda^g(x^)=0. ]
解得 (\lambda^*=1),约束活跃且互补松弛成立。因为 (N_{(-\infty,1]}(1)=[0,\infty)),有 (-f’(1)=1\in N_C(1))。同时
[ \Pi_C(1-\eta(-1))=\Pi_C(1+\eta)=1. ]
提醒:活跃约束未必有正乘子。 例如 (\min_{x\le0}x^2/2) 在 (x^=0) 活跃,却有 (\lambda^=0)。
四、Prox:把不可微项放进一个容易求的小优化问题
对真、下半连续、凸函数 (h),定义
[ \boxed{\operatorname{prox}_{\eta h}(v) =\arg\min_z\left{h(z)+\frac1{2\eta}|z-v|^2\right},\quad \eta>0.}\tag{5} ]
二次项使这个子问题强凸,故 prox 单值。最优性条件为
[ 0\in\partial h(p)+\frac{p-v}{\eta}, \quad\Longleftrightarrow\quad \boxed{\frac{v-p}{\eta}\in\partial h(p).}\tag{6} ]
这里 (\partial h(p)) 是凸次微分,不是普通梯度。
对于 (h=\delta_C),式 (5) 只允许 (z\in C),因此
[ \boxed{\operatorname{prox}_{\eta\delta_C}(v)=\Pi_C(v).} ]
投影就是指标函数的 Prox。
4.1 软阈值为什么自然出现?
| 令 (h(z)=\lambda | z | ),其中 (\lambda>0)。近端问题是 |
[ \min_z \lambda|z|+\frac1{2\eta}(z-v)^2. ]
| 若 (z>0),一阶条件给 (z=v-\eta\lambda>0);若 (z<0),给 (z=v+\eta\lambda<0);若 (z=0),使用 (\partial | 0 | =[-1,1]),有 (v/\eta\in[-\lambda,\lambda])。 |
所以
[ \boxed{ S_{\eta\lambda}(v) =\operatorname{sign}(v)\max{|v|-\eta\lambda,0}. }\tag{7} ]
多维 (h(x)=\lambda|x|_1) 时按坐标分别软阈值。例:(\eta=0.5,\lambda=1),(v=2) 输出 (1.5),(v=0.3) 输出 (0)。
与硬截断不同,Soft Threshold 不但会把小值置零,还会将较大值向零收缩 (\eta\lambda)。
五、近端梯度法(Proximal Gradient / ISTA)
对 (F=f+h),光滑项走梯度步,非光滑项走 Prox:
[ \boxed{x_{k+1}=\operatorname{prox}_{\eta h} \bigl(x_k-\eta\nabla f(x_k)\bigr).}\tag{8} ]
这等价于最小化关于 (u) 的局部模型
[ Q_x(u)=h(u)+\nabla f(x)^T(u-x)+\frac1{2\eta}|u-x|^2. ]
定理(凸复合优化):在第一节全部假设下,若 (0<\eta\le1/L),则目标值单调不增,而且对 (K\ge1):
[ \boxed{ F(x_K)-F(x^)\le\frac{|x_0-x^|^2}{2\eta K}. }\tag{9} ]
5.1 一步不等式的关键证明
令 (x^+) 为一次近端梯度更新,(g=\nabla f(x)),任意取 (z)。函数 (Q_x) 是 (1/\eta)-强凸且 (x^+) 最小化它,所以
[ Q_x(x^+)+\frac1{2\eta}|z-x^+|^2\le Q_x(z). ]
同时 (L)-Smooth 给出
[ f(x^+)\le f(x)+g^T(x^+-x)+\frac L2|x^+-x|^2, ]
凸性给出
[ f(z)\ge f(x)+g^T(z-x). ]
组合并消去梯度内积后得到:
[
\begin{aligned}
F(x^+)-F(z)
&\le \frac{|x-z|^2-|x^+-z|^2}{2\eta}
&\quad-\left(\frac1{2\eta}-\frac L2\right)|x^+-x|^2.
\end{aligned}\tag{10}
]
由于 (\eta\le1/L),最后一项非正。取 (z=x^*),得到一个相邻距离平方之差的上界;取 (z=x) 又得到 (F(x^+)\le F(x))。从 (k=0) 至 (K-1) 求和,平方距离项望远镜抵消,结合单调性可得式 (9)。
结论的边界:这是凸复合目标的最后一步函数值误差 (O(1/K))。它不直接证明非凸全局最优,也不意味着任意 (\eta) 都合法。
六、两轮精确数值迭代:L1 正则改变了最优点
考虑
[ F(x)=\frac12(x-3)^2+|x|,\quad x_0=0,\quad\eta=0.5. ]
| 这里 (f’(x)=x-3,\ L=1,\ h(x)= | x | ),所以阈值 (\eta\lambda=0.5)。 |
第一轮先算 (v_0=x_0-\eta f’(x_0)=1.5),再做软阈值:
[ x_1=S_{0.5}(1.5)=1. ]
第二轮 (v_1=1-0.5(1-3)=2),故
[ x_2=S_{0.5}(2)=1.5. ]
| 由于 (0\in x-3+\partial | x | ),全局最优点为 (x^=2),最优值 (F^=2.5)。 |
| 迭代 (k) | 输入 (x_k) | 梯度步 (v_k) | Prox 后 (x_{k+1}) | (F(x_{k+1})) |
|---|---|---|---|---|
| 0 | 0 | 1.5 | 1 | 3.000 |
| 1 | 1 | 2.0 | 1.5 | 2.625 |
| — | — | — | 最优点 2 | 2.500 |
初始 (F(0)=4.5)。若完全忽略 (h),光滑项的最优点是 (3),并非原问题最优点 (2)。这就是近端梯度与普通 GD 的实质区别。
七、失败反例:哪些条件不能删?
反例一:非凸集合使投影不唯一。 取 (C={-1,1}),(v=0)。两点到原点距离都为 1,因此 (\Pi_C(0)={-1,1}) 是多值的;第二节的单值和坚固非扩张结论需要凸性。
反例二:步长过大可使迭代发散。 令 (f(x)=x^2/2)、(h=0)、(L=1)、(x_0=1),却取 (\eta=3)。近端梯度退化为 GD:
[ x_{k+1}=x_k-3x_k=-2x_k, ]
所以 (1\to-2\to4),目标值 (0.5\to2\to8)。不能把 (\eta\le1/L) 的收敛定理应用到此例。
| 反例三:非光滑不意味着不能优化。 (h(x)= | x | ) 在 0 不可微,然而式 (7) 的 Prox 在 0 附近仍有明确、唯一的解;错误做法是把不可微直接当成“无法迭代”。 |
八、关系图与核心结论
flowchart TD
A["约束 x∈C"] --> B["指标函数 δ_C"]
B --> C["prox(δ_C) = 投影 Π_C"]
C --> D["法锥与变分不等式"]
D --> E["约束最优点的投影不动点 / KKT"]
F["非光滑凸项 h"] --> G["prox 的次梯度条件"]
G --> H["L1 对应 Soft Threshold"]
I["凸且 L-Smooth 的 f"] --> J["近端梯度:∇f + prox(h)"]
G --> J
J --> K["步长 η≤1/L:函数值 O(1/K)"]
今日要带走三个公式:
[ \boxed{p=\Pi_C(v)\iff v-p\in N_C(p)} ]
[ \boxed{p=\operatorname{prox}_{\eta h}(v)\iff (v-p)/\eta\in\partial h(p)} ]
[ \boxed{x_{k+1}=\operatorname{prox}_{\eta h}(x_k-\eta\nabla f(x_k))} ]
下一讲(2026-11-11,第23课):Moreau Envelope、Moreau 分解与 Prox 为什么能把非光滑问题转化为光滑的梯度信息。我们将推导 Envelope 的梯度和 L1/投影的相关恒等式,并解释光滑化的收益与局限。
九、今日四级自测(100 分)
首次课堂不公布答案或开放题评分标准。独立测验 JSON 包含答案,作答前不要打开,避免泄题。
Lv1|投影与最优性条件辨析|15 分|预计 2 分钟
设 (C\subset\mathbb R^n) 非空、闭、凸,(h=\delta_C) 是其指标函数,(\eta>0)。以下哪项必然正确?
- A. 只要 (C) 闭,投影 (\Pi_C(v)) 就一定唯一,即使 (C) 非凸。
- B. (\operatorname{prox}_{\eta\delta_C}(v)=\Pi_C(v)),且 (p=\Pi_C(v)) 当且仅当 (v-p\in N_C(p))。
- C. 若约束在最优点活跃,它的 KKT 乘子一定严格为正。
- D. 对任意不可微函数 (h),(\operatorname{prox}_{\eta h}(v)) 必须用普通梯度下降求解。
提示:从指标函数的定义出发;回忆投影变分不等式及非凸集合的反例。
Lv2|软阈值的一步近端梯度更新|20 分|预计 3 分钟
| 考虑 (F(x)=\frac12(x-4)^2+1.5 | x | ),从 (x_0=0) 开始,取步长 (\eta=0.5),执行一步近端梯度 (x_1=\operatorname{prox}_{\eta h}(x_0-\eta f’(x_0))),其中 (f(x)=\frac12(x-4)^2)、(h(x)=1.5 | x | )。求 (x_1),保留三位小数。 |
提示:先计算纯梯度试探点 v,再对 v 施加阈值 η×1.5 的 soft-thresholding。
Lv3|两次迭代、模型比较与最优点核验|25 分|预计 5 分钟
| 对 (F(x)=\frac12(x-5)^2+2 | x | ),从 (x_0=0) 开始,使用 (\eta=1/2) 的近端梯度法做两次迭代。该凸问题的全局最优点可由次梯度条件确定。以下哪项完全正确? |
- A. (x_1=2.5,\ x_2=3.75);因为只需对光滑项做梯度下降。
- B. (x_1=1.5,\ x_2=2.25,\ F(x_2)=9.28125),且最优点为 5。
- C. (x_1=1.5,\ x_2=2.25,\ F(x_2)=8.28125),且最优点为 3。
-
D. (x_1=x_2=0);因为 ( x ) 在零处不可微,算法无法启动。
| *提示:每轮先对光滑项作梯度步,再执行阈值为 η×2 的软阈值;计算 F 时别忘记 2 | x | 。* |
Lv4|投影最优性、近端梯度收敛与 KKT 证明|40 分|预计 12 分钟
完成四个部分,注明每一部分的假设。
A(10 分)设 (C\subset\mathbb R^n) 非空闭凸,证明 (p=\Pi_C(v)\iff (v-p)^T(z-p)\le0\ \forall z\in C)。进而证明可微凸函数在 (C) 上的最优点 (x^) 满足 (x^=\Pi_C(x^-\eta\nabla f(x^)))(任意 (\eta>0))。
| B(10 分)对适当的真、下半连续、凸函数 (h),由近端子问题推导 ((v-p)/\eta\in\partial h(p))。解释为何 (h=\delta_C) 时 prox 就是投影,并分情况推导 (h(t)=\lambda | t | ) 的软阈值公式。 |
C(14 分)考虑 (F=f+h),其中 (f) 凸、可微且 (L)-Smooth,(h) 真、下半连续且凸,最优点 (x^) 存在,取 (0<\eta\le1/L)。对 (x^+=\operatorname{prox}_{\eta h}(x-\eta\nabla f(x))),证明 (F(x^+)-F(z)\le[|x-z|^2-|x^+-z|^2]/(2\eta))(任意 (z)),并推导 (F(x_K)-F^\le|x_0-x^*|^2/(2\eta K)),(K\ge1)。说明用到了哪些条件。
D(6 分)对 (\min_{x\le1}\frac12(x-2)^2) 写出最优点、活跃约束、非负乘子、驻点与互补松弛,并给出一个投影失去唯一性的非凸集合反例。
提示:A 用投影最优性的一阶变分不等式;B 用 Fermat 次梯度条件;C 比较近端二次模型在 x+ 与 z 的值,结合 Smooth/凸性及望远镜求和;D 注意约束活跃不等于一般地强制正乘子。
作答后会逐题评分:80 分及以上正常继续;60–79 分补充针对性例题;低于 60 分优先复习投影最优性、法锥、次梯度与 KKT。评分不改变按日期计算的课号。