本節講解線性規劃的一項基礎建模技巧:絕對偏差與極小極大目標的精確線性表述。
動機
求解器只能優化交給它的模型。在選擇主元規則之前,先要弄清每個變量的意思,以及不等式是否真的表達決策者的要求。假設我們要用一個設定值近似多個測量值:最小化最大誤差會保護最差的一個觀測值;最小化誤差總和則衡量另一種取捨。由於誤差涉及絕對值與最大值,兩個目標看似都不是線性的。只要不等式方向正確,引入輔助變量便可把它們化為線性規劃(LP)。
建模的關鍵是等價。同一個原決策可能對應多個可行的輔助變量值,因此不能要求兩個可行集逐點相等。我們應檢查:每個原決策能否擴展為新模型的可行解?對固定原決策優化輔助變量後,是否得到原本的目標值?
定義
定義 20.1.1
(殘差與上圖集)
設 是非空多面體;模型也可包含仿射等式和變量界。對有限個()仿射殘差 及權重 ,考慮加權絕對偏差問題
函數 在 上的上圖集是滿足 、 的點對 的集合。對有限多個仿射函數 ,條件 等價於對每個 都有 。
此處目標以下界零為界;由線性規劃的最優值存在定理,非空可行 LP 會取到有限最優值。保留下確界符號是為了清楚比較兩個問題的值。除非另有界限, 的分量可以為負。在轉換後的 LP 中,對每個殘差引入 ,要求 及 。這兩個不等式已經推出 ;額外寫出非負約束雖無妨,卻是多餘的。
定理/命題
定理 20.1.2
(精確表述與原解的還原)
當所有權重 時,原偏差問題與以下 LP 有相同的下確界:
只要其中一個問題取到下確界,另一個也會取到。任何 LP 最優解的 部分都是原問題的最優解。若 ,每個 LP 最優解均滿足 ;若 ,此等式未必成立,但可以選擇使它成立。
同樣,要最小化 ,可在 及所有 的限制下最小化 。即使 沒有界或是自由變量,這仍是有限條約束的 LP;可行集本身不必有界。
證明思路
固定任意 。關於 的兩個不等式恰好等價於 。因此取 不但可行,而且對固定的 使 最小。由於權重非負,任何擴展解的目標值都不小於原偏差目標,而上述選擇恰好達到它。再對 取下確界,兩個最優值相同。
若原問題有最優解,把它用絕對值擴展便得 LP 最優解。反過來,將 LP 最優解與每個原決策的這種擴展比較,可知其 部分必定原本已最優。若某權重嚴格為正,最優解中該 一旦有多餘值,就可減至其下界並嚴格改善目標,造成矛盾;權重為零時則沒有這個嚴格改善。
最壞情況模型亦然: 大於等於全部 個帶符號殘差,等價於它大於等於這些數的最大值,也就是 。固定 作同樣比較,便得到最優值與解的等價;證明不需要可微性或唯一解。
證明透視
為何不等式在最優時可以取等號?
對一般可行點,這些不等式只給 的下界。最小化含正係數的 才是最優時下界取等號的另一個理由。證明是在固定 後比較可行擴展,並不是說每個可行輔助變量都等於絕對值。套用前必須檢查係數符號和這變量有否受其他約束。
例題
例題 20.1.3
(用一個設定值配合三個目標)
對目標 ,選擇實數設定 ,最小化絕對誤差總和。LP 是
消去輔助變量後,在 、、、 四段上,目標值分別為 、、、。各分段在端點相接。最小值在 取得,等於 ;對應 。這個設定是中位數,不是平均數 。
若改為最小化最大誤差,令 且 ,並最小化 。單看兩端目標已得 。取 時,三個誤差都不超過 ,所以達到此下界。故最小最大誤差為 ,設定值為 。中間目標影響誤差總和,卻沒有改變此例的最壞情況解。
例題 20.1.4
(共享資源與最優性證書)
設 、,兩項目標均為 。若超出目標也算偏差,最小化最大偏差的模型為
把兩條 相加,得 ,所以 。可行選擇 達到這下界,因而是全局最優;我們毋須預先猜測哪條約束在未知最優解處取等號。若只懲罰不足而不懲罰超額,應使用不足量 ;那是另一個模型,需包括 及不足量不等式。
常見錯誤與細節
反例模式
負權重會顛倒誘因
考慮固定 時最小化 ,其值為零。若以 、 取代絕對值,卻得到在 下最小化 ,目標無下界。這些不等式確實描述上圖集,但最小化負倍數會獎勵人為增大的 。同理,在這些下界下最大化 也不能表示最大化 ;其他情況可能需要非凸等式或離散模型。
固定 時, 恰好等價於 。相反,若 , 是「 或 」的析取;同時要求兩者是不可能的。若只寫 及 ,又完全不能限制 ,因為總可把 選得夠大。上圖集表述必須連同其使用方式一起檢查。
快速檢查
若零權重殘差的值是 ,最優 LP 解的輔助變量可以是 嗎?可以,只要其他約束與目標項都得到滿足:它的上圖集約束只要求 。在本模型中,把它改為 不會改變目標值。
練習
快速檢查
(在實數上最小化 ,寫出 LP 並求最優解及最小值。)
解答 · 答案
令 、、、,最小化 。原目標在 、、 分別為 、、。它在 之前遞減,其後遞增;故唯一最優解為 ,最小值為 。
快速檢查
(在 下最小化 。以一個下界和一個可行點證明答案。)
解答 · 答案
因 ,第二個誤差為 。取 時兩個誤差是 和 ,故最小值為 。下界與可行點共同證明最優性,無須依賴圖形。
快速檢查
(有人為 建立模型:最小化 ,但只加 。求其值並說明如何修正。)
解答 · 答案
所建 LP 在最優時取 ,在 得值 ;真正的最小值卻是 時的 。加上 ;兩個符號都不可缺。修正後,在給定區間內最小可行 是 。