為甚麼需要資格條件
在受約束最小點,目標函數的負梯度可能由約束梯度平衡。但即使可行集很簡單,描述它的約束梯度也可能毫無作用: 描述單點集 ,其梯度在零點卻是零。在此集合上最小化 ,零點是最小點,但沒有任何乘子可使駐點方程 成立。因此,斷言乘子存在前,我們需要的是對約束表示方式的條件,而不僅是對可行集的條件。
設 和 在可行點 附近連續可微;不等式寫作 ,等式寫作 。令 ,。非活躍不等式已經嚴格成立,在附近仍然嚴格成立。
定義 4.2.1
(Mangasarian–Fromovitz 約束資格條件)
若下列兩項成立,稱 處滿足 Mangasarian–Fromovitz 約束資格條件(MFCQ):
- 的行向量線性無關;及
- 存在向量 ,使 ,並對所有 有 。
若 為空,第二項自動成立,取 便可;若沒有等式,第一項自動成立。MFCQ 要求有一個方向,一階上不違反等式,並走向所有活躍不等式的嚴格一側。它比要求所有等式及活躍不等式梯度線性無關(LICQ)為弱。
命題 4.2.2
(LICQ 推出 MFCQ)
若梯度 及 ()線性無關,則 處成立 MFCQ。
證明
(指定方向導數)
的各行都在這組線性無關的梯度之中,所以線性無關。把所列梯度依次排成矩陣 的各行。各行線性無關表示 滿行秩,故對任何右端 , 都有解。取 在等式行為零、在每個活躍不等式行為 。所得解滿足 ,且對 有 。
反過來不一定,以下重複約束的例子便會說明。
由線性化方向得到乘子
定義線性化錐
定理 4.2.3
(MFCQ 與 KKT 條件)
若 是局部最小點且滿足 MFCQ,則存在 和 ,使
此外,這些乘子對的集合有界而且閉,因此是緊緻集;它不一定只有一個元素。
證明
(推入嚴格一側,再正規化)
任取 及一個 MFCQ 方向 。對每個 , 滿足 ,並嚴格減少每個活躍不等式的一階變化。由於 滿行秩,隱函數定理給出滿足等式的曲線 ,其中 為充分小的正數。對每個活躍約束,;非活躍約束仍然嚴格成立。局部最小性給出 。令 ,得到對所有 均有 。
有限維 Farkas 擇一定理於是給出 ,其中 。把非活躍乘子設為零,便得到駐點條件及互補條件。
要證有界性,反設有一列乘子對的範數趨於無窮。用各自範數除以駐點方程,並取正規化乘子對的收斂子列。其極限 的範數為一,活躍乘子非負,而且
與 取內積:等式項消失,而每個 都嚴格為負,所以所有 均為零。 滿行秩再推出 ,與範數為一矛盾。乘子集合由閉等式和不等式定義,因此是閉集。
證明透視
一個方向做兩件事
MFCQ 方向 用了兩次,目的不同。在存在性部分,它把任意線性化方向 傾斜成 ,使之嚴格指向每個活躍不等式的內側;只有這樣,隱函數曲線才保持可行,而 滿行秩正是令該定理適用於等式的條件。不等式 是閉條件,所以可令 。在有界性部分,關鍵一步是正規化:除以發散的範數會消去 ,只剩非零異常乘子的齊次方程。把該方程與 配對,便證明這樣的乘子不存在,因為餘下的每個係數都有嚴格符號。滿行秩第二次用於消去 。沒有 MFCQ,齊次方程可以有非零解;下面的反例顯示乘子集合此時會變得無界。
關鍵是排除了上述齊次方程的非零異常乘子。此有界性針對固定點及固定表示方式;它本身不保證數值算法收斂,也不保證鄰近問題的乘子連續變化。
概念視角代數
把 MFCQ 看作不存在異常乘子
MFCQ 有一個等價的對偶形式:它成立當且僅當
的唯一解是 、。有界性證明用了其中一個方向:與 作內積迫使 ,滿行秩再迫使 。反方向來自一個 Farkas 型的擇一定理。原始形式靠給出 來確認;對偶形式則只要給出一個異常乘子就被否定,正如下面的反例。
例:重複約束
例題 4.2.4
(一整段乘子)
在 、 下最小化 。唯一最小點是 。兩個活躍梯度 和 線性相關,故 LICQ 失敗;取 ,兩個內積分別是 和 ,所以 MFCQ 成立。駐點條件要求
所有 ()都是乘子對。集合有界但乘子不唯一:相同的支撐作用可以分配給冗餘的描述。
常見錯誤
(把乘子當作可行集的性質)
約束重新縮放會改變乘子的數值,儘管可行集不變:在上例中,把 換成 ,係數 便變成 。乘子屬於約束的某種表示方式,只有在 LICQ 之類的資格條件下才唯一。
約束梯度線性無關時,乘子便被確定。
例題 4.2.5
(一個等式與一個活躍不等式)
在 及 下最小化 。可行點為 ,,而 ,所以 是最小點。此時 ,。取 ,則 且 ,故 MFCQ 成立。駐點條件為
即 及 。因此 、。兩個梯度線性無關,所以 LICQ 亦成立,乘子對唯一。
定義的邊界情形,是沒有任何活躍約束的點。
例題 4.2.6
(沒有活躍不等式)
在 下最小化 。最小點 滿足 ,所以 為空,亦沒有等式;取 便滿足 MFCQ。互補條件迫使 ,駐點條件 於是化為無約束條件。乘子集合是單點 ,如定理所言是緊緻集。
資格條件失敗時
在單點問題「最小化 ,滿足 」中,活躍梯度為零,沒有方向能令其一階嚴格減少。MFCQ 失敗,而且如上所見不存在 KKT 乘子。
反例模式
沒有 MFCQ 時乘子集合可以無界
保留約束 ,但把目標改為 。最小點仍是 ,該處 MFCQ 仍然失敗。駐點條件為 ,在 對每個 都成立。所以 KKT 乘子存在,但乘子集合是整條射線 ,並非有界。事實上 解出齊次方程 :它是異常乘子,正是 MFCQ 所排除的。定理的有界性結論需要資格條件。
這個例子亦顯示,MFCQ 失敗不代表 KKT 必定失敗。資格條件保證有用結論;個別問題即使沒有它,仍可能存在證書。
練習與解答
快速檢查
(在 、 下最小化 。驗證原點的 MFCQ,並以 慣例求乘子。)
解答 · 答案
寫成 、,方向 與兩個梯度的內積均為 ,故 MFCQ 成立。駐點方程 給出 。所有可行點均有 ,因此原點確是全局最小點。
快速檢查
(在 及 下最小化 。在 驗證 MFCQ 並求乘子;LICQ 是否成立?)
解答 · 答案
,活躍不等式梯度是 。取 ,則 且 。駐點方程 給出 、。兩個梯度線性無關,LICQ 亦成立。等式將可行集化為 ,所以 是全局最小點。
快速檢查
(某可行點沒有等式約束,活躍不等式梯度是 、。MFCQ 能否成立?不需假設目標函數。)
解答 · 答案
不能。嚴格下降同時要求 及 ,互相矛盾。這是該點約束表示方式的性質,與目標函數無關;它不排除某個特定目標仍有 KKT 乘子。