数学优化理论 · 第 4 课|投影、法锥与有约束最优性

2026 年 10 月 23 日|第 1 周|预计 17 分钟

核心问题:上一讲证明了无约束凸优化的判据 $0\in\partial f(x^)$。但如果 $x^$ 位于可行域边界,$\nabla f(x^*)\ne0$,它为什么仍可能是全局最优点?怎样设计保持可行且有收敛保证的算法?

本课目标:①从平方距离推导欧氏投影及其几何判据;②用法锥建立约束最优性条件;③看懂活跃约束、非负乘子与互补松弛;④推导投影梯度下降(PGD)的单步下降和 $O(1/T)$ 收敛界。先修:凸集、凸函数的一阶不等式,以及第 3 课的次梯度概念。

一、约束为何改变最优性?

看一维问题:

\[\min_{x\ge0}f(x)=(x+1)^2.\]

如果忽略约束,极小点是 $x=-1$,但它不可行。在 $x\ge0$ 上,最优解是 $x^*=0$,此时 $f’(0)=2\ne0$。所以 有约束问题不要求梯度为零,而要求负梯度方向没有可行的下降空间。

下面假设 $C\subseteq\mathbb R^d$ 非空、闭、凸,$f$ 凸且可微,最优解存在。以后会分别指出哪些结论还需要 $L$-Smooth 条件。

二、欧氏投影:把点拉回可行域

对任意 $z\in\mathbb R^d$,定义欧氏投影:

\[\Pi_C(z)=\arg\min_{y\in C}\frac12\|y-z\|_2^2.\]

由于 $C$ 非空且闭,而平方距离目标严格凸并在无穷远处增大,因此投影存在且唯一。

投影定理: 令 $p=\Pi_C(z)$,则

\[\boxed{(z-p)^\top(y-p)\le0,\quad\forall y\in C.}\tag{1}\]

推导:对任意 $y\in C$,由于凸性,$p+t(y-p)\in C$($0\le t\le1$)。令 $\phi(t)=\tfrac12|p+t(y-p)-z|^2$,$t=0$ 处不能往可行方向下降,因此 $\phi’(0)=(p-z)^\top(y-p)\ge0$,即式 (1)。

反过来,若式 (1) 成立,则

\[\|y-z\|^2=\|p-z\|^2+\|y-p\|^2+2(p-z)^\top(y-p)\ge\|p-z\|^2.\]

于是 $p$ 确实是最近可行点。必要性和充分性都得到证明。

例:半空间投影。 若 $C={x:a^\top x\le b}$,$a\ne0$,则

\[\boxed{\Pi_C(z)=z-\frac{(a^\top z-b)_+}{\|a\|^2}a,\qquad (t)_+=\max(t,0).}\tag{2}\]

若 $z$ 已可行,就不动;否则沿约束法向量反方向移动恰好越界的距离。区间 $C=[l,u]$ 的投影则是 $\min{u,\max{l,z}}$。

三、法锥:边界允许怎样的非零梯度?

定义凸集 $C$ 在可行点 $x$ 的法锥:

\[N_C(x)=\{v:v^\top(y-x)\le0,\ \forall y\in C\}.\]

它收集所有朝向可行域外侧的法向量。若 $x$ 为 $C$ 的内点,则 $N_C(x)={0}$;在边界,法锥可能包含非零向量。

例如 $C=[0,\infty)$,$N_C(0)=(-\infty,0]$。前面一维例子的最优点有 $-\nabla f(0)=-2\in N_C(0)$,所以即使梯度不是零也完全合理。

由凸函数一阶不等式可得:

\[f(y)\ge f(x^*)+\nabla f(x^*)^\top(y-x^*).\]

结合沿可行方向的一阶最优性,得到充要条件:

\[\boxed{x^*\in\arg\min_{x\in C}f(x) \iff 0\in\nabla f(x^*)+N_C(x^*).}\tag{3}\]

等价地:

