劉應興的部落格

如果有一個問題，要找 f(x,z) 之極值（極大、極小）, 條件是 x, y 滿足 g(x,y) = 0，微積分中兩個方法，一是解出 z = h(x) 或 x = h(z)，代入 f，變成單變量函數；另一種方法是所謂 Lagrange 乘數法：令

F(x,z,λ) = f(x,z) - λg(x,z)

而後對 x, z, λ 偏微以尋找所謂臨界點或平穩點，而結果 f 函數值是極大或極小用所謂 bordered Hessian （鑲邊 Hessian）來判斷。

Lagrange 乘數法是怎麼來的？鑲邊 Hessian 怎麼用？我們先以一個 z, 一個限制式 g(x,z) = 0 來探討。如果 g(x,z) 是可微分的，在適當條件下可解出 z = h(x) 也是可微分的，而且

dz/dx = - Dx(g(x,z))/Dz(g(x,z))

式中 Dx, Dz 代表對 x, z 的偏微分，即 g 對 x, z 的偏導式。如果 f 也是可微分，則

df(x,h(x))/dx = Dx(f(x,z)) + Dz(f(x,z))(dz/dx)
                    = Dx(f(x,z)) - Dz(f(x,z))Dx(g(x,z))/Dz(g(x,z))

如果 f(x,h(x)) 的極值是發生在可微分的 x 處，則其導數是 0, 也就是

　　Dx(f(x,z)) -（Dz(f(x,z))/Dz(g(x,z))）Dx(g(x,z)) = 0

取 λ = Dz(f(x,z))/Dz(g(x,z)), 加上限制式 g(x,z) = 0, 即是 Lagrange 乘數法的極值條件式；反之，本例的 Lagrange 乘數法中對 z 偏微結果條件式就是告訴我們 λ 要那樣取。

如果極值所在確實可用微分並設導數為 0 來求得，又它是二階可微的，那麼第二階導數可以讓我們判斷在上述臨界點得到的是相對（局部）極大或極小：

   d^2f(x,h(x))/dx^2
      = (Dxx f - λ Dxx g) + (Dzz f - λ Dzz g)(dz/dx)^2 + 2(Dxz f - λ Dxz g)(dz/dx)

式中 λ = (Dz f)/(Dz g) 而 dz/dx = -(Dx g)/(Dz g)。將上列第二階全導數乘以非負的 (Dz g)^2，則得所謂鑲邊 Hessian 矩陣行列式值的相反數，鑲邊 Hessian 矩陣是

　Dλλ F    Dλx F    Dλz F            0     -Dx g    -Dz g

　Dλx F    Dxx F    Dxz F    =    -Dx g    Dxx F    Dxz F

　Dλz F    Dxz F    Dzz F         -Dz g    Dxz F    Dzz F

其中 F 是前述 Lagrage 函數式 F(x,z,λ) = f(x,z)-λg(x,z)。如果 dz/dx 存在，意謂 g 對 z 的偏遵數不為 0, 則鑲邊 Hessian 矩陣 B 行列式正負恰與縮減目標函數 f(x,h(x)) 的第二階導數相反，因此 |B| > 0 表示第二階全導數是負的，我們得局部極大；反之，|B| < 0 表示第二階全導數是正的，則得到的是相對極小。

把 Lagrange 法極值條件用梯度 (gradient) 向量表示，即 ▽f = λ▽g, 且 g = 0。後者是本來的限制，▽f, 和 ▽f = λ▽g, 分別是 f 和 g 雙變量函數的瞬間增速度向量，因此條件 ▽f = λ▽g, 表示要達極值，在可微分的情形，在極值達成點，目標函數 f 和限制函數 g 的最陡增速方向必須一致。另一方面，在單自由變量 x, 單限制式 g = 0 的情形，前述條件式等同於

 -(Dx f(x,z))/(Dz f(x,z)) = -(Dx g(x,z))/(Dz g(x,z))

意謂在極值 K 達成處，曲線 f(x,z) = K 與限制曲線 g(x,z) = 0 相切（斜率一致）。注意這都在一些「可微分」條件下導得的結果，而實際上尋找極值還需考慮不可微分或導數不存在的情形，還有區域邊界，就像定義於有限區間之單邊量函數需考慮端點，有限制條件式之下找極值也要考慮極值可能發生在範圍邊界，此時 ▽f = λ▽g 的條件並不適用。

