搜索失敗也可以有證書
求解 、 看似要在無限多個候選向量中搜索。Farkas 擇一原理把不成功的搜索轉化成可檢查的見證:找出向量 ,使它與 每個列向量的內積均非負,卻與 的內積為負。這些列向量的非負組合不可能與 有負內積。這個分離原理也解釋最優性條件中乘子的來源,以及乘子證書實際證明了甚麼。
以下均在有限維歐氏空間中工作,、,向量不等式逐分量理解。容許空的約束集合;特別地,沒有生成向量的錐定義為 。內積和範數均採用歐氏形式。
有限生成錐的幾何性質
定義 2.2.1
(有限生成錐)
把 的列向量記作 。它們生成的錐為
是凸集,而且當 、 時 。閉性值得證明:閉集在連續映射下的像不一定是閉集。
引理 2.2.2
(有限生成錐是閉集)
由 中有限多個向量生成的錐 是閉集。
證明
(化為線性無關的生成向量,再用緊緻性)
每個 都能用線性無關的列向量表示。先取任一表示並刪除零係數。若餘下向量線性相關,取非零關係 ;必要時把 換成 ,使某個 。令 ,以 取代 。係數仍非負、至少一個變成零,而表示的向量不變。重複此步,直至餘下向量線性無關。
現在令 收斂至 。線性無關的列向量子集只有有限多個,故可取子序列,使它們都使用同一子集 。若 為空,這些向量均為零。否則映射 是單射,因而存在 使 :只需在緊緻單位球面上取 的最小值。因此對應係數向量有界。再取子序列使之收斂至非負向量 ,便得 。在歐氏空間,序列閉性即給出閉性。
擇一原理
定理 2.2.3
(Farkas 擇一原理)
以下兩個系統恰有一個有解:
- 且 ;
- 且 。
證明
(把 b 投影到錐上)
兩者不能同時成立,因為 。反之,若第一個系統無解,則 。取 在非空閉凸錐 上的最近點 。投影性質給出對每個 均有 。分別代入 和 ,得 。因此令 ,每個 都滿足 ,而
每個列向量均屬於 ,所以 。
證明透視
閉性與錐性質用在哪裏
容易的一半只用到 和 。困難的一半有三步。第一, 的閉性保證最近點 存在且屬於 ;由於 ,便有 及正的間距 ,有限生成正是在這裏用到。第二, 是錐,所以 和 都是可用的測試點;對一般凸集,投影不等式只給出仿射分離 ,錐性質則把它變成齊次的 ,並有 。第三,在生成向量本身測試,便把這個結論變成 。 的嚴格性則來自正交關係 與 。
例題 2.2.4
(用簡短證書取代搜索)
考慮 ,其中 。方程給出 、,所以此系統不可行。證書為 :它與兩個列向量的內積分別是 、,但 。檢查這三個內積無須依賴上面的解方程過程。
常見錯誤
(放寬證書中的嚴格不等式)
嚴格不等式不能放寬為 :即使第一個系統可行, 也會滿足第二個系統。此證書證明的是不可行,不是近似解。
不等式形式
同一擇一原理亦可就線性不等式系統表述。
推論 2.2.5
(不等式形式的 Farkas 擇一原理)
對 及 ,以下兩個系統恰有一個有解:
證明
(拆分自由變量並加入鬆弛變量)
寫 ,其中 ,再加入鬆弛變量 ,把擇一原理應用於 。所得見證 滿足 、 及 ,即 、,並有 。反過來,若兩個系統同時有解,以非負的 乘 便得到 ,矛盾。
這個形式清楚地展示如何把不等式相加以得到矛盾。
例題 2.2.6
(把兩條不等式相加得到矛盾)
單變量系統 、 有 、。向量 非負,,且 ,所以系統不可行。具體而言,把兩條不等式相加便得 。生成集為空的邊界情況亦一樣:若 ,則 ;對 ,向量 就是證書,因為條件 自動成立,而 。
從線性化下降方向到乘子
在光滑約束問題的可行點,把活躍不等式的梯度排列為矩陣 的行,把等式梯度排列為矩陣 的行,並記 。線性化方向滿足 和 。有沒有這樣的方向令目標嚴格下降,即 ?由於正數倍不改變齊次條件,這等價於以下系統可行:
定理 2.2.7
(不存在線性化下降方向的證書)
以下兩者恰有一個成立:(i) 存在 使 、 及 ;(ii) 存在 和不受正負號限制的 ,使
證明
(對正規化系統應用不等式形式的擇一原理)
把 寫成 和 。若上述正規化下降系統不可行,不等式形式的擇一原理給出 ,使
因此 ;除以 並令 。反過來,若上述乘子方程和嚴格下降方向同時存在,與 取內積便得到
與嚴格下降矛盾。等式乘子不受正負號限制:它是兩個非負乘子之差。
對約束為 、 的最優化問題,給不活躍的不等式賦零乘子,上述證書便是 KKT 條件中的駐點、乘子符號和互補鬆弛部分。它來自不存在線性化下降方向,而非僅僅來自可行性。在局部最小點,要另用如 MFCQ 的約束資格條件證明這類方向不存在:它把線性化方向與實際可行曲線連繫起來。
常見錯誤
(把 KKT 證書當作最小點證書)
對一般非凸問題,KKT 證書本身不能證明最小;還要檢查凸性或其他充分條件。上述定理只排除了該點的嚴格線性化下降方向。
例題 2.2.8
(從方向檢驗求乘子)
在 、 下最小化 。在 ,活躍梯度為 、,而 。線性化約束給出 和 ,所以 ,不可能嚴格線性化下降。駐點方程 給出 、。此例中,可行性本身給出 ,另外證明了全局最優。
實際方向和線性化方向的區別很重要;沒有約束資格條件時,即使在真正的最小點,乘子結論亦可能失效。
反例模式
沒有乘子的全局最小點
聲稱:光滑問題的每個局部最小點都有滿足駐點條件的乘子。考慮在 下最小化 。唯一可行點是 ,因而它是全局最小點。但該處活躍約束梯度為 ,故每個 都是線性化可行方向,而 給出 :存在嚴格線性化下降方向,沒有乘子能滿足 。修正後的敍述須加上約束資格條件。此處 MFCQ 不成立,因為沒有 滿足 ;在 MFCQ 下,局部最優排除線性化下降方向,上述定理便提供乘子。
練習與解答
快速檢查
(令 、。找出 、 的不可行證書。)
一個數 便足夠。
解答 · 答案
取 ,則 且 。
快速檢查
(令 、、。求乘子證書,並解釋為何沒有嚴格線性化下降方向。)
先解駐點方程,再與方向條件對照。
解答 · 答案
駐點方程 給出 、。也可直接看出 給出 , 給出 ,所以 。
快速檢查
(在反例 中, 能否是通過 的可行曲線的導數?為甚麼?)
先描述可行集。
解答 · 答案
不能。可行集只有 ,所以每條可行曲線恆為零,其導數也是零。沒有適當正則性時,線性化方向不一定是實際可行速度。