\[\boxed{\nabla f(x^*)^\top(y-x^*)\ge0,\quad\forall y\in C.}\tag{4}\]

必要性:对任意 $y\in C$,令 $x(t)=x^+t(y-x^)$,由于 $t=0$ 是 $f(x(t))$ 在 $[0,1]$ 上的最小值,右导数非负,得到式 (4)。充分性:把式 (4) 代入凸性的一阶下界,立刻得到 $f(y)\ge f(x^*)$。

关键直觉: 在内点,向任何方向都能走,因此只能有 $\nabla f=0$;在边界,一些下降方向不可行,法锥负责抵消梯度。

四、从法锥走向 KKT:活跃约束与互补松弛

考虑由仿射不等式组成的多面体:

\[C=\{x:Ax\le b\},\quad g_i(x)=a_i^\top x-b_i\le0.\]

令活跃集合 $I(x)={i:a_i^\top x=b_i}$。对于非空多面体,其法锥满足:

\[N_C(x)=\left\{\sum_{i\in I(x)}\lambda_i a_i:\lambda_i\ge0\right\}.\]

代入式 (3),得到线性不等式约束下的 KKT 条件:

\[\boxed{ \begin{aligned} &\nabla f(x^*)+\sum_i\lambda_i a_i=0 &&\text{(驻点)}\\ &a_i^\top x^*\le b_i &&\text{(原始可行)}\\ &\lambda_i\ge0 &&\text{(对偶可行)}\\ &\lambda_i(a_i^\top x^*-b_i)=0 &&\text{(互补松弛)}. \end{aligned}}\tag{5}\]

最后一条的含义非常具体:未活跃约束 $a_i^\top x^*<b_i$ 必须有 $\lambda_i=0$;活跃约束可以有正乘子,也可能乘子恰好为零。乘子不是“违反约束的惩罚”,而是最优点处约束法向量的组合系数。

这里是凸可微目标 + 非空多面体约束,KKT 是最优性的充要条件。对于一般非线性凸不等式,证明最优解存在 KKT 乘子通常还需要 Slater 等约束资格条件;不能把线性约束的结论无条件照搬。

flowchart TD
    A["可行集合 C(闭、凸)"] --> B["欧氏投影 p = Π_C(z)"]
    B --> C["投影判据 (z-p)·(y-p) ≤ 0"]
    C --> D["法锥 N_C(x)"]
    D --> E["约束最优性 0 ∈ ∇f(x*) + N_C(x*)"]
    E --> F["多面体:活跃法向量的非负组合"]
    F --> G["KKT:驻点、可行性、互补松弛"]
    E --> H["投影梯度:x+ = Π_C(x-η∇f(x))"]

五、带数值的二维例题:投影和 KKT 如何对应?

考虑三角形可行域:

\[C=\{(x,y):x\ge0,\ y\ge0,\ x+y\le1\}\]

和目标:

\[f(x,y)=\frac12[(x-3)^2+(y+1)^2].\]

梯度 $\nabla f=(x-3,y+1)$,Hessian 为单位矩阵,所以 $f$ 是 $1$-Smooth、$1$-强凸。

从 $(0,0)$ 开始,用步长 $\eta=1/4$ 做投影梯度:

\[z_k=(x_k,y_k)-\eta\nabla f(x_k,y_k),\qquad (x_{k+1},y_{k+1})=\Pi_C(z_k).\]
步数 可行起点 梯度 未投影 $z_k$ 投影后的新点
0 $(0,0)$ $(-3,1)$ $(0.75,-0.25)$ $(0.75,0)$
1 $(0.75,0)$ $(-2.25,1)$ $(1.3125,-0.25)$ $(1,0)$

第一次是被 $y\ge0$ 挡住;第二次同时受到 $y\ge0$ 与 $x+y\le1$ 的约束,最近可行点是顶点 $(1,0)$。

在 $x^*=(1,0)$,梯度 $\nabla f=(-2,1)$。活跃约束的外法向量为 $(1,1)$(对应 $x+y\le1$)和 $(0,-1)$(对应 $-y\le0$)。确有

