数学优化理论 · 第 7 课

第一周复盘:一条证明链,串起凸性、乘子和收敛保证

2026 年 10 月 26 日|第 1 周·第 7 天(复盘)|核心阅读约 18 分钟;四道自测另计。

今天只复盘,不增加新专题。 要回答三个相互不同的问题:①“这个点真是全局最优吗?”②“为什么能写出 KKT 乘子?”③“算法为什么会收敛,速度由哪些假设保证?”不要把它们混成一句“因为凸,所以可以优化”。

一、前六课的证明工具各解决什么问题?

工具 需要核对的假设 真正证明的结论 不能擅自推出
凸集 + 凸函数 可行域凸,目标凸 局部最优即全局最优;可微时一阶变分不等式是充要条件 一定存在有限 KKT 乘子
次梯度 凸函数,可在该点定义次微分 无约束时 $0\in\partial f(x^*)$ 当且仅当全局最优 函数必须可微
欧氏投影 + 法锥 $C$ 非空、闭、凸 投影唯一;边界最优点可以有非零梯度 一阶驻点自动全局最优(非凸时不成立)
支持超平面 / 分离 非空闭凸集与外点 可构造法向,把可行集与外点严格分开 任何非凸集合也有相同结论
Slater + KKT / 对偶 凸约束优化、适当严格可行性、最优值有限且原问题最优可达到 乘子存在、强对偶与 KKT 必要性(标准条件下) Slater 是 KKT 充分性的必要条件
$\mu$-强凸与 $L$-Smooth 曲率上下界、合法步长 唯一最优点、下降界;在适当条件下线性收敛 任意步长稳定;Smooth 自动意味着凸

后文用同一个二维问题把这些行连接起来,而不是分别背结论。

二、从“分离”走到“约束一阶最优性”

令 $C\subseteq\mathbb R^d$ 非空、闭、凸,取外点 $z\notin C$。其欧氏投影 $p=\Pi_C(z)$ 唯一。由投影的最优性,对任意 $u\in C$ 都有

\[(z-p)^\top(u-p)\le 0. \tag{1}\]

这是因为沿可行线段 $p+t(u-p)$,距离平方函数 $|z-p-t(u-p)|^2$ 在 $t=0$ 右导数非负。设 $a=z-p\ne0$,则

\[a^\top u\le a^\top p \quad\text{而}\quad a^\top z=a^\top p+\|a\|^2>a^\top p.\]

所以超平面 $a^\top u=a^\top p$ 把外点和整个凸集严格分离。同一不等式也解释了法锥:

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

对于凸可微 $f$,固定可行 $x^*$,以下三个判据等价:

\[\begin{aligned} x^*\text{ 全局最优} &\iff \nabla f(x^*)^\top(u-x^*)\ge0,\quad\forall u\in C\\ &\iff -\nabla f(x^*)\in N_C(x^*)\\ &\iff x^*=\Pi_C\bigl(x^*-\eta\nabla f(x^*)\bigr),\quad\forall\eta>0. \end{aligned}\tag{2}\]

前两个等价用凸性的一阶下界与沿可行线段求右导数证明;最后一个来自式 (1)。边界最优不需要 $\nabla f(x^*)=0$,而是要求负梯度被法锥“挡住”。

若 $f$ 不可微,要把普通梯度换成次梯度。回顾 $f(t)= t $:在 $t=0$ 有 $\partial f(0)=[-1,1]$,其中包含 0,因此原点全局最优。无约束凸问题的 $0\in\partial f(x^)$ 判据不用强行求不存在的导数。对于带约束的非光滑问题,写 $0\in\partial f(x^)+N_C(x^*)$ 时还要核对次微分求和规则的资格条件,例如 $f$ 在可行点附近连续、且凸定义域兼容。

三、综合数值模型:两个约束活跃,为什么只有一个乘子非零?

考虑

\[\min_{(x,y)\in C} f(x,y) =\frac12\bigl[(x-2)^2+2(y-1)^2\bigr],\] \[C=\{(x,y):x\ge0,\ y\ge0,\ x+y\le2,\ x\le4/3\}. \tag{3}\]

先查假设。 $C$ 是四个闭半空间的交,因此闭且凸;由 $x,y\ge0$ 和 $x+y\le2$ 可知有界,所以最优解存在。$(1/2,1/2)$ 严格满足四条不等式,故满足 Slater。Hessian 为

\[\nabla^2f=\begin{bmatrix}1&0\\0&2\end{bmatrix}, \qquad \mu=1,\quad L=2.\]

