動機
下界只有在知道它為何有效及是否能達到真實最小值時,才能完成最優性證明。凸幾何提供這個理由:超平面能把點與凸集分離;次梯度則是凸函數的支撐斜率。把分離應用到可實現的約束違反量與目標值集合,支撐超平面便成為拉格朗日(Lagrange)乘子。本節在明確的有限維假設下推導這個關係,並檢查假設失敗時可能發生的事。
非光滑函數同樣需要幾何。絕對值在零沒有普通導數,卻有支撐斜率和清楚的最小點。次梯度記錄這些斜率。把乘子解釋為最優值的導數,則另外需要價值函數可微;一般只能得到不等式。
定義
定義 5.1.1
(凸集、次梯度與次微分)
非空集合 若包含任意兩點間整條線段便是凸集。設有限凸函數 定義於開凸集 。若
則 是 的次梯度;全體次梯度記為 。因此 當且僅當 在 上最小化 。若 在 可微,則 :導數給出支撐斜率,並沿正反方向測試可證其他次梯度相同。例如 在零的次微分為 。
定義 5.1.2
(歐氏投影)
對閉非空凸集 及點 ,歐氏投影 是距離 最近的唯一 中點。將最小化序列限制在有界球內並取收斂子列,得到存在;距離平方的嚴格凸性給出唯一性。沿 至任意 的線段微分距離平方,得投影不等式 。
定理/命題
定理 5.1.3
(與閉凸集嚴格分離)
若 非空、閉且凸,,則存在非零向量 及純量 ,使對所有 均有 。
對偶證明會用到兩個關於開凸集的輔助事實。
引理 5.1.4
(開凸集與其閉包)
非空開凸集 滿足 。
命題 5.1.5
(與開凸集的弱分離)
若非空開凸集 不含 ,則存在非零 ,使所有 滿足 。
有了這些工具,便可陳述主要的對偶定理。
定理 5.1.6
(Slater 強對偶及乘子取得)
設 為開凸集, 在 可微且凸, 仿射。假設存在 滿足 及所有 ,而有限的原問題最小值 在 取得。則存在 和 ,使 滿足 KKT,且對偶最大值等於 。
這是嚴格不等式版本的充分條件;更一般的相對內部版本可放寬部分仿射不等式。結論既包括零間隙,也包括對偶乘子取得最大值。單有凸性或原問題最小點,並不能推得這兩項。
證明思路
由投影得到分離
證明
(由投影得到分離向量)
取 和 。因 ,。投影不等式給出每個 的 ;但 ,取 即得結論。支撐平面垂直於由 到 的最短線段,嚴格間隙就是距離的平方。閉性不可省:、 時,沒有線性函數能在 和集合之間留出嚴格間隙。
概念視角分析
分離向量是距離函數的次梯度
設 ,這是一個凸函數,恰好在 上為零。對 及 ,向量 是 在 的次梯度:記 ,投影不等式給出 ,所以 。當 時左邊為零,整理後即得 。因此嚴格分離就是 的次梯度不等式在其零集上的讀法。
證明
(從內部逼近單形)
先證一個基本引理:非空開凸集 等於 。包含關係 顯然。反過來,若 在閉包內部,可選一個包含 於其內部、且足夠小而位於該內部的單形。以 中點充分近似各頂點,令 仍在所得新單形內部。凸性使整個新單形屬於 ,所以 。此引理的證明沒有使用分離定理。
證明
(以極限得到弱分離)
還需使用開凸集分離推論:若非空開凸集 不含 ,存在非零 使所有 滿足 。若 ,可對閉包使用投影證明;若 ,取不屬於閉包且趨於 的點列,逐一分離,將法向量正規化並取單位球面上的收斂子列,再令點列趨近 ,便得到弱分離。引理保證 時 ,所以這兩種情況已涵蓋所有可能。
擾動集合的支撐平面
證明
(分離嚴格上集)
先限制在仿射切片 ,定義嚴格上集
非空且開:對已給的見證點,稍微改變 後嚴格不等式仍成立。兩個見證點的凸組合仍在 ,各函數的凸性保留嚴格上界,故 凸。 不屬於 ,否則存在原問題可行點的值小於最小值。
將此點與 分離。 沿每個座標向上封閉,故分離法向量 滿足 、,以及
對任意 ,從上方趨近 ,得到 。若 ,嚴格可行點對任何非零 都有 ,矛盾。所以 ;除以它並重用 記號,得到
在 ,可行性給出相反不等式,故取等號,並且每個 。凸可微函數 在仿射切片上由 最小化。由 開放,沿 的每個方向可作足夠小的正反移動,所以 與 正交,屬於 。選 令 。
完整拉格朗日函數在 凸且於 駐定,其下確界因此等於該處值 。構造出的乘子取得對偶值 ;弱對偶又限制任何對偶值不超過它。這同時證明零間隙和對偶取得,並無預先假設後者。
擾動證明中的符號為何固定
證明透視
嚴格上集的作用
論證依靠 的三個特點。第一, 向上封閉,這迫使符號確定:若法向量在某座標的係數為負,在 內把該座標推向 ,便令 趨於 ,違反其下界。所以 、,而分離定理保證 。第二,嚴格可行性只在一步使用,就是排除 :由 ,任何非零 都給出 。一旦 ,把它正規化為一,餘下座標便成為乘子;若只有邊界可行點,則可能出現 的異常法向量,如下面對偶不取得的例子。第三,嚴格不等式令 直接為開凸集,無須假設價值函數的上圖集閉合,而這一點可能不成立:非緊緻定義域上的下確界未必取得,閉凸集的投影亦未必閉。從上方趨近 ,便把弱分離轉化為 上的不等式。等式乘子在此之後才由仿射切片的梯度條件加入,所以對偶取得是結論而非假設。
價值函數與敏感度
對不等式右端 ,令 ,不可行時取 ;對 定義 。
命題 5.1.7
(乘子是價值函數的次梯度)
假設 有限,而某對 (其中 )滿足 ,例如上述 Slater 假設下便成立。則
所以 是延伸值凸函數 在零的次梯度。若 在零可微,則 。
證明
(擾動問題的弱對偶)
若 不可行,則 ,無需證明。否則設 滿足 及 。由於 ,
對這些 取下確界即得不等式。若 在零可微,把 分別除以小的 及小的 ,得到對每個 都有 。
對不可行的擾動,這個不等式仍有意義;不可微時可以有多個支撐斜率。價值函數的凸性可由兩個擾動的近似最優可行點取凸組合,再令目標誤差趨零得到。
尖角處的支撐斜率
即使定義簡單,價值函數也可能不可微。考慮 。在零,每個 都滿足對所有 的 ,所以 。左右斜率分別為零及一,普通導數不存在。一個次梯度仍提供有效的全局下界,但只描述其中一條支撐線,不是唯一的邊際變化率;可微時所有支撐斜率才必須相同。
次梯度可直接相加。若同一凸定義域上 、,相加兩個定義不等式得到 。反向的完整求和公式需要另外的正則性假設,本節只需這個包含關係。例如 :加上仿射項將 的每條支撐斜率加二;反過來減去仿射項可證沒有其他斜率。
例題詳解
例題 5.1.8
(投影產生分離直線)
設 、。投影 ,。每個點 滿足 ,但 。直線 支撐 並嚴格分離 。
例題 5.1.9
(非光滑次微分)
對 ,不等式 對所有 成立,當且僅當 :分別測試正負 得兩個界,且兩界亦充分。所以 證明零點最小,即使普通導數不存在。正點的次微分是 ,負點是 。
例題 5.1.10
(一個有尖角的價值函數)
在 和 下最小化 ,其值是 。 時兩個約束均活躍。將它們寫成 和 ,駐點條件為 ,且乘子非負。每個和為一的乘子對均最優。第二個約束的擾動支撐斜率是 ,恰好是 在零的次微分。這個線性凸問題說明,乘子不唯一和價值函數不可微可以同時出現;兩者都不表示存在對偶間隙。
支撐不等式對所有擾動成立,即使所選乘子不唯一。離開基準點後,它通常比真實價值函數弱。尖角例子中,斜率零給出 ,斜率一給出 。在此例取這兩個仿射下界的最大值恰好恢復 ;一般最優化問題並不自動如此。
常見錯誤
以下是處理分離與乘子時容易犯的錯誤。
常見錯誤
(期望與開集嚴格分離)
若 位於開凸集 的閉包內但不屬於 ,便只能得到弱分離。對開單位圓盤及 ,法向量 在圓盤上給出 ;但不存在 使所有 都滿足 ,因為圓盤中的點可任意接近 。
常見錯誤
(一個乘子不代表價值函數可微)
在尖角處,次微分可以包含許多斜率。上面的尖角例子中,每個 都是最優乘子,而 在零沒有導數。選定一個乘子只證明一條支撐不等式,並非唯一的邊際效應。
常見錯誤
(Slater 條件是充分而非必要)
沒有嚴格可行點時,問題仍可零間隙且對偶取得。在 及 下最小化 ,唯一可行點為 ,Slater 條件不成立;但 在 時為 ,否則為 ,而 取得原問題的值 。
零間隙與對偶取得是兩個不同的結論,定理同時斷言兩者。
反例模式
值相等不保證對偶有最大點
由 便斷定某個乘子取得上確界,是很自然卻錯誤的推論。在 下最小化 。唯一可行點是零,所以 。對 ,:該函數在零的導數為一,稍向左移便降低拉格朗日函數值。但當 時 :對 ,由 得 ,而 。因此值上強對偶成立,卻沒有有限乘子取得對偶值。缺少的假設是嚴格可行性:沒有點滿足 。若有嚴格可行點,分離論證便會給出取得對偶值的乘子。
總結
投影給出閉凸集的嚴格分離;對凸擾動集合用開集分離得到乘子,嚴格可行性迫使目標係數非零。仿射切片的梯度條件補上等式乘子,從而證明對偶取得。次梯度表達支撐不等式,導數則需要更多光滑性。
練習
快速檢查
(求 到 的投影,並寫出嚴格分離不等式。)
沿鉛直方向投影到直線 。
解答 · 答案
投影是 ;取 ,在半空間上有 。
快速檢查
(求 在零的值,並求 的最小值或說明不存在。)
使用次梯度之前,先看負的 。
解答 · 答案
。當 ,,所以沒有最小值。該和在零的次微分為 ,不含零。
快速檢查
(在 下最小化 。求最優乘子及零附近擾動約束 的價值函數。)
從擾動約束解出 的範圍。
解答 · 答案
寫 ,最小點 ,駐點條件給 。當 ,可行集為 ,故 、; 時公式改變。
快速檢查
(對上述不取得的對偶例子,證每個有限 有 ,並找一個趨向一的下界。)
利用 。
解答
在零的導數為一,稍向左移使值小於一。對 , 給出 。又 ,所以上確界為一但不取得。