如果自由變數 x 不是單變量，x 基本上是向量，假設限制條件只有一個 g(x,z) = 0, 則 z = h(x), 前述 x 是單變量的 Lagrange 法仍有用。假設極值發生在可微處，則條件仍是 ▽f = λ▽g, 其原理與單變量 x 時完全相同，只是此時如何用鑲邊 Hessian 矩陣判定一個臨界點是相對極大？極小？或是鞍點？此時用縮減目標函數（簡稱 RTF） f*(x) = f(x,h(x)) 來看，我們需要看 RTF 的 Hessian 矩陣，由其二階偏導數所組成的對稱方陣（假設交叉偏導數與微分順序無關）, 其二階偏導數如下：

　　f*_ii = F_ii + 2F_iz (dz/dx_i) + F_zz (dz/dx_i)^2
　　f*_ij = F_ij + F_iz (dz/dx_j) + F_jz (dz/dx_i) + Fzz (dz/dx_i)(dz/dx_j)

式中 f*_ii  代表 f*(x) 對 x_i 的二階偏導數，f*_ij 是對 x_i 和 x_j 的第二階交叉偏導數。Lagrange 函數 F = f - λg, 其中 λ = f_z/g_z 如前面 x 為單變量時一般。被「解出」變數 z = h(x) 也是多變量函數，所以 dz/dx_i = - g_i/g_z 也是偏導數。由這些 f*_ij 所構成的 Hessian 矩陣 H* 在 Lagrange 臨界點如果是負確定 (negative definite)，則在此臨界點得到的就是受限之下 f，或縮減式 f* 得一相對極大；如果 H* 是正確定，則得到的是相對極小。但這又如何和鑲邊 Hessian 矩陣 B 連繫？鑲邊 Hessian 矩陣 B 是

0     g_1  ... g_n    g_z
g_1   F_11 ... F_1n   F_1z
 :     :
 :     :
g_n   F_n1 ... F_nn   F_nz
g_z   F_z1 ... F_zn   F_zz

和前面不同的是對限制式 g 做偏微後不再變號，相當於把 F 定義為 f + λg，此時的λ與定義 F 為 f - λg 時的λ成反向關係，所以對 F 實質沒影響。另外，這又相當於先前的鑲邊 Hessian 矩陣前後各乘一個對角線是 ±1 的對角線矩陣，這對鑲邊 Hessian 矩陣的正負確定性質沒有影響。

矩陣 H* = [f*_ij] 是正確定代表對任意非全 0 的 a = [a_1,...,a_n]' 而言

Q*(a) = ΣΣ f*_ij a_i a_j

恆為正值；負確定則表示除 Q*(0) 外，Q*(a) 恆為負值。如果取 b = [b_0, b_1,..., b_n, b_z]' 用鑲邊 Hessian 矩陣 B 建立二次式：

Q(b) = b_0 (Σ_j g_j b_j +g_z b_z) + (Σ_i g_i b_i +g_z b_z) b_0
             + Σ_iΣ_j F_ij b_i b_j + F_zz b_z^2
             + b_z Σ_j F_zj b_j + Σ_i F_iz b_i b_z

如果 Σ_i g_i b_i +g_z b_z = 0，則經過演算可得 Q(b) = Q*(b*)（b* 是 b 去掉 b_0 與 b_z）。所以，用鑲邊 Hessian 矩陣 B 判斷臨界點是否為極大或極小，就是看 B 矩陣在前述限制下二次式是否恆負或恆正。當然，如果 B 本身是負確定，則在有限制下的二次式仍是負確定；B 是正確定則限制下的二次式也是正確定。注意 b_0 不影響前述對 b 的限制要求，而 b_z 完全可以配合 b* 的設定而滿足限制，所以限制條件下 Q(b) 的正負確定性完全滿足 H* 的正負確定性；反過來 H* 正或負確定也蘊含 Q(b) 在滿足條件時正或負確定，但 B 本身倒不一定是正或負確定。以前面 x, z 各是單變數,即原問題是兩變數一限制條件為例，B 的行列式值與 f*(x) 對自由變數 x 的第二階導數正負相反，意謂若 B 是正碓定，則 f* 的第二階導數為負；但依此處結論，B 正確定則 f* 的第二階導數是正的。結果相互矛盾，表示 B 矩陣不應是正確定或負確定。

