第10课|拉格朗日鞍点、原始—对偶间隙与可验证停止准则

2026年10月29日 · 第2周第3天 · 讲授约18分钟(自测另计)

前两讲学习了约束资格条件、弱/强对偶。今天回答更贴近实际求解器的问题:我们如何用一对原始/对偶变量,严格证明解已经足够好? 必须同时区分数学上的鞍点、KKT、可计算间隙,以及未经证明的“残差小就差不多了”。

一、问题、假设与四组KKT条件

考虑 [ \min_{x\in\mathbb R^n} f(x)\quad \mathrm{s.t.}\quad g_i(x)\le0\ (i=1,\ldots,m),\quad Ax=b. ] 暂时假设 (f,g_i) 凸且可微,等式为仿射。定义 [ L(x,\lambda,\nu)=f(x)+\sum_i\lambda_i g_i(x)+\nu^\top(Ax-b), \quad\lambda\ge0,\ \nu\in\mathbb R^r, ] 以及 [ q(\lambda,\nu)=\inf_{z\in\mathbb R^n}L(z,\lambda,\nu). ] 如果存在最优点并满足适当约束资格条件(如标准Slater),KKT乘子存在;但下文“KKT⇒全局最优”并不要求预先假设Slater。

KKT四组条件分别为: [ \underbrace{g_i(x^)\le0,\ Ax^=b}{\text{原始可行}},\quad \underbrace{\lambda_i^*\ge0}{\text{对偶可行}}, ] [ \underbrace{\nabla f(x^)+\sum_i\lambda_i^\nabla g_i(x^)+A^\top\nu^=0}{\text{驻点}},\quad \underbrace{\lambda_i^*g_i(x^*)=0}{\text{互补松弛}}. ] 特别注意活跃约束:(g_i(x^)=0) 只能推出该约束活跃,不意味着 (\lambda_i^>0)。非活跃约束 (g_i(x^*)<0) 才强制乘子为零。

二、什么是拉格朗日鞍点?

对 (x) 求最小,对乘子 ((\lambda,\nu)) 求最大。若存在 ((x^,\lambda^,\nu^)),且 (\lambda^\ge0),使对任何 (x\in\mathbb R^n,\lambda\ge0,\nu\in\mathbb R^r) 都成立 [ \boxed{L(x^,\lambda,\nu)\le L(x^,\lambda^,\nu^)\le L(x,\lambda^,\nu^)}, \tag{1} ] 则称它为拉格朗日鞍点。

左边(固定原始点,乘子方向最大化)如何推出可行性? 如果某 (g_i(x^)>0),固定其他乘子并令 (\lambda_i\to+\infty),左侧会无界增长,矛盾;如果 (Ax^\ne b),可以沿残差方向令自由乘子 (\nu) 的内积无界增长,也矛盾。因此 (x^) 必可行。对于可行点,最大化 (\sum_i\lambda_i g_i(x^)) 的条件还要求 (\lambda_i^g_i(x^)=0):严格不活跃的约束乘子必须为零。

右边(固定乘子,原始方向最小化)意味着 [ x^\in\arg\min_xL(x,\lambda^,\nu^), \quad q(\lambda^,\nu^)=L(x^,\lambda^,\nu^). ] 由可行性与互补松弛,右侧又等于 (f(x^))。因此 [ q(\lambda^,\nu^)=f(x^)=p^=d^. ] 即存在鞍点就给出了原始最优、对偶最优和零对偶间隙的证书。这个“鞍点⇒证书”的论证甚至不要求 (f) 凸,只要以上全局鞍点不等式成立。

反向看,在凸且可微的条件下,如果一对变量满足KKT,则因为 (L(\cdot,\lambda^,\nu^)) 为凸函数且梯度在 (x^*) 为零,它达到全局最小;可行性与互补松弛给出左侧最大化,于是KKT⇒鞍点。非凸时只有驻点条件不能替代全局最小化,因此不能照搬。

三、原始—对偶间隙为什么是可检验的上界?

