用斜率構造下界
可微凸函數的切線位於圖像下方。若函數不可微,或我們想找指定斜率下最好的仿射下界,該怎樣做?對 ,定義它的共軛函數為
擴充值 可用來表示約束:非空集合 的指示函數 在 上為零,在集合外為 。若 在某點有限且從不取 ,稱它為真函數;下文除另有說明外均假設它是真函數。即使如此, 仍可能為無窮大:這表示指定斜率下沒有有限截距的仿射下界。由於 是一族關於 的仿射函數的上確界,它總是凸函數,即使 本身不是凸的。
對任何 的 和任何 ,定義立即給出 Fenchel 不等式:
兩邊將不同變量分開,因此它能產生對偶下界。等號亦有明確的幾何意義。回想 表示對每個 都有 ;這個定義對真函數均有意義,不要求可微。
定理 5.4.1
(Fenchel 不等式的等號)
設 為真函數且 。則 當且僅當 。特別地,等號成立時 有限。
證明
(上確界與支撐平面表達同一條件)
等號表示 是所有 的上確界,也就是對每個 ,
移項便得到次梯度不等式 。反過來,次梯度不等式使上確界不超過 ;取 又使它不少於該值,故等號成立。由於 有限, 亦有限。這個等價性不需要可微、凸性或另一個最大值存在定理。
三個手算共軛函數
例題 5.4.2
(二次函數的共軛)
對 上的 ,配方得 ,所以 ,上確界在 取得。(1) 的等號恰好在 時成立,與定理對可微函數的預測一致。
例題 5.4.3
(絕對值的共軛)
對 ,若 ,則 ,而 達到零;若 ,令 沿 的符號方向趨向無窮,則 無界。因此 。在 ,(1) 的等號為 ,給出熟悉的 ;當 ,等號迫使 且 ,所以 。
例題 5.4.4
(指示函數的共軛:支撐函數)
對非空集合 ,,因為 以外的點貢獻 。這稱為 的支撐函數。若 ,它在 時為 ,在 時為 。這裏上確界是在真正的可行集合上取的,而不是自動取遍整個 。對無界集合 ,同樣的計算給出: 時 , 時為 ;共軛在整條半直線上取值 。
下例由兩個不同函數得到同一個共軛,於是自然要問:共軛究竟記住了甚麼?
反例模式
共軛不保留任意非凸細節
令 ,其他點取 ,則 。區間 的指示函數也有同一共軛,但在 處前者為 ,後者為零。因此不能不加條件地說取兩次共軛便能還原任意函數;還原定理需要閉凸等假設。
等式約束的對偶下界
設 為 實矩陣,考慮
每個乘子都給出一個下界。
命題 5.4.5
(等式約束的弱對偶)
對每個 及每個可行 ,
因此即使兩個最優值都沒有取得,仍有 。
證明
(以 為斜率的 Fenchel 不等式)
若 ,無需證明。否則把 代入 (1):,再由可行性 ,右邊就是 。若 ,則 ,不等式自然成立。對可行 取下確界,再對 取上確界,便得最後一個結論。
轉置前的負號來自拉格朗日(Lagrange)函數 ;採用相反符號也可以,但必須前後一致。
定理 5.4.6
(原問題與對偶問題的解構成最優證書)
若 可行、,且 ,則 在約束 下最小化 、 最大化 ,而且 。
證明
(使兩個界相等)
由等號定理及可行性,,所以 。弱對偶說任何對偶值都不超過任何可行目標值,因此對所有 及所有可行 都有 ,兩者均為最優。
這是充分證書;沒有額外假設時,不能斷言這樣的乘子必定存在。
常見錯誤
(把證書定理倒過來讀)
定理並沒有說每個約束問題都有滿足 的乘子。沒有進一步假設時,對偶下界可以嚴格小於原問題的值。對 上的 及約束 ,原問題的值為 ,而 給出 ,故 。
例題 5.4.7
(線性等式下的最小範數)
最小化 ,條件為 。這裏 ,逐座標配方得 。因此 ,在 取得最大值 。可行點 的目標值也是 ,且 。兩個界相等,便嚴格證明了全局最優性。
概念視角幾何
證書需要上下兩個界
可行點給出原問題最優值的上界,乘子給出下界,兩界相等便封閉了間隙。單有駐點方程而點不可行,或單有可行點,都不足以證明最優。
練習與解答
快速檢查
(求 的共軛及上確界取得的位置。)
配方前先平移變量。
解答 · 答案
令 ,則 。配方得 ,在 ,即 取得。
快速檢查
(求 的共軛及次微分 。)
在區間上最大化一個線性函數。
解答 · 答案
在 上最大化 : 時得到 , 時得到 。在 ,不等式 對所有 成立,恰好當 。因此 。區間外左邊為 ,不構成額外限制。
快速檢查
(最小化 ,條件為 。利用 求對偶最大點。)
對偶函數只在 時有限。
解答 · 答案
唯一可行點為 ,目標值為 。當 時對偶值為 ,否則為 ,故在 取得最大值 。亦可驗證 。原問題與對偶問題的值相等。
快速檢查
(對無約束函數 ,求 ,並解釋為何這個精確下界不給出最小點。)
考慮 (1) 的等號能否成立。
解答 · 答案
,所以 (1) 給出精確下確界 。但每個有限 都滿足 ,故等號從不成立,下確界不被取得。精確的下界未必能達到。