前面的對偶筆記說明找到乘數後如何核驗證書;本節解釋這些乘數為甚麼存在。論證限於有限維線性模型。
動機
未找到可行點並不證明不可行;不斷改善界,也不證明某個界會真正等於原始值。擇一定理把第一個困難化為兩種互斥而窮盡的可能:可行決策,或分離乘數。強對偶則保證有限最優值有取得同值的乘數。
關鍵是有限線性系統的特殊性:有限個向量生成的錐是閉集。因此錐外一點有最近點,兩者位移產生分離線性泛函。我們逐步證明,不把分離當成一張無法核驗的幾何圖。
敏感度也是證書的結果。只改右端時,對偶乘數仍可行,給最小值函數處處適用的下界;原問題的最優乘數才在原右端給出支撐下界;只有相應原始基保持可行,下界才是精確線性公式。活動基改變時,可能同時存在多個支撐斜率,不能直接說成唯一導數。
定義
定義 5.1.1
(等式原始問題、對偶及生成錐)
採用最小化慣例:
等式乘數 不受符號限制。向量 的生成錐為 。擇一定理指定兩個系統恰有一個可行。
幾何證明使用歐氏內積,但可行性結論不依賴算法選哪個範數。零列及空系統也容許。錐含零、凸且對非負倍數封閉;這些代數性質並未證明其拓撲閉性,後者必須另行處理。
令 為可行且下確界有限時的最優值。若在擾動值有限之處都有 ,稱 在 支撐此值函數,也稱次梯度。支撐向量不必唯一,也未必是通常的導數。
定理/命題
定理 5.1.2
(Farkas 擇一定理)
對有限實矩陣 及向量 ,下列恰有一個成立:
第二個向量是第一個系統的不可行證書。
定理 5.1.3
(包括取得性的強對偶)
若 可行且下確界有限,則原始下確界與對偶上確界都取得,且兩值相等。對可行 ,目標相等當且僅當
因此原始可行、對偶可行及這些乘積,是可行對同時最優的充要條件。
有限維及有限個線性限制很重要。一般閉凸集上的有限下確界未必取得;任意非線性問題也未必有取得同值的對偶乘數。
證明思路
有限生成錐為閉集
引理 5.1.4
(有限生成錐是閉集)
對向量 ,生成錐 是 的閉子集。
證明
(先縮減到無關支撐,再用連續的逆)
任一錐內點都能用線性無關生成元表示。若某非負表示的正支撐相關,取非零關係 ,必要時反號使某個 。由係數減去 ,其中 是正 所對應的最小 。全部係數仍非負,至少一個正項消失;反覆做便剩無關支撐。
固定一組無關列矩陣 ,係數由像向量透過連續公式 唯一恢復。像收斂,非負係數也收斂到非負極限,所以這個子錐閉。無關子集只有有限個,其閉子錐聯集由支撐縮減覆蓋整個錐。有限閉集聯集仍閉,包括空支撐表示的零,故得證。
不能直接假設任意表示的係數都有界。例如生成元一與負一,可以用同時趨向無限的兩個相同係數表示零。像保持有界而係數發散,正是天真取極限的漏洞。先縮減到無關支撐,才有連續左逆可控制係數。有限種支撐還保證可以固定其中一種分析極限;無限個閉子集的聯集一般並不閉,所以「有限」並非可有可無的修飾。
最近點產生另一個系統
證明
(以最近點把 與錐分開)
取 為 的列錐。若 ,選最近點 。零已是候選,太遠的點不可能改善距離,因此可把搜尋限在足夠大的閉球;閉且有界的交集緊緻,最近點存在。令 。沿 至任意 的線段最小化平方距離,得
分別取 ,得 ,所以全部 。令 ,每列均有 ,而 。兩系統不可能同時成立,因可行點會使 ,矛盾。
分離向量還可除以負的 的絕對值,正規化成值負一,但仍須逐列檢查符號。若右端為零, 已可行,當然不可能有嚴格負證書。重複生成列也無礙,只需找到一個無關表示。錐本身一般無界;緊緻性只用於排除太遠候選後的最近點搜尋,沒有假設錐可行性是有界問題。
原始取得性與最優乘數
證明
(上圖錐給出取得性,Farkas 給出乘數)
存在非負 使 的對 ,恰為向量 及 的生成錐,所以閉。取可行目標趨向有限下確界 ,相應對趨向 ,仍在錐內。其表示給出 ,按下確界定義必相等,證明取得。
這裏閉的不是任意投影,而是已明確寫成有限生成錐的集合。一般閉集的線性像未必閉,不能略去生成元表示便套用同一句話。多出來的生成元最後座標為一,正好表示容許目標高於某個可行成本的非負餘量;沒有它,便只描述精確成本對,不是上圖集合。這個表示也容許成本係數為負,不曾假設目標本身非負。
取最優 ,令 為零座標集。我們要證明存在
若沒有,以 各列、其負列及 的座標向量作生成矩陣,右端取 ,套用 Farkas。其替代向量 滿足 於 ,且 。
足夠小的正 使 非負:零座標不能下降,正座標還有餘量;等式也因 保持。目標卻下降,矛盾。
更明確地,只需看那些正座標而方向為負的有限個位置;把步長取成小於其正比值的最小值,即能保留全部正座標。若沒有這類位置,任何足夠小正步長都可。零座標由替代系統的符號條件保護,等式由零方向保護,下降由成本內積的嚴格負號保護。這三項檢查分別對應可行性及改善,不能只用「朝較好方向」代替。故所需表示存在,給對偶可行 ,且
弱對偶即證對偶取得及同值。一般可行對的差距為 ,每項非負,等號恰好等價於逐項乘積零,完成證明。
證明透視
乘數存在性用在哪一步?
非負差距恆等式只證充分性,不會自己造出乘數。存在性來自把 Farkas 用在成本向量及活動零座標錐:若無乘數,分離向量就成為可行改善方向,違反最優性。原始最優值取得則是更早的上圖錐論證。分清這兩步,才不會假設欲證的證書而循環論證。
例題詳解
例題 5.1.5
(明確的不可行乘數)
方程 、 左端相同、右端不同。取 ,有 ,但 。任何非負可行點都會導出 。嚴格負純量是可核驗證書,不是未成功搜尋的紀錄。
例題 5.1.6
(完整求出敏感度函數)
最小化 ,限制 及全部非負。可行需 。當 ,取 ,對偶 ;其限制為 ,雙方值為 。
當 ,取 及 ,同樣可行且同值 。故
舊乘數超過二仍對偶可行,卻只給下界 ;使它精確的原始基已不可行。可行乘數不能無條件當成全局精確價格公式。
例題 5.1.7
(角點有多個支撐斜率)
時, 對每個 都可行且值二,給
負 時最小斜率一給最高下界;正 時最大斜率三給最高下界。左導數一、右導數三,通常導數不存在。對偶不唯一正確記錄這個角點,並非計算矛盾。
概念視角分析
值函數是有限個線性函數的最大值
若 有滿行秩,對偶多面體 不含直線,所以只有有限個頂點 ,而在其上有上界的線性目標必在某個頂點取得最大值。強對偶於是給出:凡 有限之處,。因此 是凸的分段線性函數。在上例中頂點為 與 ,得 ; 的拐角正是兩個頂點同時最優之處。
一般基的參數範圍
刪冗餘等式行後,最優基滿足 。只改右端,約化成本不變;原基在 的區域保持可行及最優,值恰為 。這些線性不等式給精確多面參數範圍。若基本值全正,連續性給一個開鄰域,局部值函數為仿射且梯度為乘數;若已有零基本值,某些方向可立即離開區域,可能出現角點或可行邊界。因此同一個基計算既解釋平滑的局部價格含義,也解釋這種含義的界限,毋須預先假設可微。成本擾動則會改約化成本,需要另一套檢查,不能直接沿用右端公式。
常見錯誤
常見錯誤
(把零值當作不可行證書)
不可行證書需要嚴格負值, 並未把 分離到錐外。這樣的向量或許另有用途,卻不能證明系統無解。例如 對任何系統都滿足 及 。
常見錯誤
(照搬另一種慣例的對偶符號)
對偶符號取決於本節最小化等式慣例,不能照抄前節最大化上界形式;兩者模型不同。先由可行不等式推弱對偶,才相信記憶中的符號。
閉性不能從最近點論證中刪去。目標值能否取得是另一回事;在這一點上,強對偶的多面體假設不能放寬為閉凸。
反例模式
有限下確界不被取得的閉凸集
一個看似合理的說法是:可行集閉凸且下確界有限的凸問題,會像線性規劃一樣取得下確界。在 上最小化 。 是凸函數 ()圖像上方的區域,所以凸。儘管描述中有嚴格不等號,它仍是閉集:若 收斂,則 有界,設上界為 ,於是 ;極限滿足 及 ,故屬於 。點 的目標值為 ,所以下確界為 ,但 中每點都有 。取得性證明用的是有限生成上圖錐的閉性;彎曲的集合沒有這種表示,這例子並不違反多面體情形的取得定理。
總結
有限生成錐閉,最近點給 Farkas,上圖錐給原始取得,再一次擇一產生最優乘數。敏感度由對偶可行性配原始基可行範圍推導。每步回答不同問題,不能把存在、核驗及局部變化率混成一句話。
練習
快速檢查
(對 給 Farkas 證書。)
解答 · 答案
取純量 ,有 而 。等式雖有自由實數解,卻無非負解。
快速檢查
(最小化 ,限制 ,求原始、對偶最優及互補乘積。)
解答 · 答案
值六。對偶最大化 ,限制 ,故 取得六。餘量 ,乘積為 。正餘量與零原始變量完全相容。
快速檢查
(求例中 ,比較保留乘數 所給兩個界。)
解答 · 答案
值分別 ,舊乘數界為 。第一個精確,第二個嚴格偏低,因原基候選鬆弛 已負。
快速檢查
(證明任一最優對偶在擾動值有限處支撐 。這足以證可微嗎?)
解答 · 答案
對偶可行集不依賴右端,故弱對偶給 ,原最優性給 ,相減即得。不能推出可微; 的支撐斜率區間及不同左右導數已是反例。