這是 MVP 首批 7 篇主幹的最後一篇。前面鋪了三塊墊腳石——凸集的分離超平面定理、LP 可行域的頂點幾何、單體法的 pivot——這篇要把它們接起來，證明 LP 裡最漂亮的一個結論：原問題與對偶問題的最佳值永遠相等 。
01 弱對偶回顧
給定原問題 min { c ⊤ x : A x ≥ b , x ≥ 0 } \min\{c^\top x : Ax \ge b, x \ge 0\} min { c ⊤ x : A x ≥ b , x ≥ 0 } max { b ⊤ y : A ⊤ y ≤ c , y ≥ 0 } \max\{b^\top y : A^\top y \le c, y \ge 0\} max { b ⊤ y : A ⊤ y ≤ c , y ≥ 0 } x x x y y y
⧉ 複製 LaTeX b ⊤ y ≤ c ⊤ x . b^\top y \le c^\top x. b ⊤ y ≤ c ⊤ x . 一行證明：b ⊤ y ≤ ( A x ) ⊤ y = x ⊤ ( A ⊤ y ) ≤ x ⊤ c = c ⊤ x b^\top y \le (Ax)^\top y = x^\top (A^\top y) \le x^\top c = c^\top x b ⊤ y ≤ ( A x ) ⊤ y = x ⊤ ( A ⊤ y ) ≤ x ⊤ c = c ⊤ x A x ≥ b , y ≥ 0 Ax \ge b, y\ge 0 A x ≥ b , y ≥ 0 A ⊤ y ≤ c , x ≥ 0 A^\top y \le c, x \ge 0 A ⊤ y ≤ c , x ≥ 0
02 強對偶定理敘述
**強對偶（strong duality）**更進一步：只要原問題有最佳解 x ⋆ x^\star x ⋆ y ⋆ y^\star y ⋆
⧉ 複製 LaTeX c ⊤ x ⋆ = b ⊤ y ⋆ . c^\top x^\star = b^\top y^\star. c ⊤ x ⋆ = b ⊤ y ⋆ .
用一個具體例子：原問題 max 2 x + 3 y 2x+3y 2 x + 3 y 4 y 1 + 5 y 2 4y_1+5y_2 4 y 1 + 5 y 2 灰色永遠不會跑到橘色左邊 （弱對偶）。切到兩邊都是各自的最佳頂點時，兩個箭頭會精確疊在同一點上——這就是強對偶。
✦ 直覺 弱對偶保證「對偶可行值永遠是原問題的一個下界」——就像從各種角度量身高，量出來的都不會比真實身高高。強對偶則說：只要原問題真的有解，一定存在某個角度，量出來的下界剛好等於真實身高，不多不少。
03 證明（用分離超平面定理）
▸ 展開完整證明Proof · 幾何構造 設 x ⋆ x^\star x ⋆ v ⋆ = c ⊤ x ⋆ v^\star = c^\top x^\star v ⋆ = c ⊤ x ⋆ R m + 1 \mathbb{R}^{m+1} R m + 1
⧉ 複製 LaTeX S = { ( A x − b , c ⊤ x − v ⋆ ) : x ≥ 0 } , T = { ( u , t ) : u ≥ 0 , t < 0 } . S = \{(Ax - b,\ c^\top x - v^\star) : x \ge 0\}, \qquad T = \{(u, t) : u \ge 0,\ t < 0\}. S = {( A x − b , c ⊤ x − v ⋆ ) : x ≥ 0 } , T = {( u , t ) : u ≥ 0 , t < 0 } . 可以驗證 S S S x ≥ 0 x \ge 0 x ≥ 0 A x − b Ax-b A x − b c ⊤ x − v ⋆ c^\top x - v^\star c ⊤ x − v ⋆ T T T
關鍵一步 ：S ∩ T = ∅ S \cap T = \emptyset S ∩ T = ∅ x ≥ 0 x \ge 0 x ≥ 0 A x ≥ b Ax \ge b A x ≥ b x x x c ⊤ x < v ⋆ c^\top x < v^\star c ⊤ x < v ⋆ v ⋆ v^\star v ⋆
由於 S , T S, T S , T ( y , λ ) ≠ 0 (y, \lambda) \ne 0 ( y , λ ) = 0 λ ≥ 0 \lambda \ge 0 λ ≥ 0 y ≥ 0 y \ge 0 y ≥ 0 x ≥ 0 x \ge 0 x ≥ 0
⧉ 複製 LaTeX y ⊤ ( A x − b ) + λ ( c ⊤ x − v ⋆ ) ≥ 0. y^\top (Ax - b) + \lambda (c^\top x - v^\star) \ge 0. y ⊤ ( A x − b ) + λ ( c ⊤ x − v ⋆ ) ≥ 0. 取 λ > 0 \lambda > 0 λ > 0 λ = 0 \lambda = 0 λ = 0 λ \lambda λ y ˉ = y / λ \bar{y} = y / \lambda y ˉ = y / λ y ˉ ≥ 0 \bar{y} \ge 0 y ˉ ≥ 0 A ⊤ y ˉ ≤ c A^\top \bar{y} \le c A ⊤ y ˉ ≤ c y ˉ \bar{y} y ˉ b ⊤ y ˉ ≥ v ⋆ b^\top \bar{y} \ge v^\star b ⊤ y ˉ ≥ v ⋆
配合第一節的弱對偶 b ⊤ y ˉ ≤ v ⋆ b^\top \bar{y} \le v^\star b ⊤ y ˉ ≤ v ⋆ b ⊤ y ˉ = v ⋆ = c ⊤ x ⋆ b^\top \bar{y} = v^\star = c^\top x^\star b ⊤ y ˉ = v ⋆ = c ⊤ x ⋆ y ˉ \bar{y} y ˉ
∎
▲ 注意 上面證明中「λ = 0 \lambda = 0 λ = 0
04 互補鬆弛條件
強對偶還有一個等價、且在演算法上更好用的刻畫：x ⋆ , y ⋆ x^\star, y^\star x ⋆ , y ⋆ 互補鬆弛（complementary slackness） ——對每一條約束，原變數與對應的對偶鬆弛不能同時非零。這個條件正是 KKT 條件在 LP 特例下的樣子，之後在 NLP 的 KKT 那篇會再完整展開。
至此，MVP 首批 7 篇主幹全部跑通：從凸集出發，經過分離超平面、LP 幾何、單體法，一路走到強對偶定理——Astro + KaTeX + D3 互動 + 可摺疊證明的完整流程都驗證過了。接下來可以往回補完整的 ~110 篇文章清單。