对任意原始可行点 (x) 和对偶可行乘子 ((\lambda,\nu)),弱对偶保证 [ \boxed{q(\lambda,\nu)\le p^\le f(x)}. ] 因此 [ \boxed{0\le f(x)-p^\le f(x)-q(\lambda,\nu)}. \tag{2} ] 右端完全由当前原始可行目标和合法对偶下界计算而来,是可以检查的最优性误差上界。

进一步将其拆开: [ \begin{aligned} f(x)-q(\lambda,\nu) &=[f(x)-L(x,\lambda,\nu)]+[L(x,\lambda,\nu)-q(\lambda,\nu)]
&=\underbrace{-\sum_i\lambda_i g_i(x)}{\ge0\text{,互补性缺口}} +\underbrace{L(x,\lambda,\nu)-\inf_zL(z,\lambda,\nu)}{\ge0\text{,内层最小化缺口}}. \end{aligned} \tag{3} ] 等式约束的乘子项因为原始可行而消失。两个非负项之和为零意味着所有非负乘子与约束松弛互补,而且当前 (x) 全局最小化固定乘子下的拉格朗日函数。因此,结合可行性,这对变量给出鞍点证书。

如果内层只能近似求解,就不能把计算得到的近似 (L(x_\lambda,\lambda,\nu)) 直接冒充真正的下界 (q=\inf L):因为近似函数值满足 (L(x_\lambda,\lambda,\nu)\ge q),反而可能高估对偶函数。

四、完整一维算例:数值证书与残差

考虑 [ \boxed{\min_{x\le1}\ f(x)=\frac12(x-2)^2}. \tag{4} ] 无约束最优点为2,不可行;约束边界最优点为 (x^=1),(p^=f(1)=1/2)。

采用 (g(x)=x-1\le0): [ L(x,\lambda)=\frac12(x-2)^2+\lambda(x-1),\qquad\lambda\ge0. ] 对 (x) 求导并令零: [ \frac{\partial L}{\partial x}=x-2+\lambda=0 \Rightarrow x(\lambda)=2-\lambda. ] 代回: [ \boxed{q(\lambda)=\lambda-\frac12\lambda^2}. \tag{5} ] 它在 (\lambda^=1) 达到最大值 (d^=1/2),与 (p^) 相等。KKT四组:(1-1=0)、(\lambda^=1\ge0)、(1-2+1=0)、(1(1-1)=0),全部成立。

本例还能把式(3)写为显式平方: [ \boxed{ f(x)-q(\lambda)=\lambda(1-x)+ \frac12(x-2+\lambda)^2}. \tag{6} ] 当 (x\le1,\lambda\ge0) 时,右侧两项非负;第一项检查互补性,第二项检查固定乘子下的驻点/内层最小化是否充分。

对于一般求解器,可以分别监控:

指标 本例定义 希望达到什么    
原始可行残差 (r_p=[x-1]_+=\max(0,x-1)) 0    
对偶可行残差 (r_d=[-\lambda]_+) 0    
驻点残差 (r_s= x-2+\lambda ) 0
互补残差 (r_c= \lambda(x-1) ) 0
可认证间隙 (G=f(x)-q(\lambda))(仅当两端可行时用于非负证书) 小于给定容差    

残差小并不自动保证任意非凸问题的全局最优;在凸优化中可结合误差界、强凸性、数值精度与可行性判定建立保证。最直接的最优值证书仍是满足可行性前提的式(2)。

五、三次对偶梯度迭代及收敛证明

由于 (q’(\lambda)=1-\lambda),投影对偶梯度上升为 [ \lambda_{k+1}=\Pi_{\mathbb R_+}[\lambda_k+\eta(1-\lambda_k)] =\max{0,(1-\eta)\lambda_k+\eta}. ] 取 (\eta=1/2)、(\lambda_0=0)。原始候选始终固定为可行点 (x=1)。计算:

(k) (\lambda_k) (q(\lambda_k)) 证书 (G_k=f(1)-q(\lambda_k)) ( r_s = 1-2+\lambda_k )
0 0 0 0.500000 1        
1 0.5 0.375000 0.125000 0.5        
2 0.75 0.468750 0.031250 0.25        
3 0.875 0.4921875 0.0078125 0.125        

