完整搜尋頁面 →

沿著中心路徑走向最佳頂點

進階OPT 07・等式限制與內點法互動圖表

題目說明

在兩變數線性規劃上提高障礙權重 t,觀察中心點、對偶界與差距 m/t。

試試看:把 t 乘以十。與邊界的距離、真實的次佳程度與界限 m/t 如何改變?再旋轉目標方向:路徑仍然會停在頂點嗎?

先預測

你把障礙權重 t 乘以 10。對偶差距 m/t 會怎麼變?

提示

使用這個實驗的章節段落:

解析

請先回答預測問題,或在準備好時再打開解析。

顯示解析

差距恰為 m/t,所以與 t 成反比。有 m = 5 條限制時為 5/t:t = 10 時是 0.5,t = 100 時是 0.05。中心點朝最佳頂點移動,其真正的次佳程度絕不超過這個界限。

實驗 · 沿著中心路徑走向最佳頂點

先預測

你把障礙權重 t 乘以 10。對偶差距 m/t 會怎麼變?

差距 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。

方法來源

在互動實驗頁開啟 →