注意這裡我們是把解變數 z 特意與自由變數區分出來，在 Lagrange 法，或說在限制式下求極值時，我們並不會特意將某個變數用其他變數的函數表示，所以 z 與 x 是一體的，相同地位的，所以如果問題是在 g(x) = 0 下求 f(x) 的極值，那麼 B 是

0     g_1  ... g_n 
g_1   F_11 ... F_1n
 :     :
 :     :
g_n   F_n1 ... F_nn

而 Q(b) = 2b_0 Σ_j g_j b_j + ΣΣ F_ij b_i b_j, 限制 Σ g_j b_j = 0 看 Q(b) 是負定或正定，分別是目標函數在限制式之下得相對極大或極小的充分條件。

現在假設我們有 k 個限制式，g 是個 k 元向量函數，因此我們假設有 k 個可解變數，n 個自由變數，問題形式是：

求 f(x,z) 的極值，限制條件 g(x,z) = 0 等價於 z = h(x)

其中 f 是 n+k 變量實數值函數，g 是 n+k 變量 k 元向量值函數。可解出 z = h(x) 是 n 變量 k 元向量值函數。則由 g(x,z) = 0 及 z = h(x) 的關係：

Dx g(x,z)' + (Dx h(x)') (Dz g(x,z)') = 0

式中 g(x,z)' 等視為行向量函數 g 轉置 (transpose) 為列向量，勿與微分符號混淆，特別是如果為了簡化把它表示成 g' 時（我們避免用 f', g' 代表微分，畢竟現在考慮的是多變量，且可能是向量值函數）。寫成這樣的結果 Dx g', Dx h' 是 n×k 矩陣，而 Dz g' = [ Dz_i g_j] 是 k×k 矩陣。假設 Dz g' 可逆，因此才可局部唯一解出 z = h(x), 故

Dx h(x)' = - (Dx g(x,z)') (Dz g(x,z)')^(-1)

所以

Dx f*(x) = Dx f(x,z) +  (Dx h(x)') (Dz f(x,z))
         = Dx f(x,z) - (Dx g(x,z)') (Dz g(x,z)')^(-1) (Dz f(x,z))

如果極值發生的地方可微分，則必須 Dx f*(x) = 0, 也就是

Dx f(x,z)' = (Dx g(x,z)')λ, 其中 λ = (Dz g(x,z)')^(-1) (Dz f(x,z))

故令 F(x,z,λ) = f(x,z)-g(x,z)'λ，而後對 x, z, λ 做偏微即可建立方程式解得臨界點，

就 RTF f*(x) 而言，其一階偏導向量簡記為

Dx f* = Dx f - (Dx g') (Dz g')^(-1) (Dz f)

而其 Hessian 矩陣是

H* = Dx(Dx f*)'
   = {Dx(Dx f)' - (Dx g')(Dz g')^(-1)(Dz (Dx f)')}
      - {Dx[(Dx g') (Dz g')^(-1) (Dz f)]'
            - (Dx g')(Dz g')^(-1) Dz[(Dx g') (Dz g')^(-1) (Dz f)]'}

因涉及矩陣，不好表達，我們且看Ｈ* 矩陣的個別元素 f*_ij。首先，f*(x) 對 x_i 的偏導數是：

f*_i  = f_i - (g'_i)(Dz g')^(-1)(Dz f)

以 Di 代表對 x_i 的偏微分，則

f*_ij = f_ij - g'_j(Dz g')^(-1)(Dz f_i)}
        - Dj[(g'_i)(Dz g')^(-1)(Dz f)]
        + g'_j(Dz g')^(-1) Dz[g'_i(Dz g')^(-1)(Dz f)]

式中

Dj[(g'_i)(Dz g')^(-1)(Dz f)]
   = (g'_ij)(Dz g')^(-1)(Dz f) + (g'_i)(Dz g')^(-1)(Dz f_j)
       - (g'_i)(Dz g')^(-1)(Dz g'_j)(Dz g')^(-1)(Dz f)

