動機
受約束最小點的目標梯度可以非零,因為最速下降方向或許不可行。反過來,解出乘子方程也不代表候選點必然是最小點。關鍵在於幾何:哪些方向可由可行曲線實現?沿這些方向目標函數的一階和二階變化又如何?本節在有限維空間中分辨局部最小的必要條件和嚴格局部最小的充分條件。
約束資格條件不可省略:描述同一可行集的不同方程,可能有不同梯度。例如 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 。