沿著中心路徑走向最佳頂點
進階OPT 07・等式限制與內點法互動圖表
題目說明
在兩變數線性規劃上提高障礙權重 t,觀察中心點、對偶界與差距 m/t。
試試看:把 t 乘以十。與邊界的距離、真實的次佳程度與界限 m/t 如何改變?再旋轉目標方向:路徑仍然會停在頂點嗎?
解析
請先回答預測問題,或在準備好時再打開解析。
顯示解析
差距恰為 m/t,所以與 t 成反比。有 m = 5 條限制時為 5/t:t = 10 時是 0.5,t = 100 時是 0.05。中心點朝最佳頂點移動,其真正的次佳程度絕不超過這個界限。
實驗 · 沿著中心路徑走向最佳頂點
- 差距 m/t
- 0.5
- 次佳程度 c·x − p*
- 0.1841
- 到最近邊的距離
- 0.109
t = 10 時,中心點離最近的邊 0.109。它的次佳程度 0.1841 不超過對偶差距 m/t = 0.5;由對偶點 λ = 1/(t·鬆弛量) 算出的差距為 0.5。
試試看:把 t 乘以十。與邊界的距離、真實的次佳程度與界限 m/t 如何改變?再旋轉目標方向:路徑仍然會停在頂點嗎?
在有 m = 5 條邊限制 a_i·x ≤ b_i 的凸五邊形上最小化 c·x。中心點最小化 t·c·x − Σ log(b_i − a_i·x)(阻尼牛頓法)。令 λ_i = 1/(t s_i)(s_i 為鬆弛量),對偶目標為 −b·λ,對偶差距恰為 Σ λ_i s_i = m/t。真正的次佳程度 c·x − p* 不會超過 m/t。