目标既 $1$-强凸又 $2$-Smooth,因而最优解唯一。

为找候选点,先检查斜边 $x+y=2$。代入 $y=2-x$:

\[\phi(x)=f(x,2-x)=\tfrac12(3x^2-8x+6), \quad \phi'(x)=3x-4.\]

驻点为 $x^=4/3$、$y^=2/3$,恰好还满足 $x\le4/3$ 的等号。不过沿斜边求出候选点不等于已证明全局最优;接着要检验完整 KKT。

按 $g_i\le0$ 的形式依次写

\[g_1=x+y-2,\quad g_2=x-4/3,\quad g_3=-x,\quad g_4=-y.\]

对应乘子 $\lambda_i\ge0$。在候选点,

\[\nabla f(x^*,y^*)=(-2/3,-2/3).\]

选择

\[\boxed{(\lambda_1,\lambda_2,\lambda_3,\lambda_4) =(2/3,0,0,0).} \tag{4}\]

则驻点条件逐项核对为

\[(-2/3,-2/3)+(2/3)(1,1) +0(1,0)-0(1,0)-0(0,1)=(0,0).\]

两条约束 $g_1=0$ 和 $g_2=0$ 都活跃,但 $\lambda_2=0$。原因不是这条约束“无效”,而是当前目标梯度仅用第一条法向就能平衡。互补松弛只要求 $\lambda_i g_i(x^*)=0$,没有要求“活跃 $\Rightarrow \lambda_i>0$”。

用一张表检查四项,能防止忘记 KKT 的常见错误:

约束 $g_i(x^*)$ 活跃? $\lambda_i^*$ $\lambda_i^g_i(x^)$
$x+y-2\le0$ $0$ 是 $2/3$ $0$
$x-4/3\le0$ $0$ 是 $0$ $0$
$-x\le0$ $-4/3$ 否 $0$ $0$
$-y\le0$ $-2/3$ 否 $0$ $0$

四、KKT 为什么能充当“全局最优证书”?Slater 又负责什么?

对任意凸目标 $f$、凸不等式 $g_i$ 与非负乘子 $\lambda$,拉格朗日函数

\[\mathcal L(u,\lambda)=f(u)+\sum_i\lambda_i g_i(u)\]

对 $u$ 仍凸。如果某可行 $u^$ 与 $\lambda^\ge0$ 同时满足驻点条件、互补松弛,那么

\[\underbrace{f(u)}_{\text{任意可行点}} \ge\mathcal L(u,\lambda^*) \ge\mathcal L(u^*,\lambda^*) =f(u^*),\qquad \forall u\in C. \tag{5}\]

第一步用 $\lambda_i g_i(u)\le0$;第二步用 $\mathcal L(\cdot,\lambda^)$ 凸且在 $u^$ 驻点;最后一步用互补松弛。因此 $u^*$ 必是全局最优。证明这条充分性不需要 Slater;Slater 的典型作用是:在满足标准假设且原问题有最优解时,确保存在这样的有限最优乘子,并让强对偶成立。

在式 (3) 中,以式 (4) 的乘子代入,

\[\mathcal L(x,y,\lambda^*) =f(x,y)+\tfrac23(x+y-2).\]

其梯度零点恰为 $(4/3,2/3)$,故

\[d(\lambda^*)=\min_{x,y}\mathcal L(x,y,\lambda^*) =f(x^*,y^*)=\boxed{\tfrac13}.\]

这既给出原问题的可行上界 $f(x^,y^)=1/3$,也给出对偶下界 $d(\lambda^*)=1/3$。上下界相遇,最优性得到验证。请区分:弱对偶给出下界;零对偶间隙是数值相等;对偶最优可达到是存在有限乘子。三者不是同一个概念。

五、从“最优性证书”走到“可执行算法的收敛界”

同一目标满足全局 Hessian 界 $I\preceq\nabla^2f\preceq2I$。用沿线段积分展开,对 $d=v-u$ 有

\[\begin{aligned} f(v)-f(u)-\nabla f(u)^\top d &=\int_0^1(1-t)d^\top\nabla^2f(u+td)d\,dt,\\ \frac{\mu}{2}\|d\|^2 &\le f(v)-f(u)-\nabla f(u)^\top d \le\frac{L}{2}\|d\|^2. \end{aligned}\tag{6}\]

左边是强凸下界,右边是Smooth 上界;二者分工不同。取投影梯度法

\[u^+=\Pi_C(u-\eta\nabla f(u)),\quad G_\eta(u)=(u-u^+)/\eta.\]

将投影式 (1) 用在 $z=u-\eta\nabla f(u)$、$p=u^+$、比较点 $u$ 上,记 $d=u^+-u$,得到

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

再用式 (6) 的 Smooth 上界:

\[\boxed{f(u^+)\le f(u) -\left(\frac1\eta-\frac L2\right)\|u^+-u\|^2.}\tag{7}\]

所以只要 $0<\eta<2/L$ 且 $u^+\ne u$,就有严格单步下降。这项结论本身甚至不需要强凸;但“函数值下降”远弱于“找到全局最优”。

若进一步有上述全域 Hessian 上下界,还能证明线性距离收敛。因为投影到闭凸集是非扩张映射,而

\[\nabla f(u)-\nabla f(v)=A(u-v),\quad A=\int_0^1\nabla^2f(v+t(u-v))\,dt,\quad \mu I\preceq A\preceq LI,\]

故 $I-\eta A$ 的谱范数至多

\[\rho=\max\{|1-\eta\mu|,\ |1-\eta L|\}.\]

结合最优点的投影不动点条件,有

\[\boxed{\|u_{k+1}-u^*\|\le\rho\|u_k-u^*\|.}\tag{8}\]

当 $0<\eta<2/L$ 且 $\mu>0$ 时 $\rho<1$。这给出几何距离收缩,不能未经额外证明就把相同 $\rho$ 当成任意约束问题的函数值误差收缩因子。

手算两步。 在式 (3) 上从 $u_0=(0,0)$ 开始,取 $\eta=1/L=1/2$,理论上 $\rho=1/2$。

步 原点梯度 未投影步 $z=u-\eta\nabla f(u)$ 投影后 $u_k$ $f(u_k)$
$0$ $(-2,-2)$ — $(0,0)$ $3$
$1$ $(-2,-2)$ $(1,1)$,已可行 $(1,1)$ $0.500000$
$2$ $(-1,0)$ $(1.5,1)$ $(1.25,0.75)$ $0.343750$

第二步将 $(1.5,1)$ 投影到 $x+y=2$,沿法向每个坐标减去 $0.25$;结果仍满足 $x\le4/3$。精确最优值为 $1/3\approx0.333333$。这使优化步骤、活跃边界、KKT 证书、收敛常数在同一个实例中相互印证。

六、失败反例:哪些逻辑箭头不成立?

失败 1:活跃不意味着正乘子。 主例中 $x-4/3=0$,但它的乘子就是 0。若从“取等号”直接推断“乘子大于 0”,会误判临界约束。

失败 2:凸问题不自动拥有有限 KKT 乘子。 比如 $\min_x x$,s.t. $x^2\le0$。唯一可行解 $x^=0$ 也是最优,但驻点要求 $1+\lambda\,2x^=0$,无论取多大的有限 $\lambda$ 都不可能成立;Slater 失效。反过来,Slater 失效也不必然导致 KKT 失败,例如 $\min_x x^2$,s.t. $x^2\le0$ 在 0 处就有 KKT 乘子。Slater 是常见充分资格条件,不是逐个实例的必要条件。

失败 3:Smooth 不意味着凸。 $f(t)=-t^2/2$ 的梯度是 1-Lipschitz,Hessian 却是 $-1$;它没有全局最小点。不能把 Descent Lemma 单独当成全局最优保证。

失败 4:步长越大不一定越快。 $f(t)=t^2/2$ 同时 1-强凸且 1-Smooth,但 $\eta=3$ 时 GD 得 $t_{k+1}=-2t_k$,函数值每步放大四倍,根本不收敛。

七、把证明依赖画成一张图

flowchart TD
  A["凸可行集 C"] --> B["投影不等式 / 法锥"]
  S["凸可微目标 f"] --> D["全局最优 ⇔ 变分不等式"]
  B --> D
  D --> E["最优点是投影不动点"]
  Q["凸约束 + Slater + 原最优可达"] --> K["存在最优 KKT 乘子"]
  K --> M["KKT + 凸性 ⇒ 全局下界证书"]
  H["μI ⪯ Hessian ⪯ LI"] --> T["强凸 + Smooth"]
  T --> R["下降不等式 / 唯一最优"]
  B --> R
  E --> R
  R --> Z["合法步长 + 投影非扩张 ⇒ 距离几何收缩"]

本周复盘自检: 能否解释“法锥为什么容许非零梯度”“Slater 保证什么而不保证什么”“$\mu$ 与 $L$ 哪个控制下界、哪个控制上界”“为什么收敛结论必须标明步长与误差量”?如果能把这些说准确,就可以进入第二周。

八、四级自测|满分 100 分

首次授课不附答案、选项正误或开放题示范证明。 Lv1–Lv3 可客观评分,Lv4 依据推导完整性人工/ChatGPT 评阅。每题考察侧重点不同;作答时可写「1:选项,2:数值,3:选项,4:完整过程」的形式,请独立作答。

Lv1|KKT 的充分性与约束资格条件|15 分|预计 2 分钟|单选

设目标函数与所有不等式约束函数均凸且可微,问题存在最优解。下列哪项一定正确?

A. 只要某约束在最优点活跃,它的 KKT 乘子就必须严格为正。

B. 只要某可行点存在满足驻点、对偶可行性和互补松弛的乘子,它就是全局最优点,即使没有 Slater 条件。

C. 只要 Slater 条件不成立,任何最优点都不可能有 KKT 乘子。

D. 只要目标强凸,任意正步长的普通梯度下降都保证收敛。

可选中立提示:分别区分:KKT 的必要性何时成立,以及一组已存在的 KKT 条件何时足以证明全局最优。

Lv2|活跃约束与 KKT 乘子的数值计算|20 分|预计 4 分钟|数值

求解 min f(x,y)=½[(x−3)²+2(y−1)²],约束 x≥0、y≥0、x+y≤2。记 g(x,y)=x+y−2≤0 的乘子为 λ≥0。求最优 λ*,填一个数(保留三位小数)。

可选中立提示:先检验无约束极小点是否可行;若落在斜边上,将 y=2−x 代入并用驻点条件求 λ。

Lv3|Slater 失效、零对偶间隙与对偶不达到|25 分|预计 5 分钟|单选

考虑一维凸优化 min (x−1)²,s.t. x²≤0,x∈ℝ。哪一项关于原问题、KKT 和拉格朗日对偶的判断正确?

A. 满足 Slater 条件,因为唯一可行点恰好使约束取等号。

B. 存在有限 λ≥0,使唯一原问题最优点满足 KKT 驻点条件。

C. 原问题最优值和对偶上确界都为 1,但没有有限对偶最优乘子。

D. 只要 Slater 不成立,原问题和对偶问题之间必然存在严格正的对偶间隙。

可选中立提示:显式对 x 最小化 (x−1)²+λx²;检查 λ 取有限值还是趋向无穷时才接近对偶上确界。

Lv4|曲率—KKT—投影下降的综合证明|40 分|预计 12 分钟|开放推导

设 C={(x,y): x≥0,y≥0,x+y≤1},f(x,y)=½[(x−3/2)²+4(y−1)²]。定义 x⁺=Π_C(x−η∇f(x)),其中 x 是二维向量。

A(8 分)验证 C 非空闭凸、给出一个严格可行点,并求 f 的 μ 与 L(取最佳二阶全局常数)。

B(14 分)求唯一最优点、各约束的活跃状态及一组 KKT 乘子;再用凸性和拉格朗日函数说明为什么满足 KKT 足以证明全局最优。

C(12 分)从投影变分不等式与 L-Smooth 上界证明 f(x⁺)≤f(x)−(1/η−L/2)‖x⁺−x‖²,指出严格下降需要的步长区间(当 x⁺≠x)。

D(6 分)以 x₀=(0,0)、η=1/4 手算一次投影梯度更新 x₁,写出未投影点及投影后的点。

可选中立提示:先看 Hessian 的特征值。求最优点时可在斜边上消元,再用完整 KKT 核验;投影定理要把原迭代点作为比较点。

九、下一讲与反馈方式

下一讲(第 8 课,2026 年 10 月 27 日): 第二周开始系统研究约束资格条件与 KKT:为什么 LICQ/MFCQ/Slater 的适用对象不同,什么时候乘子唯一,什么时候会退化;继续从活跃约束和互补松弛入手,而非堆抽象名词。

提交四题答案后,将按 Lv1 15 + Lv2 20 + Lv3 25 + Lv4 40 逐题打分并说明错误原因。总分 ≥80:按原日期进度继续;60–79:补对应薄弱点的例题;<60:先集中复习 KKT、法锥与曲率界,再完成同难度巩固练习。不会改变日期课号,也不会提前公布本次测评的标准答案。