只觀察可行方向上的曲率
考慮
其中 , 滿行秩,且 。這些條件保證每個 都有可行解,卻沒有要求 正定。約束可能排除負曲率方向;反過來,只有違反約束的方向具有正曲率,並不能保證可行集上有最小值。
取任一可行點 ,令 的列構成 的一組基。每個可行點都能唯一寫成 。代入得到
定義 4.3.1
(零空間基與約化 Hessian)
若矩陣 的列構成 的一組基,便稱它為約束的零空間基。對稱矩陣 稱為約化 Hessian,而 稱為可行點 處的約化梯度。
的具體元素隨基而變,但正定性和半正定性不變: 恰好量度原目標沿可行方向的曲率。
定理 4.3.2
(完整分類)
問題 (1) 存在最小點,當且僅當 半正定且 。存在時,全部最小點為 ,其中 。最小點唯一,當且僅當 正定。其餘情況下,目標函數在可行集上無下界。
證明
(分別檢查彎曲方向和平坦方向)
由 (2),只須研究 上的 。若存在 使 ,則 時 。現在假設 。由對稱性,。若 不在該值域中,便有 使 ;適當選擇 的符號,就有 。
若 在值域中,取 使 。配方得
故 是最小點。對於半正定矩陣,二次型為零等價於向量屬於其核,所以其他最小點與 之差恰好屬於 ,亦即它們正是 的解。因此唯一性等價於核為零,也就是 。
證明透視
兩種失敗方式從何而來
代入式 (2) 是約束唯一出場之處;此後問題變成 的無約束二次問題, 的滿行秩只用來保證存在可行點 。證明接著分開兩種失敗方式。負曲率由一個 的方向揭示,線性項無法補救,因為二次項增長更快。平坦方向較微妙: 的對稱性用於 ,把代數條件 轉成幾何事實,即存在一個平坦方向,約化梯度沿它有非零分量。餘下情況的關鍵一步,是圍繞 的解配方,把與每個競爭點的差寫成 的二次型。唯一性一步再次用到半正定性:對不定矩陣,二次型為零並不迫使向量落在核中。
常見錯誤
(檢查完整 Hessian 而非約化 Hessian)
不定並不排除唯一的約束最小點,約束可能剔除所有負曲率方向:對 及約束 ,約化 Hessian 是 。決定分類的只有 ,即沿可行方向的曲率。 正定確實給出 ,但那只是充分條件,而不是判別準則。
乘子與完整算例
在可行點處,沿所有可行方向的一階導數為零,即 。因為 ,這恰好等價於存在乘子 ,滿足
滿行秩保證給定駐點的乘子唯一。該系統尋找駐點,不能自動保證最小。它能否唯一決定駐點,同樣取決於 。
命題 4.3.3
(KKT 矩陣的可逆性)
在問題 (1) 的假設下,(3) 的係數矩陣可逆,當且僅當約化 Hessian 可逆。
證明
(在零空間座標中解齊次系統)
考慮齊次系統 、。第二式給出 ;由於 ,把第一式左乘 得 。若 可逆,則 ,故 ;再由 單射及 得 。反之,若有非零 使 ,則 與 的每一列正交,故屬於 ,可寫成 。因 的列線性無關, 是非零齊次解。
例題 4.3.4
(約束改變無約束解)
最小化 ,滿足 。取 ,。此時 ,,故 ,,。於是 ,。該點梯度為 ,所以乘子 滿足 (3)。因為 ,它是唯一全局約束最小點,函數值為 。無約束最小點 不可行。
和 的數值與基綁定,最小點卻不然。
例題 4.3.5
(換一組零空間基)
改用 重做計算。則 ,,所以 ,而 ,是同一點。把基放大 倍使 乘以 、 乘以 ,但 的符號和解集都不變。
分類的邊界情形,是約化 Hessian 奇異卻仍有最小點。
例題 4.3.6
(奇異約化 Hessian 與一整條最小點)
最小化 ,滿足 。此時
取 ,並以 為 的列。則 奇異,而 。 的解為 ,所以最小點是所有實數 對應的 ,函數值都是 。在每一點 ,且 滿足 (3)。KKT 矩陣如命題所料是奇異的,但系統相容。
反例模式
KKT 矩陣可逆仍可能得到最大點
最小化 ,滿足 。此時 ,,,因而 可逆。KKT 系統唯一解為 ,但 。可逆只保證駐點唯一,不保證它是最小點;分類還需要 。
練習與解答
快速檢查
(最小化 ,滿足 。寫出全部最小點。)
解答 · 答案
每個 都是最小點。取 ,則 且 ,約化目標為常數。
快速檢查
(最小化 ,滿足 。最小點是否存在?)
解答 · 答案
不存在。,但 不屬於其值域 ;可行點 的函數值 。
快速檢查
(若 ,約束為 , 的約束最小點唯一嗎?)
解答 · 答案
唯一。約化 Hessian 是 ,因此 是唯一最小點,儘管 在整個空間不定。
滿行秩簡化了乘子的討論。冗餘方程可以描述同一個可行集,但乘子可能不唯一;使用 (3) 前,應先去掉冗餘,或另行說明適用結果。