動機
線性規劃的一個可行解給出最優值的一個界,其對偶規劃的一個可行解則給出另一個方向的界。近似算法常利用由此得到的證書,把離散解與線性規劃鬆弛作比較。但為甚麼這兩個最好的界會重合呢?回答這個問題需要假設條件:不可行的規劃沒有原問題最優解,無界的規劃則沒有可與之匹配的有限最優值。
我們將針對一種具體而常用的標準形式證明強對偶性。證明的做法是從不等式中逐個消去變量,同時記錄每個新不等式是由哪個非負組合產生的。目標函數最終得到的一個上界就成為對偶解。這樣既建立了存在性,也建立了等式;它並不只是觀察到兩種算法恰好給出相同的數值。
定義與弱對偶
定義 4.2.1
(原問題與對偶問題)
設 ,,。原問題與對偶問題分別為
不等式均按座標分量理解。可行點是滿足所列全部約束的點。若存在可行點實際取得某個有限最優值,則稱該有限最優值被取到。變量集或約束集為空的情形,可按通常的空和約定來解釋;當原問題可行且有界時,主要證明在這些情形下同樣成立。
定理 4.2.2
(弱對偶性)
若 是原問題的可行點、 是對偶問題的可行點,則 。
證明
(以兩個受符號控制的不等式連鎖)
對任意可行的 ,有
第一個不等號用到 與 ;最後一個不等號用到 與 。這就是弱對偶性:每個對偶可行點都是每個原問題可行目標值的上界。
定理
定理 4.2.3
(帶有可達性的強對偶定理)
若原問題可行且其目標函數有上界,則兩個規劃都取得有限最優值,且最優值相等。
定理 4.2.4
(一個實變量的精確消去)
對於關於 的有限個非嚴格線性不等式組,可以構造出關於 的有限個非嚴格不等式,使得它們成立當且僅當存在實數 滿足原不等式組。所構造的每個不等式都是原不等式的非負線性組合。
證明
消去引理的證明
證明
(配對下界與上界)
將每個含 的不等式改寫成上界 或下界 :兩邊除以 係數的正絕對值,必要時反轉不等號方向。 的係數為零的不等式原樣保留。對每一對下界與上界,加入不等式 。它由兩個原不等式的正數倍相加得到,因此是非負組合。若沒有下界或沒有上界,則不加入任何配對不等式。
原不等式組的每個解都滿足所構造的不等式組。反之,若所構造的不等式組成立,則所有下界都不超過所有上界。當兩類界都非空時,在它們的有限最大值與有限最小值之間取 。若只出現下界,則取 不小於這些下界的最大值;若只出現上界,則取 不大於這些上界的最小值。若兩者都不出現,則取任意實數 。保持不變的那些不等式同樣成立。於是存在相容的 ,精確性得證。
重複消去會保持證書性質:由本身已是原不等式組非負組合的那些不等式再作非負組合,仍然是原不等式組的非負組合。不等式的個數可能迅速增長,所以這個證明是存在性論證,並不表示它是高效的線性規劃算法。
強對偶性的證明
證明
(投影目標並讀出對偶解)
引入實的目標變量 ,考慮不等式組
利用引理消去 的全部座標,得到只含單一變量 的有限個不等式。精確投影說明:實數 滿足這個不等式組,當且僅當存在某個原問題可行點使得 。
投影集非空,因為原問題可行。它有上界,因為原問題的目標函數有上界。因此至少有一個投影後的不等式中 的係數為正:否則所有不等式都只是下界或常數,那麼這個非空集合將向上無限延伸。把每個 係數為正的不等式規範化為 ,並令 為這有限多個上界中最小的一個。每個可行的 都不超過 。
投影集也是閉集,因為它由有限個非嚴格不等式描述。它含有某個值 ,並包含 以下的每個數:同一個原問題見證點對更小的 同樣適用。它的正係數不等式以 為上界,而它的下界型不等式在 處成立,因為 。因此 本身滿足整個投影不等式組。由精確性得到原問題可行點 使 ;上界迫使等號成立。於是原問題的最優值在 處被取到。
取一個達到最小值的導出不等式 。它是原不等式的非負組合。設它對 、、 的乘子分別為 、、。該組合中 的係數恰為 ,因為只有最後一個原不等式含 。由於所選不等式已規範化為係數為一,故 。其 的係數全部消去,給出
於是 ,所以 是對偶可行解,其目標值為 。由弱對偶性,任何對偶可行點的值都不可能更小,證明完成。
證明透視
最後的不等式記得自己的來源
的乘子在規範化後必須為一。其餘乘子非負,並且抵消 的係數。這種抵消恰好就是對偶約束;其右端恰好就是原問題的最優值。
例題詳解
例題 4.2.5
(一個變量與一個被取到的證書)
在 與 的條件下最大化 。原問題的最優值為 ,在 處取得。對偶問題在 與 的條件下最小化 ,所以 的值同樣是 。將 乘以三,再加上 ,得到 。
例題 4.2.6
(一個冗餘的界)
在 、、 的條件下最大化 。對偶問題在 與 的條件下最小化 。取 即證明原問題的最優值為二。較鬆的約束可以取乘子為零;對偶性並不要求每個約束都發揮作用。
例題 4.2.7
(最優值為負的可行規劃)
在 與 的條件下最大化 。其可行域為 ,最優值為 。對偶問題在 、 的條件下最小化 ,所以 ,而 取得 。係數為負與最優值為負都是容許的。
例題 4.2.8
(零目標函數)
對任意非空可行域及 ,每個可行的 的目標值都為零。對偶點 可行且目標值為零,即使原問題的可行域無界也是如此。目標函數有界與可行域有界是不同的。
常見錯誤
反例模式
丟掉假設條件
僅在 的條件下最大化 。目標函數無上界。其對偶將要求不可能成立的不等式 ,所以不存在有限的對偶最優值。強對偶性並不是說每一對語法上合法的規劃都有兩個有限最優值。
常見錯誤
(兩個界還不是最優值)
僅憑弱對偶性不能證明等式。例如,原問題可行點的值為二、對偶可行點的值為十,給出的是一個正確的區間,但不是最優性證書。若兩個值相等,則弱對偶性立刻證明兩者都是最優的。強對偶性保證在所述假設下存在一對相等的解;如何高效地找到它則是另一個算法問題。
常見錯誤
(不檢驗就照搬符號)
弱對偶性的乘法推導中,符號約束至關重要。若 的某個座標可以為負,用它去乘一個按座標成立的不等式就可能使不等號反向。含無約束變量的規劃,可以把每個自由變量寫成兩個非負變量之差而化為標準形式,但所得對偶的符號必須從這一轉換中推導,而不能不加檢驗地照搬。
投影證明提供了甚麼、沒有提供甚麼
消去法的證明表明,即使可行多面體本身延伸到無窮遠,有限的上界仍然被取到。這來自投影後的目標集的有限閉描述,而不是來自原可行域的緊緻性。一個變量的負最優值例子與零目標函數例子說明了這兩種可能。
導出的乘子是在所給實數據之上的精確證書。對有理數輸入,消去只用到有理數的加、乘、除,因此原則上得到有理數見證。中間不等式的個數與位元長度可能迅速增長。這裏的論證並不說明某個具體線性規劃求解器的多項式運行時間,也不說明浮點輸出的數值可靠性。計算得到的證書應當在適當的精確或經認證的算術模型下,對照原不等式加以檢驗。
常見錯誤
(線性規劃對偶不能消除整數性間隙)
對於整數優化,即使線性規劃的最優值是精確的,也可能嚴格大於整數解上的最優值。強對偶性使兩個連續的線性規劃值相等;它不會消除整數性間隙。近似性證明仍然可以把線性規劃最優值當作界來用,前提是其捨入或原始—對偶分析單獨考慮了這個間隙。
跟隨一個消去步驟
考慮 、 與 。寫成關於 的界,即 、 與 。將唯一的上界與兩個下界配對,得到 與 。將後者規範化後,投影得到的限制為 。這個證書中目標不等式的係數,要在 乘以三之後才變為一。在由此得到的原不等式組合中, 的乘子是三,恰好就是對偶最優解 ,其目標值 與原問題最優值相等。
多個上界可以產生若干個投影不等式。其中最小的右端控制最大目標值,其餘的仍然有效但是較弱的界。若兩個界相等,則任何一個都可以提供對偶證書;這就是為甚麼一個最優值可能對應不止一個對偶解的原因之一。冗餘的中間不等式可以保留而不改變投影,儘管它們會使消去過程大得多。
對於任意一對目標值相等的可行點,該證書也解釋了互補鬆弛性。在弱對偶的鏈式不等式中,間隙分解為
兩項都是非負乘積之和。若目標值相等,則兩個和中的每個乘積都為零:正的對偶乘子迫使其對應的原問題不等式取等,正的原問題變量迫使對應的對偶不等式取等。反之,可行點滿足這些乘積為零的條件時,目標值相等,從而證明最優性。這些條件並不要求每個取等的約束都有正的乘子。
概念視角幾何
目標是活動約束法向量的組合
由於 ,有 ,其中 是 的第 行。依互補鬆弛性,只有在最優解 處取等號的約束才帶正權重。所以 落在活動約束的外法向量所生成的錐內:在 處沒有任何可行方向能使目標增大。
作為具體檢驗,在冗餘界的例子中,第一個乘子為一,其界 取等;第二個乘子為零,其界 有三的鬆弛量。原問題變量為正,且對偶不等式 取等。這些是間隙為零的推論,而不是強對偶性所需的額外假設。
總結
從有限個非嚴格不等式中消去變量,既保持精確的可行性,又記錄非負組合。將原問題目標投影到一維,得到一個被取到的有限上界。產生該上界的乘子構成一個值相同的對偶可行解。弱對偶性隨即證明兩個解都是最優的。
練習
快速檢查
(在 與 的條件下最大化 。給出原問題與對偶問題的最優解及其共同的值。)
先寫出對偶問題。
解答 · 答案
原問題點 的值為六。對偶問題在 與 的條件下最小化 ; 的值為六。弱對偶性證明兩者都是最優的。
快速檢查
(從 與 中消去 。對哪些 存在相容的 ?)
比較兩個界。
解答 · 答案
這一對不等式相容,當且僅當 ,即 。對這樣的 ,取 即同時滿足兩個不等式。
快速檢查
(某個原問題可行點的值為七,某個對偶可行點的值也為七。說明為甚麼兩者都不能再改進。)
對兩個方向都使用弱對偶性。
解答 · 答案
弱對偶性使每個原問題的值以七為上界,每個對偶問題的值以七為下界。所給的兩個可行點恰好取到這兩個界。
快速檢查
(在 與 的條件下最大化 。該定理適用嗎?請說明理由。)
先檢查定理的假設。
解答 · 答案
這些約束互相矛盾,所以原問題不可行。這裏所述的強對偶定理假設原問題可行,因此不適用。