(\lambda^*=1) 是投影更新的不动点。利用欧氏投影非扩张性: [ \begin{aligned} |\lambda_{k+1}-1| &\le|[(1-\eta)\lambda_k+\eta]-[(1-\eta)\cdot1+\eta]|
&=|1-\eta||\lambda_k-1|. \end{aligned} ] 因此 当 (0<\eta<2) 时,有 (|1-\eta|<1),即 [ |\lambda_k-1|\le|1-\eta|^k|\lambda_0-1|. ] 而固定 (x=1) 时 [ G_k=\frac12(1-\lambda_k)^2, ] 所以该证书按照至多 (|1-\eta|^{2k}) 的几何因子下降。本结论只针对本例的光滑强凹二次对偶函数及精确梯度计算;不能直接套用到任意不可微对偶函数。

六、两个必须记住的失败反例

反例A:原始变量不可行,所谓“间隙”竟可以是负数。 在式(4)中取 (x=2)(违反 (x\le1)),取合法 (\lambda=1)。有 (f(2)=0)、(q(1)=1/2),故 [ f(2)-q(1)=-1/2<0. ] 这不违反弱对偶,因为(f(x)) 仅在原始可行时才是 (p^*) 的上界。不能对未经验证的候选点直接报告“最优性已证”。

反例B:存在鞍点不意味着朴素的同时梯度下降—上升一定收敛。 考虑凸等式问题 [ \min_x 0,\quad\mathrm{s.t.}\ x=0, ] 其拉格朗日函数为 (L(x,\nu)=\nu x),鞍点之一是 ((0,0))。对 (x) 做下降、对自由乘子 (\nu) 做同步上升: [ x_{k+1}=x_k-\eta\nu_k,\quad \nu_{k+1}=\nu_k+\eta x_k. ] 直接计算 [ x_{k+1}^2+\nu_{k+1}^2=(1+\eta^2)(x_k^2+\nu_k^2). ] 任何固定 (\eta>0),从非零初值出发,距离反而增长。这说明求解鞍点需要适当算法(例如某些条件下的外梯度、PDHG或近端方法)及其各自的步长和结构假设,不能把“凸—凹”误当成同步梯度法的收敛定理。

七、图解:资格条件、KKT、鞍点和停止准则的分工

flowchart TD
  A["凸目标 + 凸不等式 + 仿射等式"] --> B["存在可行最优点"]
  S["Slater等资格条件(合适假设下)"] --> C["KKT乘子存在"]
  B --> C
  C --> D["满足KKT的原始—对偶点"]
  D --> E["全局拉格朗日鞍点"]
  E --> F["p*=d*=f(x*)=q(λ*,ν*)"]
  G["原始可行 x + 对偶可行乘子"] --> H["q(λ,ν) ≤ p* ≤ f(x)"]
  H --> I["f(x)-q(λ,ν) 为可认证误差上界"]
  F --> I
  J["残差小 / 启发式停止"] -. "没有额外误差界不等于全局证书" .-> I
你想证明什么? 必须检查的条件 能得到的结论
某点满足KKT 原始可行、乘子合法、驻点、互补松弛 凸条件下全局最优
某对点是鞍点 式(1)对所有原始/对偶变量成立 原始与对偶最优、零间隙
当前解离最优值不超过ε 原始可行、乘子对偶可行、(f(x)-q\le\varepsilon) 可验证的目标误差上界
迭代确实收敛 算法更新、光滑/强凸等结构、步长合法 依具体定理而定,不能从KKT直接推断

八、今日四级自测(100分)

以下是首次课堂版本,不展示答案、解析或开放题评分要点;请独立作答,不能提前泄题。

Lv1|鞍点与最优证书|15分|预计2分钟|单选

考虑最小化 f(x),约束 g(x)≤0,拉格朗日函数 L(x,λ)=f(x)+λg(x),其中 λ≥0、x∈R。若存在有限点 (x,λ) 满足对所有 x∈R、λ≥0 都有 L(x,λ)≤L(x,λ)≤L(x,λ),下列哪项一定正确?

