动机
受约束最小点的目标梯度可以非零,因为最速下降方向或许不可行。反过来,解出乘子方程也不代表候选点必然是最小点。关键在于几何:哪些方向可由可行曲线实现?沿这些方向目标函数的一阶和二阶变化又如何?本节在有限维空间中分辨局部最小的必要条件和严格局部最小的充分条件。
约束资格条件不可省略:描述同一可行集的不同方程,可能有不同梯度。例如 x 2 ≤ 0 x^2\le0 x 2 ≤ 0 与 x = 0 x=0 x = 0 的可行集相同,前者在零的梯度却为零。依赖梯度线性无关的定理,不能默默把这两种描述当作可以互换。下文函数均定义于所研究点的开邻域,不等式写成 g i ( x ) ≤ 0 g_i(x)\le0 g i ( x ) ≤ 0 。
定义
考虑最小化 f ( x ) f(x) f ( x ) ,约束为 h ( x ) = 0 h(x)=0 h ( x ) = 0 和 g i ( x ) ≤ 0 g_i(x)\le0 g i ( x ) ≤ 0 ,其中 h : R n → R m h:\mathbb R^n\to\mathbb R^m h : R n → R m 。可行点 x ∗ x_* x ∗ 的活跃集是 A = { i : g i ( x ∗ ) = 0 } A=\{i:g_i(x_*)=0\} A = { i : g i ( x ∗ ) = 0 } 。
x ∗ x_* x ∗ 处的线性化锥 为
L ( x ∗ ) = { d : D h ( x ∗ ) d = 0 , ∇ g i ( x ∗ ) T d ≤ 0 对 i ∈ A } . L(x_*)=\{d:Dh(x_*)d=0,\ \nabla g_i(x_*)^Td\le0\text{ 对 }i\in A\}. L ( x ∗ ) = { d : D h ( x ∗ ) d = 0 , ∇ g i ( x ∗ ) T d ≤ 0 对 i ∈ A } . 切方向 是可行割线的极限:存在可行点 x k → x ∗ x_k\to x_* x k → x ∗ 和 t k ↓ 0 t_k\downarrow0 t k ↓ 0 ,使 ( x k − x ∗ ) / t k → d (x_k-x_*)/t_k\to d ( x k − x ∗ ) / t k → d 。若所有等式梯度和活跃不等式梯度线性无关,称 x ∗ x_* x ∗ 处成立线性无关约束资格条件 (LICQ)。
可微性保证切方向属于线性化锥;反方向需要额外条件。
对 λ i ≥ 0 \lambda_i\ge0 λ i ≥ 0 和不受符号限制的 ν j \nu_j ν j ,定义拉格朗日(Lagrange)函数
L ( x , λ , ν ) = f ( x ) + ∑ i λ i g i ( x ) + ν T h ( x ) . \mathcal L(x,\lambda,\nu)=f(x)+\sum_i\lambda_i g_i(x)+\nu^Th(x). L ( x , λ , ν ) = f ( x ) + i ∑ λ i g i ( x ) + ν T h ( x ) .
若可行点 x ∗ x_* x ∗ 存在乘子 λ i ≥ 0 \lambda_i\ge0 λ i ≥ 0 和 ν \nu ν ,使 ∇ x L ( x ∗ , λ , ν ) = 0 \nabla_x\mathcal L(x_*,\lambda,\nu)=0 ∇ x L ( x ∗ , λ , ν ) = 0 ,且对每个 i i i 有 λ i g i ( x ∗ ) = 0 \lambda_ig_i(x_*)=0 λ i g i ( x ∗ ) = 0 ,则称 x ∗ x_* x ∗ 为 KKT 点 。其临界锥 是 C ( x ∗ ) = { d ∈ L ( x ∗ ) : ∇ f ( x ∗ ) T d = 0 } C(x_*)=\{d\in L(x_*):\nabla f(x_*)^Td=0\} C ( x ∗ ) = { d ∈ L ( x ∗ ) : ∇ f ( x ∗ ) T d = 0 } 。
目标的一阶变化若严格为正,小步已不利;二阶分析主要针对临界方向。由 KKT 符号及互补条件,每个临界方向在 λ i > 0 \lambda_i>0 λ i > 0 时亦有 ∇ g i ( x ∗ ) T d = 0 \nabla g_i(x_*)^Td=0 ∇ g i ( x ∗ ) T d = 0 。
定理/命题
设 f f f 在 x ∗ x_* x ∗ 附近二阶连续可微。若 x ∗ x_* x ∗ 是无约束局部最小点,则 ∇ f ( x ∗ ) = 0 \nabla f(x_*)=0 ∇ f ( x ∗ ) = 0 ,且对所有 d d d 有 d T ∇ 2 f ( x ∗ ) d ≥ 0 d^T\nabla^2f(x_*)d\ge0 d T ∇ 2 f ( x ∗ ) d ≥ 0 。反之,若梯度为零且 Hessian 正定,则 x ∗ x_* x ∗ 是严格局部最小点。
定理 4.1.4
(LICQ 下的 KKT 与二阶条件)
设 f , h , g f,h,g f , h , g 在可行局部最小点 x ∗ x_* x ∗ 附近皆为 C 2 C^2 C 2 ,且 LICQ 成立。则存在唯一 KKT 乘子,并对每个 d ∈ C ( x ∗ ) d\in C(x_*) d ∈ C ( x ∗ ) 有
d T ∇ x x 2 L ( x ∗ , λ , ν ) d ≥ 0. d^T\nabla^2_{xx}\mathcal L(x_*,\lambda,\nu)d\ge0. d T ∇ xx 2 L ( x ∗ , λ , ν ) d ≥ 0. 反之,在任何可行 KKT 点,若此二次型对每个非零临界方向严格为正,则该点为具有二次增长的严格局部最小点:存在 c , r > 0 c,r>0 c , r > 0 ,使距离小于 r r r 的每个可行 x x x 均满足 f ( x ) ≥ f ( x ∗ ) + c ∥ x − x ∗ ∥ 2 f(x)\ge f(x_*)+c\|x-x_*\|^2 f ( x ) ≥ f ( x ∗ ) + c ∥ x − x ∗ ∥ 2 。
一旦已知 KKT 乘子与上述正性,充分结论不需 LICQ。必要条件的半正定性不是充分条件:− x 4 -x^4 − x 4 在零的梯度和 Hessian 都为零,却有严格局部最大值。充分条件亦非必要,x 4 x^4 x 4 在零便有严格最小值,但 Hessian 不正定。
没有资格条件时,仍有一个较弱的必要条件。
设 f , h , g f,h,g f , h , g 在可行局部最小点 x ∗ x_* x ∗ 附近连续可微。则存在 α ≥ 0 \alpha\ge0 α ≥ 0 、λ ≥ 0 \lambda\ge0 λ ≥ 0 及 ν \nu ν ,不全为零,使
α ∇ f ( x ∗ ) + D h ( x ∗ ) T ν + ∑ i λ i ∇ g i ( x ∗ ) = 0 , λ i g i ( x ∗ ) = 0. \alpha\nabla f(x_*)+Dh(x_*)^T\nu+\sum_i\lambda_i\nabla g_i(x_*)=0,
\qquad \lambda_i g_i(x_*)=0. α ∇ f ( x ∗ ) + D h ( x ∗ ) T ν + i ∑ λ i ∇ g i ( x ∗ ) = 0 , λ i g i ( x ∗ ) = 0. 若 x ∗ x_* x ∗ 处 LICQ 成立,则每个这样的关系都有 α > 0 \alpha>0 α > 0 。
证明思路
无约束方向
把函数限制于直线 x ∗ + t d x_*+td x ∗ + t d 。一变量局部最小点的一阶导数为零、二阶导数非负;任意 d d d 均如此,便得到梯度为零及 Hessian 半正定。反过来,正定二次型在紧致的单位球面上有正下界 μ \mu μ 。Taylor 公式的余项是 o ( ∥ s ∥ 2 ) o(\|s\|^2) o ( ∥ s ∥ 2 ) ,故充分小的非零 s s s 满足 f ( x ∗ + s ) ≥ f ( x ∗ ) + μ ∥ s ∥ 2 / 4 f(x_*+s)\ge f(x_*)+\mu\|s\|^2/4 f ( x ∗ + s ) ≥ f ( x ∗ ) + μ ∥ s ∥ 2 /4 。
LICQ 如何给出 KKT
对每个 d ∈ L ( x ∗ ) d\in L(x_*) d ∈ L ( x ∗ ) ,LICQ 保证存在 u u u ,使 D h ( x ∗ ) u = 0 Dh(x_*)u=0 D h ( x ∗ ) u = 0 且所有活跃 i i i 均有 ∇ g i ( x ∗ ) T u = − 1 \nabla g_i(x_*)^Tu=-1 ∇ g i ( x ∗ ) T u = − 1 。故 d + ϵ u d+\epsilon u d + ϵ u 沿每个活跃不等式严格下降。隐函数定理沿这个初速度建立可行曲线,用 O ( t 2 ) O(t^2) O ( t 2 ) 的修正满足等式。充分小的正 t t t 令活跃不等式严格,不活跃约束亦保持可行。局部最优因此给出 ∇ f ( x ∗ ) T ( d + ϵ u ) ≥ 0 \nabla f(x_*)^T(d+\epsilon u)\ge0 ∇ f ( x ∗ ) T ( d + ϵ u ) ≥ 0 ;令 ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 ,得对整个线性化锥的非负方向导数。
有限维 Farkas 择一定理给出 − ∇ f ( x ∗ ) = D h ( x ∗ ) T ν + ∑ i ∈ A λ i ∇ g i ( x ∗ ) -\nabla f(x_*)=Dh(x_*)^T\nu+\sum\limits_{i\in A}\lambda_i\nabla g_i(x_*) − ∇ f ( x ∗ ) = D h ( x ∗ ) T ν + i ∈ A ∑ λ i ∇ g i ( x ∗ ) ,其中 λ i ≥ 0 \lambda_i\ge0 λ i ≥ 0 。其几何理由是:若负梯度不在活跃梯度所生的闭多面锥加等式梯度子空间内,分离超平面会给出线性化锥内一个与梯度内积为负的方向,矛盾。令不活跃乘子为零;LICQ 使这个表示唯一。
二阶必要性
固定 d ∈ C ( x ∗ ) d\in C(x_*) d ∈ C ( x ∗ ) ,令 B B B 包含沿 d d d 的方向导数为零的活跃不等式。等式梯度与 B B B 的梯度仍线性无关。隐函数定理建立 C 2 C^2 C 2 曲线 x ( t ) x(t) x ( t ) ,满足 x ( 0 ) = x ∗ x(0)=x_* x ( 0 ) = x ∗ 、x ′ ( 0 ) = d x'(0)=d x ′ ( 0 ) = d 、所有等式及 g i ( x ( t ) ) = 0 g_i(x(t))=0 g i ( x ( t )) = 0 (i ∈ B i\in B i ∈ B )。其余活跃不等式的方向导数为负,故小的正 t t t 时严格成立;原先不活跃者也保持严格。因此曲线在正侧可行。
由互补松弛及临界性,乘子为正的活跃约束都在 B B B 中。曲线上 L ( x ( t ) , λ , ν ) = f ( x ( t ) ) \mathcal L(x(t),\lambda,\nu)=f(x(t)) L ( x ( t ) , λ , ν ) = f ( x ( t )) ,一阶导数为零;局部最小性令右二阶导数非负。驻点条件消去含 x ′ ′ ( 0 ) x''(0) x ′′ ( 0 ) 的项,剩下的正是 d T ∇ x x 2 L d ≥ 0 d^T\nabla^2_{xx}\mathcal L\,d\ge0 d T ∇ xx 2 L d ≥ 0 。
曲线约束的曲率因此进入判别;仅看目标 Hessian 并不够。
二阶充分性
若二次增长不成立,便存在可行 x k → x ∗ x_k\to x_* x k → x ∗ ,令 s k = x k − x ∗ ≠ 0 s_k=x_k-x_*\ne0 s k = x k − x ∗ = 0 ,并有 f ( x k ) < f ( x ∗ ) + ∥ s k ∥ 2 / k f(x_k)<f(x_*)+\|s_k\|^2/k f ( x k ) < f ( x ∗ ) + ∥ s k ∥ 2 / k 。单位方向 d k = s k / ∥ s k ∥ d_k=s_k/\|s_k\| d k = s k /∥ s k ∥ 有收敛子列,极限为单位向量 d ∈ L ( x ∗ ) d\in L(x_*) d ∈ L ( x ∗ ) 。可行性和驻点条件给出 ∇ f ( x ∗ ) T d ≥ 0 \nabla f(x_*)^Td\ge0 ∇ f ( x ∗ ) T d ≥ 0 ,目标值不等式给出相反不等式,因此 d d d 临界。对可行 x k x_k x k ,非负乘子使 L ( x k , λ , ν ) ≤ f ( x k ) \mathcal L(x_k,\lambda,\nu)\le f(x_k) L ( x k , λ , ν ) ≤ f ( x k ) ,而在 x ∗ x_* x ∗ 取等号。Taylor 展开及驻点条件得到
1 2 d k T ∇ x x 2 L ( x ∗ , λ , ν ) d k + o ( 1 ) < 1 / k . \tfrac12d_k^T\nabla^2_{xx}\mathcal L(x_*,\lambda,\nu)d_k+o(1)<1/k. 2 1 d k T ∇ xx 2 L ( x ∗ , λ , ν ) d k + o ( 1 ) < 1/ k . 取极限便与所有非零临界方向的严格正性矛盾。
证明透视
充分性证明中各假设的位置 证明从不构造可行曲线,而是从一个假想的坏序列出发导出矛盾。第一步用单位球面的紧致性抽出极限方向 d d d ,正是紧致性把逐方向正性转成一致的局部结论。序列可行使 d d d 落在线性化锥中;驻点条件与 λ ≥ 0 \lambda\ge0 λ ≥ 0 给出 ∇ f ( x ∗ ) T d ≥ 0 \nabla f(x_*)^Td\ge0 ∇ f ( x ∗ ) T d ≥ 0 ,假设的缓慢增长给出相反不等式,所以 d d d 落在临界锥中,而正性只在这个集合上假设。关键一步是用拉格朗日函数代替 f f f :非负乘子与可行性给出 L ( x k ) ≤ f ( x k ) \mathcal L(x_k)\le f(x_k) L ( x k ) ≤ f ( x k ) ,互补松弛给出 L ( x ∗ ) = f ( x ∗ ) \mathcal L(x_*)=f(x_*) L ( x ∗ ) = f ( x ∗ ) ,驻点条件消去一阶 Taylor 项,于是只剩 L \mathcal L L 的二阶项必须很小。这里没有出现资格条件,因为乘子是给定的,而不是推导出来的。
没有资格条件时的 Fritz John 条件
不假设 LICQ 时,Fritz John 定理允许非负目标乘子 α \alpha α 与 λ ≥ 0 \lambda\ge0 λ ≥ 0 并存。α = 0 \alpha=0 α = 0 称为异常情形,可能完全没有提供关于目标函数的信息。下述一般 Fritz John 证明假设局部最小点附近的函数连续可微。若 LICQ 成立,异常驻点关系因梯度线性无关而迫使所有乘子为零,所以 α > 0 \alpha>0 α > 0 ,归一化可得 KKT。此条件是必要而非充分。
反例模式
不是 KKT 点的最小点 一个诱人的说法是:每个局部最小点都是 KKT 点。在 g 1 ( x ) = x 2 − x 1 3 ≤ 0 g_1(x)=x_2-x_1^3\le0 g 1 ( x ) = x 2 − x 1 3 ≤ 0 及 g 2 ( x ) = − x 2 ≤ 0 g_2(x)=-x_2\le0 g 2 ( x ) = − x 2 ≤ 0 下最小化 x 1 x_1 x 1 。可行性迫使 0 ≤ x 2 ≤ x 1 3 0\le x_2\le x_1^3 0 ≤ x 2 ≤ x 1 3 ,故 x 1 ≥ 0 x_1\ge0 x 1 ≥ 0 ,所以原点是全局最小点。两个约束在原点都活跃,梯度 ∇ g 1 = ( 0 , 1 ) T \nabla g_1=(0,1)^T ∇ g 1 = ( 0 , 1 ) T 与 ∇ g 2 = ( 0 , − 1 ) T \nabla g_2=(0,-1)^T ∇ g 2 = ( 0 , − 1 ) T 线性相关,LICQ 失败。KKT 驻点条件会是 ( 1 , 0 ) T + λ 1 ( 0 , 1 ) T + λ 2 ( 0 , − 1 ) T = 0 (1,0)^T+\lambda_1(0,1)^T+\lambda_2(0,-1)^T=0 ( 1 , 0 ) T + λ 1 ( 0 , 1 ) T + λ 2 ( 0 , − 1 ) T = 0 ,其第一个分量给出 1 = 0 1=0 1 = 0 。线性化锥 { d : d 2 = 0 } \{d:d_2=0\} { d : d 2 = 0 } 包含 ( − 1 , 0 ) T (-1,0)^T ( − 1 , 0 ) T ,但每个可行点都有 x 1 ≥ 0 x_1\ge0 x 1 ≥ 0 ,所以它不是切方向。Fritz John 条件以异常选择 α = 0 \alpha=0 α = 0 、λ 1 = λ 2 = 1 \lambda_1=\lambda_2=1 λ 1 = λ 2 = 1 成立。KKT 必要性需要资格条件。
Fritz John 必要性可直接用有限维罚函数证明。选一个以 x ∗ x_* x ∗ 为中心的闭球,使球内所有可行点的目标值不小于 f ( x ∗ ) f(x_*) f ( x ∗ ) 。对 ε > 0 \varepsilon>0 ε > 0 ,在闭球上最小化
P ε ( x ) = [ ( f ( x ) − f ( x ∗ ) + ε ) + 2 + ∑ i ( g i ( x ) + ) 2 + ∥ h ( x ) ∥ 2 ] 1 / 2 + ∥ x − x ∗ ∥ 2 , P_\varepsilon(x)=\left[(f(x)-f(x_*)+\varepsilon)_+^2+
\sum_i(g_i(x)_+)^2+\|h(x)\|^2\right]^{1/2}+\|x-x_*\|^2, P ε ( x ) = [ ( f ( x ) − f ( x ∗ ) + ε ) + 2 + i ∑ ( g i ( x ) + ) 2 + ∥ h ( x ) ∥ 2 ] 1/2 + ∥ x − x ∗ ∥ 2 , 其中 a + = max ( a , 0 ) a_+=\max(a,0) a + = max ( a , 0 ) 。连续性及紧致性给出最小点 x ε x_\varepsilon x ε ;因 P ε ( x ε ) ≤ P ε ( x ∗ ) = ε P_\varepsilon(x_\varepsilon)\le P_\varepsilon(x_*)=\varepsilon P ε ( x ε ) ≤ P ε ( x ∗ ) = ε ,故 x ε → x ∗ x_\varepsilon\to x_* x ε → x ∗ ,充分小的 ε \varepsilon ε 时它在球内部。根号项在此不可能为零:否则该点可行,且 f ( x ε ) ≤ f ( x ∗ ) − ε f(x_\varepsilon)\le f(x_*)-\varepsilon f ( x ε ) ≤ f ( x ∗ ) − ε ,违反局部最小性。
在 x ε x_\varepsilon x ε ,正部分的平方可微。把各残差除以正的根号项,将所得系数记为 α ε \alpha_\varepsilon α ε 、λ ε \lambda_\varepsilon λ ε 及 ν ε \nu_\varepsilon ν ε ,则前两者非负,并满足
α ε 2 + ∥ λ ε ∥ 2 + ∥ ν ε ∥ 2 = 1 , α ε ∇ f + ∑ i λ ε i ∇ g i + D h T ν ε + 2 ( x ε − x ∗ ) = 0 , \alpha_\varepsilon^2+\|\lambda_\varepsilon\|^2+\|\nu_\varepsilon\|^2=1,
\quad
\alpha_\varepsilon\nabla f+\sum_i\lambda_{\varepsilon i}\nabla g_i+Dh^T\nu_\varepsilon+2(x_\varepsilon-x_*)=0, α ε 2 + ∥ λ ε ∥ 2 + ∥ ν ε ∥ 2 = 1 , α ε ∇ f + i ∑ λ ε i ∇ g i + D h T ν ε + 2 ( x ε − x ∗ ) = 0 , 各导数在 x ε x_\varepsilon x ε 评估。取归一化系数的收敛子列,其极限非零,满足驻点与非负条件;若 g i ( x ∗ ) < 0 g_i(x_*)<0 g i ( x ∗ ) < 0 ,则附近的正部分为零,所以极限乘子亦为零。这证明 Fritz John 的互补松弛。无约束情形只需第一个平方,不必加入虚构约束。
罚函数构造只在局部进行:把闭球选在函数连续可微的邻域内,才能使用一阶计算。紧致性给出罚函数的最小点,并不表示原约束问题有全局解。
比 LICQ 弱的资格条件
LICQ 虽方便,却排除重复约束,即使重复本身没有造成困难。KKT 必要性的一个较弱充分条件如下。
定义 4.1.6
(Mangasarian–Fromovitz 资格条件)
若等式梯度线性无关,且存在 u u u 使 D h ( x ∗ ) u = 0 Dh(x_*)u=0 D h ( x ∗ ) u = 0 ,并对每个活跃不等式有 ∇ g i ( x ∗ ) T u < 0 \nabla g_i(x_*)^Tu\lt 0 ∇ g i ( x ∗ ) T u < 0 ,则称 x ∗ x_* x ∗ 处成立 Mangasarian–Fromovitz 资格条件 (MFCQ)。
对线性化锥中的每个 d d d ,上面的可行曲线论证可用于 d + ϵ u d+\epsilon u d + ϵ u ;Farkas 择一定理再给出乘子。但此较弱条件不像 LICQ 那样保证乘子唯一。
例如在 x ≤ 0 x\le0 x ≤ 0 和 2 x ≤ 0 2x\le0 2 x ≤ 0 下最小化 − x -x − x 。零点两个约束均活跃,其梯度线性相关;方向 u = − 1 u=-1 u = − 1 却令两者严格下降,故较弱条件成立。KKT 驻点方程为 − 1 + λ 1 + 2 λ 2 = 0 -1+\lambda_1+2\lambda_2=0 − 1 + λ 1 + 2 λ 2 = 0 ;任何满足 λ 1 + 2 λ 2 = 1 \lambda_1+2\lambda_2=1 λ 1 + 2 λ 2 = 1 的非负乘子对都有效。最小点明确,重复描述之间如何分配影子价格却不唯一。
边界曲线的二阶修正
满足线性化约束的方向不一定令直线 x ∗ + t d x_*+td x ∗ + t d 可行。单位圆在 ( 0 , − 1 ) (0,-1) ( 0 , − 1 ) 的切方向 ( 1 , 0 ) (1,0) ( 1 , 0 ) 产生 ( t , − 1 ) (t,-1) ( t , − 1 ) ,非零 t t t 时位于圆外;可行曲线 ( t , − 1 − t 2 ) (t,-\sqrt{1-t^2}) ( t , − 1 − t 2 ) 在零有相同一阶导数,第二坐标却以二阶改变。这恰是目标可能区分候选点的阶数,亦解释约束二阶导数为何通过乘子进入拉格朗日 Hessian。
此例沿曲线有 f ( t , − 1 − t 2 ) = − 1 − t 2 = − 1 + t 2 / 2 + o ( t 2 ) f(t,-\sqrt{1-t^2})=-\sqrt{1-t^2}=-1+t^2/2+o(t^2) f ( t , − 1 − t 2 ) = − 1 − t 2 = − 1 + t 2 /2 + o ( t 2 ) 。拉格朗日二次型在 d = ( 1 , 0 ) d=(1,0) d = ( 1 , 0 ) 的值为一,Taylor 公式因而给出同样的 1 / 2 1/2 1/2 系数。只用目标 Hessian 沿直线计算会错误地得出没有二阶变化,因为该直线并不可行。
例题详解
f ( x , y ) = x 2 − y 2 f(x,y)=x^2-y^2 f ( x , y ) = x 2 − y 2 在原点驻定,但 Hessian 的二次型有正有负。沿 ( t , 0 ) (t,0) ( t , 0 ) 值上升,沿 ( 0 , t ) (0,t) ( 0 , t ) 值下降。必要 Hessian 测试失败,因此驻点不是充分证据。
例题 4.1.8
(曲线等式与拉格朗日 Hessian)
在 h ( x , y ) = x 2 + y 2 − 1 = 0 h(x,y)=x^2+y^2-1=0 h ( x , y ) = x 2 + y 2 − 1 = 0 下最小化 f ( x , y ) = y f(x,y)=y f ( x , y ) = y 。在 ( 0 , − 1 ) (0,-1) ( 0 , − 1 ) ,y + ν h y+\nu h y + ν h 的驻点条件给 ν = 1 / 2 \nu=1/2 ν = 1/2 ;∇ h = ( 0 , − 2 ) ≠ 0 \nabla h=(0,-2)\ne0 ∇ h = ( 0 , − 2 ) = 0 ,所以 LICQ 成立。切方向为 ( a , 0 ) (a,0) ( a , 0 ) ,拉格朗日 Hessian 为 I I I ,在非零切方向上正定。充分定理给出严格局部最小;圆的几何亦显示它全局最小。目标 Hessian 本身为零,会漏掉约束曲率。
在 x ≤ 0 x\le0 x ≤ 0 下最小化 x 2 x^2 x 2 。零点的 λ = 0 \lambda=0 λ = 0 ,LICQ 成立,临界锥为 d ≤ 0 d\le0 d ≤ 0 。拉格朗日 Hessian 是 2 2 2 ,在每个非零临界方向上为正,所以零点有二次增长。若把临界锥换成所有活跃梯度的零空间,所得充分测试可能失效。例如在 x ≤ 0 x\le0 x ≤ 0 下最小化 − x 2 -x^2 − x 2 ;零点的 KKT 乘子为零,活跃梯度零空间只有 { 0 } \{0\} { 0 } ,对非零向量的正性条件自动成立,但零是局部最大点而非最小点。真正的临界锥为 d ≤ 0 d\le0 d ≤ 0 ,拉格朗日 Hessian 在非零方向为负。
常见错误
LICQ 是 KKT 必要性的充分条件,不是某个 KKT 证书存在的必要条件。重复约束 x ≤ 0 x\le0 x ≤ 0 、2 x ≤ 0 2x\le0 2 x ≤ 0 在零点违反 LICQ,但最小化 − x -x − x 的问题在该处仍有一整段乘子。
活跃约束可以有零乘子。整个空间上的 Hessian 半正定,比约束问题的必要条件强;只在等式切方向检查正性又可能漏掉弱活跃不等式方向,而只在所有活跃梯度的零空间上检查正性可能是空洞的,x ≤ 0 x\le0 x ≤ 0 上的 − x 2 -x^2 − x 2 就是一例。
常见错误
(把异常 Fritz John 乘子归一化)
Fritz John 允许异常乘子,必须先证明 α > 0 \alpha>0 α > 0 (例如由 LICQ)才能归一化。
可选 乘子度量的是什么? 在额外假设下,它是放宽约束时最优值的变化率。
自然的下一个问题
乘子度量的是什么? 在额外假设下,它是放宽约束时最优值的变化率。
把圆的例子扰动为 x 2 + y 2 − 1 = u x^2+y^2-1=u x 2 + y 2 − 1 = u 。极小点变为 ( 0 , − 1 + u ) (0,-\sqrt{1+u}) ( 0 , − 1 + u ) ,最优值为 V ( u ) = − 1 + u V(u)=-\sqrt{1+u} V ( u ) = − 1 + u ,所以 V ′ ( 0 ) = − 1 / 2 = − ν V'(0)=-1/2=-\nu V ′ ( 0 ) = − 1/2 = − ν 。一般的灵敏度结果在我们的符号约定下给出同样的结论:若 LICQ、严格二阶条件与严格互补性都成立,则约束为 h = u h=u h = u 、g ≤ w g\le w g ≤ w 的问题的局部最优值在零附近可微,梯度为 ( − ν , − λ ) (-\nu,-\lambda) ( − ν , − λ ) 。其证明把隐函数定理用于 KKT 方程组,超出了本节范围。
关闭
总结
局部最小点先限制可行方向的变化。LICQ 把线性化锥连到实际可行曲线并给出 KKT 乘子。临界方向上的拉格朗日 Hessian 给出二阶必要测试;严格正性给出二次增长。这些是局部结论,额外结构才可推全局最优。
练习
快速检查
(判断 x 2 + 4 y 2 x^2+4y^2 x 2 + 4 y 2 及 x 2 − y 2 x^2-y^2 x 2 − y 2 在原点的类型。)
解答 第一个 Hessian diag ( 2 , 8 ) \operatorname{diag}(2,8) diag ( 2 , 8 ) 正定,故驻点为严格最小。第二个 Hessian 不定;原点任意邻域内都有正值和负值,故为鞍点。
快速检查
(在 x + y = 2 x+y=2 x + y = 2 下最小化 x 2 + y 2 x^2+y^2 x 2 + y 2 ,求乘子并验证二阶条件。)
解答 令 h = x + y − 2 h=x+y-2 h = x + y − 2 ,驻点条件 2 x + ν = 2 y + ν = 0 2x+\nu=2y+\nu=0 2 x + ν = 2 y + ν = 0 ,可行性给 ( 1 , 1 ) (1,1) ( 1 , 1 ) 、ν = − 2 \nu=-2 ν = − 2 。切方向满足 d 1 + d 2 = 0 d_1+d_2=0 d 1 + d 2 = 0 ,拉格朗日 Hessian 2 I 2I 2 I 对所有非零方向正定。由凸性亦得全局最小。
快速检查
(在 x 2 ≤ 0 x^2\le0 x 2 ≤ 0 下最小化 x x x ,解释零点为何不满足 KKT,并给出 Fritz John 乘子。)
解答 零是唯一可行点。KKT 驻点条件在零要求 1 + 2 λ x = 0 1+2\lambda x=0 1 + 2 λ x = 0 ,不可能。取 α = 0 \alpha=0 α = 0 、λ = 1 \lambda=1 λ = 1 得 Fritz John 条件;约束梯度为零,LICQ 失败,此乘子异常。
快速检查
(在 x ≥ 0 x\ge0 x ≥ 0 下最小化 x + x 2 x+x^2 x + x 2 。求零点的 KKT 乘子及临界锥;它是否为严格局部最小点?)
解答 写 g = − x ≤ 0 g=-x\le0 g = − x ≤ 0 ,零点驻点条件为 1 − λ = 0 1-\lambda=0 1 − λ = 0 ,故 λ = 1 \lambda=1 λ = 1 。线性化锥为 d ≥ 0 d\ge0 d ≥ 0 ,临界性要求 d = 0 d=0 d = 0 ,故临界锥只有零。充分条件中的正性自动成立。直接检查,充分小的可行 x > 0 x>0 x > 0 均有 x + x 2 > 0 x+x^2>0 x + x 2 > 0 。