為何需要障礙法
罰函數法與增廣拉格朗日(Lagrange)法以懲罰違反約束的程度來處理約束,其迭代點一般不可行。內點法則相反:每個迭代點都嚴格可行,並以一個在邊界處趨向 的障礙項使迭代點遠離邊界。參數 逐步減弱障礙的影響,所得的極小點曲線(中心路徑)收斂到解。借助拉格朗日與 KKT 單元中的拉格朗日函數及弱對偶,一個簡短的論證便把路徑上每一點變成目標值離最優有多遠的有據界。計算這些點則使用線搜索與牛頓(Newton)法單元中的帶線搜索牛頓法。
定義
考慮問題
其中 為凸且連續可微。以 記最優值。
定義 12.1.1
(嚴格可行與對數障礙函數)
若集合
非空,則稱問題嚴格可行。在 上,對數障礙函數為
障礙函數在 上為凸: 為凸且遞減, 為凹且為正,故每一項皆凸。它可微,;當 內的點趨近某個 的點時,。注意 取決於函數 本身,而不只是它們所描述的可行集;這一點在下文很重要。
定義 12.1.2
(中心化問題、中心路徑與中心乘子)
對 ,中心化問題為
若對每個 它都有極小點 ,則集合 稱為中心路徑,而中心乘子為 ,。
我們假設對每個 極小點都存在。例如可行集有界時便成立,因為目標函數在 上連續,並在 的邊界處趨向 。由於 為開集且目標函數可微, 由駐點條件刻劃:
因中心化目標為凸,此條件亦是極小點的充分條件。因 ,中心乘子嚴格為正。
概念視角代數
中心路徑即擾動的 KKT 方程組
恰好是把互補鬆弛條件放寬到同一正數水平後的 KKT 方程組之解:
把駐點條件除以 ,便見 滿足這些方程。反之,若 滿足它們,則 ,把第一條方程乘以 便得中心化駐點條件,所以 是中心化問題的極小點。當 ,乘積 被推向零,這正是 KKT 互補條件。牛頓型原始–對偶方法線性化的正是這個描述。
中心路徑上的對偶間隙
擾動的互補條件 正是可計算間隙的來源。
定理 12.1.3
(中心路徑上的對偶間隙)
在上述假設下,對每個 ,
證明
(在中心乘子處計算對偶函數)
可行,故 。把駐點條件除以 ,得
即 是拉格朗日函數 在 時的駐點。對固定的 ,拉格朗日函數對 為凸,故駐點是 上的全局極小點。因此對偶函數滿足
因為 個約束中每個都有 。弱對偶給出對每個 有 。
證明透視
三個假設,三項不同的工作
的可行性只提供上界。嚴格可行性令中心乘子有定義且為正,所以 是容許的對偶點。凸性只有一項工作:把 的駐點提升為全局極小點,從而把 認定為對偶值 。數量 則來自一個簿記恆等式:每個約束恰好貢獻 ;論證最後以弱對偶收結。證明沒有用到 或原問題解的唯一性,也不需要知道 的值。
因此 是 -次優的,無須知道 即有停止準則。凸性要求針對函數 ,不能減弱為可行集的凸性。
反例模式
凸集的非凸描述
聲稱:只要可行集是凸的,任何光滑描述都令間隙界成立。用 描述 (它在 上不是凸函數),並極小化 ,故 、。此時 ,中心化目標 的駐點條件為 ,所以 。間隙界會給出 ,這是錯的。證明在凸性一步失效:,而 無下界,其駐點不是極小點。若改用凸描述 ,同一問題給出 ,間隙恰為 。修正後的敍述保留每個 為凸的假設。
量 亦隨 不增,其論證只用到極小性。
命題 12.1.4
(目標值沿中心路徑下降)
若 ,則 。
證明
(把兩個極小性不等式相加)
記 ,。由極小性, 及 。兩式相加, 抵消,餘下 。因 ,故 。
算法
給定嚴格可行的 、初始 、因子 及容差 :
- 令 。
- 中心化。 由當前點出發,用帶回溯線搜索的牛頓法在 上極小化 。線搜索須保持在 內:試探步長不斷縮減,直至嚴格可行並達到充分下降。令 為(近似)中心化點 。
- 若 則停止;由對偶間隙定理,。
- 令 ,,回到步驟 2。
不變量。 每個迭代點都在 內,故 有限,每個中心化階段的駐點條件皆有意義。外層循環的終止。 由於 ,檢驗 首次成立於
(若括號內的量非正則取 ),故恰好解 個中心化問題。此公式不計內層牛頓迭代的次數。對一般凸數據,若無障礙函數的進一步結構(自協調性,此處不展開),無法用此類公式限定其次數; 的選取是在較少的外層步數與較難的中心化問題之間取捨。
例題
例題 12.1.5
(一個約束:間隙界取等號)
在 (即 ,,)下極小化 。此時 ,。中心化問題是極小化 。駐點條件為 ,故 。於是 :對偶間隙定理的界取等號。中心乘子為 ,正是該約束的真乘子。例如要證明間隙不超過 ,取 即可,此時 。
例題 12.1.6
(兩個約束,其中一個不活躍)
在 下極小化 ,取 ,,,。此時在 上 。令 ,駐點條件為
乘以 得 ,即 ,其根為 。取正號的根大於 (至少為 ),在 之外,故
時:,。駐點驗算:,,故 。乘子為 ,,而 即拉格朗日函數的駐點條件。有據的界為
與 一致。 時:,故 ,界為 ;真實間隙 小於 。不活躍的約束在界中仍佔 。間隙定理與單調性命題皆可見:。
例題 12.1.7
(熱啟動的牛頓步離開定義域)
在一個約束的問題中,設 的中心化已得 ,參數升至 。新目標 有 、,故在 的牛頓方向為 。完整一步到達 。把步長逐次減半,試探點依次為 、、,都在 之外,然後是 。此處 ,低於 ;取 的 Armijo 測試只要求 。於是接受此步,繼續趨向 。這個邊界情況說明線搜索為何必須先檢查是否屬於 才計算 :牛頓公式本身提出了一個障礙函數無定義的點。
常見錯誤與細節
常見錯誤
(由並非嚴格可行的點出發)
方法需要嚴格可行的起點。內部為空的問題(例如把等式寫成兩個不等式)有 ;等式約束應作為仿射約束放進中心化問題,而不是障礙項。找出 中的第一個點是另一個獨立的第一階段問題。
常見錯誤
(在未中心化的點引用 m/t)
界 針對精確中心化的點。在一個約束的問題中取 ,嚴格可行點 會給出錯誤的界 。只是近似在路徑上的點,其間隙界還要加上一項,視駐點條件的偏差而定。
常見錯誤
(讓線搜索離開內部)
線搜索必須拒絕離開 的步長:障礙函數在該處為 (無定義),而牛頓步的公式並不知道定義域,熱啟動例題正好說明這點。
另有三點容易忽略。
- 中心路徑是一條隨參數變化的問題的極小點曲線,並不是迭代點的路徑;迭代點只是近似地沿它前進。
- 增大 令中心化問題更病態:其 Hessian 含有大小為 的項,在邊界附近爆炸。因此採用適中的 及熱啟動,而不是一次用極大的 求解。
- 對偶間隙定理並不要求 或原問題的解唯一;它只用到 是中心化問題的極小點。
練習
快速檢查
(在 下極小化 。求 ,並求使對偶間隙定理能證明 的最小 。)
取 ,解中心化駐點條件。
解答
取 ,中心化目標為 ,駐點條件為 ,故 ,,其中 。對 ,定理證明的間隙為 ,故需 ,即 ;最小的 為 。
快速檢查
(取 ,,,。障礙法要解多少個中心化問題?各在哪些 值?)
找出首個滿足 的 。
解答
檢驗 要求 。因 ,首個滿足的 為 。公式給出 。故共解 個中心化問題,在 。
快速檢查
(在 下極小化 。計算 、 時的中心乘子,以及所得的 有據下界。)
消去駐點條件的分母,並取 內的根。
解答
此時 ,,,。 時駐點條件為 。乘以 得 ,即 ,在 內的根為 。乘子為 ,,滿足 。下界為 ,等於對偶值 ,且不超過 。(真實間隙為 。)
快速檢查
(在 、 下極小化 。求 、中心乘子,以及準確間隙 。)
中心化目標可分拆為單變量問題。
解答
中心化目標為 ,故 、。取 、,中心乘子為 、,滿足 。因 ,間隙為 ,恰好取等:線性問題的每個約束在解處都活躍時,界可以取到。
快速檢查
(在兩個約束的例題中,給出由 得到的 有據區間,並驗證它包含 。)
用 ,其中 。
解答 · 答案
時,,,其中 (取 )。區間為 ,包含 。