\[-\nabla f(x^*)=(2,-1)=2(1,1)+3(0,-1).\]

系数非负,满足法锥最优性条件。由于 $f$ 强凸,最优解唯一,最优函数值为 $f(1,0)=5/2$。注意此处梯度明显不为零。

六、投影梯度下降:不仅可行,还能收敛

算法为:

\[\boxed{x_{k+1}=\Pi_C(x_k-\eta\nabla f(x_k)).}\tag{6}\]

投影后每一步都位于 $C$。更重要的是,最优点等价于式 (6) 的不动点:对于任何 $\eta>0$,

\[x^*=\Pi_C(x^*-\eta\nabla f(x^*)) \iff 0\in\nabla f(x^*)+N_C(x^*).\]

现在额外假设 $f$ 的梯度是 $L$-Lipschitz($L>0$)。令 $d_k=x_{k+1}-x_k$,将投影判据应用于 $z=x_k-\eta\nabla f(x_k)$、$p=x_{k+1}$、$y=x_k$,得到

\[\nabla f(x_k)^\top d_k\le-\frac1\eta\|d_k\|^2.\]

由 Descent Lemma:

\[\begin{aligned} f(x_{k+1}) &\le f(x_k)+\nabla f(x_k)^\top d_k+\frac L2\|d_k\|^2\\ &\le f(x_k)-\left(\frac1\eta-\frac L2\right)\|d_k\|^2. \end{aligned}\]

所以当 $0<\eta\le1/L$,函数值不会增加。

还可以得到末次迭代 $O(1/T)$ 界。 对任意最优点 $x^*$,由凸性、Smoothness 和投影判据组合可得

\[\begin{aligned} f(x_{k+1})-f(x^*) &\le \nabla f(x_k)^\top(x_{k+1}-x^*)+\frac L2\|d_k\|^2\\ &\le\frac{\|x_k-x^*\|^2-\|x_{k+1}-x^*\|^2}{2\eta} -\frac{1-\eta L}{2\eta}\|d_k\|^2. \end{aligned}\]

若 $\eta\le1/L$,去掉非正的末项、对 $k=0,\ldots,T-1$ 求和,中间平方距离望远镜相消。再利用函数值单调下降:

\[\boxed{ f(x_T)-f(x^*)\le\frac{\|x_0-x^*\|^2}{2\eta T}. }\tag{7}\]

这是末次迭代点的函数值界,不是将上一讲次梯度法的“最好迭代点”结论直接挪过来。它依赖:凸可微、$L$-Smooth、闭凸可行域、可行起点、常步长 $0<\eta\le1/L$ 和最优解存在。若集合非凸,投影可能不唯一;若梯度不光滑或步长过大,上述证明不能原样使用。

七、反例与理解边界

*误解 1:边界最优也要 $\nabla f(x^)=0$。** 错。一维 $\min_{x\ge0}(x+1)^2$ 在 $x^*=0$ 的梯度是 $2$。

误解 2:约束一旦活跃,乘子必定严格大于零。 错。例如 $\min_{x\ge0}x^2$,最优点 $x=0$ 的约束活跃,但乘子可为零。

误解 3:任何步长的 PGD 都单调下降。 错。令 $C=\mathbb R$,$f(x)=x^2/2$,$\eta=3$,则 $x_{k+1}=-2x_k$,函数值反而增大。

误解 4:投影总是便宜的。 错。区间、盒约束、球与简单半空间容易投影,但复杂的组合约束集合本身可能需要求解较难的优化问题。此时惩罚、拉格朗日分解或 ADMM 等方法才有进一步价值。

八、四级学习检测(总分 100;首版不附答案)

Lv1|理解辨析(15 分;约 2 分钟;考点:法锥与约束最优性)

设 $f$ 凸且可微、$C$ 非空闭凸,且最优解存在。以下哪个条件对于 $x^*\in C$ 是全局最优的充要条件?