A. 仅要求 ∂L/∂x=0 就足以得到鞍点,与凸性和可行性无关。

B. x* 必为原问题可行最优解,而且 q(λ)=f(x),形成零间隙证书。

C. 强对偶只要成立,就必然存在有限最优乘子。

D. 对于非凸问题,任何 KKT 驻点均为全局最优点。

提示:利用鞍点左侧的不等式检验原始可行性和互补松弛,再结合右侧的最小化性质。

Lv2|可行原始—对偶间隙计算|20分|预计3分钟|数值

求最小化 f(x)=1/2(x−3)^2,约束 x≤1。令 L(x,λ)=1/2(x−3)^2+λ(x−1),q(λ)=inf_{z∈R}L(z,λ)。固定原始可行点 x=1、对偶可行乘子 λ=1.5,计算 f(1)−q(1.5)。仅填数值,保留三位小数。

提示:对内层变量 z 求导并代回,注意 f(1) 是原始可行上界。

Lv3|停止证书的逻辑前提|25分|预计5分钟|单选

设原问题为 min f(x),约束 g_i(x)≤0;对偶函数 q(λ)=inf_z L(z,λ)。关于用 f(x)−q(λ) 做最优性停止证书,下列哪一项是严谨的?

A. 即使 x 不可行,只要 λ≥0,就总有 0≤f(x)−p*≤f(x)−q(λ)。

B. 只要驻点残差足够小,就能在任意非凸问题中保证全局最优。

C. 当 x 原始可行、λ 对偶可行时,0≤f(x)−p*≤f(x)−q(λ);若 x 不可行,该差值甚至可能为负。

D. 只要 p=d,所有 λ≥0 都必须达到对偶最优值。

提示:弱对偶给出的下界需要对偶可行,原始目标给出的上界需要原始可行;分别检查两端。

Lv4|鞍点、间隙分解、对偶收敛与敏感度|40分|预计12分钟|开放题

考虑参数化凸优化问题 [ \min_{x\in\mathbb R}\ \frac12(x-4)^2,\qquad \text{s.t. }x\le2. ] 记 (L(x,\lambda)=\frac12(x-4)^2+\lambda(x-2))、(\lambda\ge0)。 A(10分):消去原始变量,求 (q(\lambda))、(x^)、(\lambda^) 与 (p^=d^),并核对四组 KKT 条件。 B(10分):对一般可微凸目标、凸不等式及仿射等式,给出完整的鞍点不等式;从原始可行性、对偶可行性和 (q=\inf_xL) 出发,推导可行点的原始—对偶间隙的两个非负组成部分,解释间隙为零时为何得到最优性证书。 C(10分):固定原始可行点 (x=2),推导 (f(2)-q(\lambda)) 的平方形式;对对偶函数使用投影梯度上升,取 (\eta=1/4,\lambda_0=0),求 (\lambda_1,\lambda_2),证明乘子误差的线性收缩因子。 D(10分):把约束改成 (x\le b),求 (b<4) 时最优值函数 (v(b)) 与最优乘子 (\lambda^(b)),验证 (v’(b)=-\lambda^(b));说明该结论的局部敏感度含义。

提示:对 A:求 x(λ)=4−λ。对 B:把 f(x)−q(λ) 拆成 f−L 和 L−q。对 C:使用投影非扩张性。对 D:先写分段最优点。

九、评分方式与下一讲

四题共100分:Lv1 15分、Lv2 20分、Lv3 25分、Lv4 40分。收到作答后逐题评分、指出错误假设及关键计算。80分及以上按正常课程进度继续;60–79分补充针对性例子;低于60分优先复习活跃约束、KKT和对偶间隙。评分不改变日期课号。

下一讲(2026年10月30日,第11课): 乘子的影子价格含义、最优值函数的灵敏度,以及扰动后哪些约束会改变活跃状态。将从 (v(b)) 的微分公式出发解释何时能写出 (\partial v/\partial b=-\lambda^*)、何时只能谈次梯度,以及对参数变化的数值例子。