其中 (Dz f_j) 即 Dj(Dz f)，而 (Dz g'_j) 即 Dj(Dz g')，因先對諸 z 之一偏微再對 x_j 偏微，等同於先對 x_j 偏微再對諸 z 之一偏微。

在 g = 0 是多限制式，或 z 是向量時，Dz[g'_i(Dz g')^(-1)(Dz f)] 雖然微分的對像是純量函數，Dz 運算的結果是取行向量沒問題，但其組成是三個矩陣（和向量）相乘，因此同時考慮對向量 z 的偏微分在式子表達上有些麻煩，所以我們逐項表示對 z_t 的偏微分，假設以 D_t 代表對 z_t 的偏微，則 Dz[g'_i(Dz g')^(-1)(Dz f)] 的第 t 成分，類同對 x_j 的偏微，得

D*t(g'_i)(Dz g')^(-1)(Dz f)]
   = (g'_it)(Dz g')^(-1)(Dz f) + (g'_i)(Dz g')^(-1)(f_zt)
      - (g'_i)(Dz g')^(-1)(Dz g'_t)(Dz g')^(-1)(Dz f)

將以上  Dj[(g'_i)(Dz g')^(-1)(Dz f)] 和 Dz[g'_i(Dz g')^(-1)(Dz f)] 的結果代入 f*_ij，並利用 F = f - g'λ 其中 λ = (Dz g')^(-1)(Dz f)，以及 (Dx h') = - (Dx g')(Dz g')^(-1)，得

f*_ij = F_ij + (Dj h')(Dz F_i) + (Di h')(Dz F_j)  + (Di h')［(Dj h')(Dz F_t)］              

中括號［］內是純量，但整個［］連同內容（其中 t = 1~k）是 k×1 行向量。也可將 f*_ij 表示為

f*_ij = F_ij + (Dj h')(Dz F_i) + (Di h')(Dz F_j) + (Di h')(Dzz F)(Dj h)

式中 (Dzz F) = (Dz (Dz F)')，是 F 對諸 z 變量的第二階偏微分，k×k 矩陣。整體 H* = [f*_ij] 可以表示為

H* = (Dxx F) + (Dx h')(Dzx F) + (Dxz F)(Dx' h) + (Dx h')(Dzz F)(Dx' h)

此處 Dxz 表示先對 z 微分再對 x 微分，即 Dx(Dz)'，因此結果是 n×k  矩陣；又：Dx' = (Dx)'，即對向量變數的微分採列方向而非一般行方向，這等同於依慣例採行方向後再轉置。如果 H* 是負確定，就證明了 f 在該臨界點達到局部極大；如果是正確定，就是達到了局部極小。

Lagrange 函數對 λ, x, z 的所有二階偏導數組成鑲邊 Hessian 矩陣 B 等於

   0      Dx' g    Dz' g
 Dx g'   Dxx F    Dxz F
 Dz g'   Dzx F    Dzz F

由 B 及向量 y = [a'  b'  c']' 構造二次式 Q(y) = y'By，在  b'(Dx g') + c'(Dz g') = 0 的條件下，會等於用 H* 及 y* = b 構造的二次式：

   Q(y) = 2[b'(Dx g)+c'(Dz g)]a + b'(Dxx F)b + c'(Dzz F)c + 2b'(Dxz F)c
           = b'(Dxx F)b + c'(Dzz F)c + 2b'(Dxz F)c = Q*(y*)

這是因

b'(Dx h') = b'(- Dx g')(Dz g')^(-1) = c'(Dz g')(Dz g')^(-1) = c'

如果 B 是正（負）確定，或在 y 滿足上述限制下 Q(y) 正（負）確定，則 Q(y) = Q*(y*) 且恆正（負），藉此可以判斷在臨界點得到的 f 值是局部極小（極大）。不過由於 B 的左上角區塊是 0 方陣，B 最多只能是正半定 (positive semi-definite)或負半定 (negative semi-definite)，更可能是不定 (indefinite) 矩陣，所以判斷極大極小仍需在  b'(Dx g') + c'(Dz g') = 0 的條件下看 y'By 是否為正確定或負確定, 其中 y = [a'  b'  c']'，因此時二次式 y'By 相當於 f(x, z) 在 g(x, z) = 0 限制下「簡化」成 f*(x) 的 Hessian 矩陣。