約束可能阻止目標函數下降的方向,因此單看目標函數的駐點並不足夠。拉格朗日(Lagrange)乘子描述這個阻礙;對偶性則用合適的乘子為所有可行值提供下界。當某個可行值等於下界時,最優性便獲證明。
拉格朗日函數與弱對偶
在 、()及 ()下最小化 。
定義 2.1.1
(拉格朗日函數、對偶函數與對偶問題)
拉格朗日函數為
對偶函數是 ,它可以等於 。對偶問題在 、 不受符號限制下最大化 ,其最優值記作 ;原問題的下確界記作 。
定理 2.1.2
(弱對偶)
對任意原問題可行點 、 及任意 ,均有 。因此 ;有定義時可使用擴展實數值。
證明
(可行性令每個附加項非正)
對可行 ,等式項為零,且因 、 而有 ,所以 。對可行 取下確界,再對對偶可行乘子取上確界,便得 。
若某可行 和對偶可行 的值相等,兩者均最優;此證明不需要凸性。此結果比較上下界,並不斷言兩邊都取得最優值。強對偶表示最優值相等,不表示任意試算值相等。對偶迭代點即使可行,也可能只給出很弱的下界;反過來,不可行點即使目標值很好,也不是原問題的上界。若同時有原可行值和對偶值,兩者之差稱為非負的對偶間隙。當有限最優值位於兩者之間,小間隙便限制了各值與最優值的距離。
符號約定不可忽略。若改成最大化,或把不等式寫為 ,乘子符號也須一致改變。乘子並非任意的罰項:在本約定中若選負乘子,上面的下界推理便可能失效。
KKT 條件
定義 2.1.3
(Karush–Kuhn–Tucker 條件)
在開定義域中,對可微函數,點 及乘子 的 KKT 條件為:
- 原可行性: ,。
- 對偶可行性: 。
- 互補鬆弛: 每個 滿足 。
- 駐點條件: 。
嚴格不活躍的不等式必有零乘子;活躍約束的乘子卻也可以是零。互補鬆弛並不表示每個活躍約束都有正乘子。KKT 不自動是所有受約束最優點的必要條件,還需要約束資格條件。
定理 2.1.4
(凸問題的 KKT 充分性)
在開凸定義域上,若 和所有 可微且凸,所有 仿射,則任何滿足駐點、乘子非負、互補鬆弛的可行點及乘子,均為原問題和對偶問題的最優解。
證明
(一個不等式、一次最小化、一個等式)
由於 、各 凸、各 仿射, 在開定義域上凸且可微。駐點條件表示它在 的梯度為零,故由凸性的一階刻劃, 最小化該函數,並有 。互補鬆弛與可行性給出 。因此每個可行 都滿足
所以 是原問題最優點。對任何對偶可行 ,弱對偶給出 ,所以這組乘子是對偶最優。
證明透視
鏈中每一環用了甚麼
上式的不等式鏈令證書一目了然。第一個不等式只用 的可行性和符號 ,即單點的弱對偶。中間的不等式用到凸性與可微性:它們把駐點方程提升為拉格朗日函數的全局最小性;對非凸問題,駐點可能是極大點或鞍點。最後的等式用互補鬆弛及 ;若缺少它,鏈只給出較弱的 。整個證明沒有出現約束資格條件:資格條件關乎乘子是否存在,而這個證明一開始便已手持乘子。
此定理不要求 Slater 條件。Slater 是保證最小點存在乘子的一種途徑;一旦找到 KKT 證書,充分性證明只需上述凸性和可微假設。分清兩個方向,便不會誤以為嚴格可行性失敗便使一個已驗證的證書無效。
反方向則需要假設;以下是 Slater 條件的一個具體充分形式。
定理 2.1.5
(Slater 條件給出 KKT 乘子)
設 為開凸集, 與每個 在 上可微且凸,各 為仿射函數。假設 內有一點滿足所有等式並嚴格滿足每個不等式,而原問題的最小值有限且在 內取得。則強對偶成立,最優乘子存在,且每個原問題最小點均有 KKT 乘子。
其分離證明見分離、次梯度與強對偶單元。必須檢查嚴格可行性,不能只因最優點存在便推斷它成立。更精細的版本可放寬仿射不等式的嚴格性並使用相對內部;本節採用剛才較強的條件。
例子:對偶證書
例題 2.1.6
(KKT 點及其對偶函數)
最小化 ,約束為 。拉格朗日函數為 。駐點條件給出 、;若約束活躍,,所以 ,。該點可行,乘子非負,互補鬆弛成立;凸性令 KKT 足以證明最優。
同一結論亦可直接從對偶讀出。代入 的最小點得
最大值 等於原問題值。 嚴格可行,所以 Slater 條件亦成立。
當最優值函數可微時,乘子與右端微小放寬的價值變化率有關,按此符號約定差一個負號;沒有可微等額外條件時不可直接斷言它就是導數。
資格條件為何重要
即使是凸問題,也不能直接刪去 Slater 假設。
反例模式
最小點沒有乘子的凸問題
聲稱:可微凸問題的每個最小點都有 KKT 乘子。在 下最小化 ;兩個函數都凸。唯一可行點為零,故它最優;然而駐點條件在零要求 ,即 ,任何乘子均不可能滿足。此處沒有嚴格可行點,而且約束梯度在最優點消失。修正後的敍述正是上面的 Slater 定理,而其嚴格可行假設在此不成立。這不是 KKT 充分性的反例,而是必要性需要假設的例子。
等式約束及乘子
等式與不等式不同:等式乘子不受符號限制。原因可從弱對偶證明看出:在可行點 ,故不論 的符號, 均為零。代數上可用兩個反向不等式代替等式,但這可能引入多餘乘子,使解釋不那麼直接。
例題 2.1.7
(等式約束下的投影)
在 下最小化 。令 ,駐點條件為 、,故 ;可行性給出 、。等式乘子可以為負。目標函數凸且約束仿射,所以 KKT 證明全局最小值為 。另一證法是 ;兩種方法得到同一下界。
例題 2.1.8
(活躍約束的乘子可以為零)
在 下最小化 。唯一最優點是 ,約束在此活躍。駐點條件 給出 ,所有 KKT 條件成立。因此活躍本身不保證乘子為正。雖然可行集阻止向右移動,無約束最優點已在邊界,故放寬約束沒有一階改善。
例題 2.1.9
(對偶函數可以無下界)
在 下最小化 。對 ,。在整條實線上取下確界,除非 ,否則結果為 ; 時結果為 。對偶最大值因此為 ,在 取得;原可行點 的值亦為 ,構成相等證書。此計算說明必須在整個定義域上最小化 ,不能只代入原問題可行點。
敏感度及符號檢查
概念視角分析
乘子作為最優值的導數
設約束 寫成 。固定某最優乘子並改變 ,拉格朗日函數改變 。在最優值函數 可微且包絡公式適用的條件下,。因此乘子亦是一個變化率:約束每放寬一單位,最優值的邊際下降量。負號符合直覺:增大 擴大可行集,最小值不可能上升。即使不可微,單調性仍成立,但具體導數公式未必成立。
上面的二次例子若把右端 改成 ,當 ,活躍解為 ,最優值 ,乘子 。微分得 。當 ,無約束最小點可行,最優值和乘子均為零。這個計算同時顯示乘子的局部含義以及活躍集的轉變。
選擇及檢查候選點
小問題可列出可能的活躍集,聯立駐點及活躍等式,再檢查所有不等式和乘子符號。不滿足任一條件的代數解不是 KKT 點。不活躍約束的乘子必為零,但反過來不一定。最後應以凸性證明充分性,或為非凸問題另給論證。非凸問題的 KKT 駐點可以是極大點或鞍點,因此解出乘子方程並非證明的終點。
不靠猜測建立對偶問題
計算次序很重要。先寫清原問題定義域,並按選定約定整理不等式方向;再以非負不等式乘子和不受符號限制的等式乘子建立 。固定乘子後,在整個定義域上對 取下確界,容許結果為 ;最後才在乘子可行範圍內最大化對偶函數。即使 的最小點不存在,下確界仍定義了 ;不能無理由地把一個駐點代入並稱作對偶值。
例如在 下最小化 。對 ,配方得 ,所以 。最大化得乘子 、;原可行點 的值也是 ,形成全局證書。 是 的全局最小點,理由是平方項係數為正,而不只是導數為零。
即使原問題不凸,對偶函數仍凹。令兩組乘子為 ,。由拉格朗日函數對乘子是仿射的,
因為下確界內每項均不小於各自下確界,便得到不等式。故在凸的乘子可行域上最大化對偶函數是凹函數最大化問題。但凹性本身不保證有限最優值或零對偶間隙;這些是另外要問的問題。
會:沒有凸性時,即使是單變量問題,對偶最優值也可以嚴格低於原問題最優值。
自然延伸的下一個問題
最好的對偶界會否嚴格低於最優值?
會:沒有凸性時,即使是單變量問題,對偶最優值也可以嚴格低於原問題最優值。
在非凸定義域 上,於 之下最小化 。唯一可行點是 ,所以 。對 ,
其最大值為 。對偶間隙 為正,所以沒有乘子能證明最優性。凸性加上 Slater 條件是排除這種間隙的一種充分條件。
常見錯誤
必須一併檢查候選點和乘子。弱對偶總給出下界,但原與對偶最優值相等是另一個命題;對非凸問題,單有 KKT 條件不能證明駐點全局最優。
常見錯誤
(以為每個活躍約束都有正乘子)
活躍約束不一定有正乘子:在 下最小化 ,約束活躍而 。另一方面,本節最小化約定中, 的負乘子則不可行。
常見錯誤
(只在可行點上最小化拉格朗日函數)
對偶函數是在整個定義域取下確界,不是在原問題可行集上取。對 下最小化 的問題,若在 時只考慮可行的 ,會得到 ,而正確的值是 。
常見錯誤
(混用符號約定)
改變符號約定不改變原問題,但會改變證書的公式。例如把 寫成 ,使用非負乘子乘以 。若改寫為 卻仍在同一拉格朗日函數中保留同樣符號,該項在可行點會給出上界方向的貢獻。解釋乘子前,應先核對弱對偶不等式。
總結
拉格朗日函數把約束轉成候選下界。若原可行點和對偶可行乘子的值相同,即證明全局最優。在可微凸問題中 KKT 條件產生這種證書;在前述假設下嚴格可行性保證已取得的最優點有證書。這些工具足以處理本節例題,並非涵蓋所有對偶性及約束資格條件。
練習
快速檢查
(在 下最小化 ,給出 KKT 證書。)
無約束最小點不可行,故試設約束活躍。
解答 · 答案
最小點 ,由 處的 得 ;可行、非負和互補鬆弛均成立,由凸性得最優。
快速檢查
(在 下最小化 ;約束是否活躍,乘子是多少?)
比較無約束最小點與上界。
解答 · 答案
最小點為零,該處不等式嚴格成立,故約束不活躍,互補鬆弛給出乘子為零。
快速檢查
(求在 下最小化 的對偶函數 (),並驗證兩邊最優值相等。)
對所有實數 最小化 。
解答 · 答案
對 最小化 得 ,所以 。在 上最大值是 ,等於原問題值 。