A. $0\in\nabla f(x^)+N_C(x^)$。

B. $\nabla f(x^)=0$,不论 $x^$ 是否在边界。

C. 每个可行方向与 $\nabla f(x^*)$ 的内积都严格小于零。

D. 只要 $x^*$ 在可行域边界,就一定最优。

Lv2|数值计算(20 分;约 4 分钟;考点:半空间投影和 PGD 一步迭代)

令 $f(x,y)=\tfrac12[(x-3)^2+(y-1)^2]$,$C={x\ge0,\ y\ge0,\ x+y\le2}$。从 $(x_0,y_0)=(0,0)$ 开始,采用 $\eta=0.8$:

\[(x_1,y_1)=\Pi_C\left((x_0,y_0)-0.8\nabla f(x_0,y_0)\right).\]

求 $x_1$ 的数值,保留三位小数(允许误差 $10^{-3}$)。请写出未投影的点及投影用的约束。

Lv3|机制与边界(25 分;约 5 分钟;考点:KKT、法锥、收敛假设)

多选题,选择所有正确项。

A. 在非空闭凸可行集上,凸可微目标的全局最优点可能满足 $\nabla f(x^*)\ne0$。

B. 对不等式 $a_i^\top x\le b_i$,若它在最优点严格不活跃,对应 KKT 乘子仍可以严格大于零。

C. 若 $f$ 凸且 $L$-Smooth,$C$ 非空闭凸、起点可行,采用 $0<\eta\le1/L$ 的投影梯度下降,函数值不会增加。

D. 只要投影存在且唯一,任何正步长的 PGD 都有相同的末次迭代 $O(1/T)$ 保证。

Lv4|综合推导与设计(40 分;约 10–12 分钟;考点:活跃约束、乘子、投影迭代、收敛证明)

考虑

\[\min_{x,y\ge0,\ x+y\le2}\ F(x,y)=\frac12[(x-3)^2+(y+1)^2].\]

A(10 分):写出可行集合在候选点 $(2,0)$ 的所有活跃约束外法向量,并描述它们生成的法锥。

B(10 分):利用 $0\in\nabla F+N_C$ 判断 $(2,0)$ 是否全局最优;如成立,求非负乘子,说明最优解是否唯一。不允许仅凭几何直觉断言。

C(12 分):从 $(0,0)$ 出发,取 $\eta=1/2$,手算两步投影梯度下降;每步写出未投影点与投影结果,解释哪个约束阻止了普通梯度更新。

D(8 分):从投影判据与 Descent Lemma 出发,写出保证 PGD 单步下降的步长条件,并指出推导末次迭代 $O(1/T)$ 误差界需要的假设;解释如果约束集非凸,证明中首先失效的关键性质是什么。

提示(不泄露答案):先分别画出两个斜边/坐标轴组成的三角形,找活跃边;再使用投影不等式 $(z-p)^\top(y-p)\le0$。本题可以把完整推导发来批改,不要求用某种特定记号。

九、复盘与下一课

请记住三件事:

  1. 投影定义几何可行性:$\Pi_C(z)$ 是最近可行点,判据为 $(z-p)^\top(y-p)\le0$。
  2. 法锥刻画边界最优性:$0\in\nabla f(x^)+N_C(x^)$ 取代无约束的 $\nabla f(x^*)=0$。
  3. 投影梯度兼顾可行与收敛:在闭凸约束和凸 $L$-Smooth 目标下,合适步长有函数值单调性及末次迭代 $O(1/T)$ 上界。

第 5 课预告:支持超平面、凸集分离与约束资格条件。 我们将用几何图像解释为什么约束资格条件决定能否写出可靠的拉格朗日乘子方程,并为第 2 周的 Slater、完整 KKT 和对偶理论建立基础。

本节测验先不公布答案。作答后按 Lv1—Lv4 逐题批改(总分 100);80 分以上继续,60–79 分针对薄弱环节补一道数值例题,60 分以下先复习投影与法锥,不改变既定课程编号。