OPT 04・對偶性、KKT 條件與證明憑證
先備知識:OPT 03・線性、二次、錐與幾何規劃
導覽:本頁與本系列: 導覽:本頁與本系列
本頁內容
最佳化
你將學到
- 從拉格朗日函數推導受限制最小化問題的下界。
- 區分對偶可行性、弱對偶、強對偶與最佳值是否達到。
- 寫出 KKT 條件,辨認它何時能證明全域最佳性。
- 以正確的乘子符號解讀互補鬆弛與敏感度。
- 建立簡單的不可行性憑證,並把對偶序關係延伸至錐。
- 回報殘差與間隙,同時保留數值證據真正支持的範圍。
先看全貌
找到好的可行解,能給最佳成本一個上界。但是,我們怎麼知道其他地方沒有藏著更好的答案?對偶問題會產生下界。當上界與下界相遇,兩者就共同證明最佳值。
Boyd 與 Vandenberghe 的第 5 章 [1] 把這個想法連到幾何、支撐平面、乘子與數值演算法。即使已經會解原問題,對偶仍有用:它能驗證答案、說明有限資源的價值,並揭露另一種計算結構。
保證必須遵守符號與假設。任意選乘子算出的數值,不一定是下界。單靠很小的駐點殘差,也不是完整的證明。並非每個凸問題表示法都自動具備強對偶。
本章保留明確的定義域,使用能檢查精確答案的小例子推導。這套推理可以延伸至大問題,但實作細節與容許誤差仍是數值判斷的一部分。
從限制式到拉格朗日函數
白話說。 替每個不等式與等式附上一個價格,再最小化加上價格後的目標,而不直接強制這些限制。
考慮
是決策向量, 是最小化時保留的共同定義域, 是目標, 是不等式, 是等式。
拉格朗日函數為
是不等式乘子, 是等式乘子。若採用 的慣例,就要求 。等式乘子不限制符號,因為任何符號乘上可行點的等式殘差,結果都是零。
在可行點,不等式的貢獻非正,等式的貢獻為零。因此,當 非負時,。
把乘子稱為「懲罰」可能造成誤解。這裡的拉格朗日函數,並不是在無限制最小化時替違規加上一個很大的正成本。它的用途是建立一族下界,符號限制也由此而來。
定義對偶函數
是拉格朗日對偶函數,輸入為乘子對。它對 中的所有點取下確界,而非只看可行點。
對任一可行的 與非負的 ,
第一個不等式來自下確界,第二個來自原問題可行性與乘子符號。因此, 是原問題最佳值的下界。
若下確界為負無窮,這仍是正確、但沒有提供資訊的下界。想取得有用的憑證,必須選擇能產生適當有限對偶值的乘子。
為什麼對偶問題是凹的
白話說。 下界會隨價格改變。我們選擇能給最強下界的價格;這個最大化問題的目標是凹函數。
固定每個 時, 對乘子都是仿射函數。仿射函數逐點取下確界,會得到凹函數。因此,即使原問題不是凸的, 仍是凹的。
對偶問題是
以 表示對偶最佳值。弱對偶(weak duality)指出 ,其中 是原問題最佳值。這個結果不要求凸性,只需要符號正確的下界構造。
最大化凹函數,符合一般凸最佳化問題的意義。但是,求對偶函數值本身可能很困難,因為它也許要求解一個難解的非凸最小化。「對偶是凹的」不等於自動擁有容易計算的查詢工具。
對偶與原問題的維度也不必相同。每個明確對偶化的限制式各產生一個變數。把部分限制留在 中,而不加乘子,會改變寫出的對偶表示,但下界邏輯依然一致。
三行看懂凹性證明
對偶為凹,是因為取下確界後,混合價格的下界不會低於個別下確界的相應混合。令 收集乘子,取兩組容許價格 與 。拉格朗日函數對價格為仿射,因此
其中 是保留的原問題定義域、 是對偶函數;此比較考慮有限的對偶值。在同一 處,每項都至少等於自己的下確界,因此得到中間不等式。這個步驟完全沒有假設原目標凸 [1]。
計算上必須區分:原問題非凸時,只找到 的局部最小值,並不等於計算其下確界。該局部值可能高於 ,因而失去合法下界的意義。對偶凹性描述的是精確對偶函數,而不是任何自稱「對偶評估器」的近似程序。
完整的一維推導
白話說。 一個小例子就能看清價格、無限制最小化解與下界之間的關係。
在 下最小化 。 是純量。受限制最佳解是 ,成本 。
使用乘子 ,
拉格朗日函數的無限制最小化解滿足 ,所以 。代回後得到
隨選擇的乘子而變,不一定是原問題可行點。對偶是一條凹拋物線,在 達到最大值 。上界與下界於此相遇。
最佳乘子平衡了目標想增加 的力量,以及作用中的上界限制。若 太小,拉格朗日最小化解會落在允許區域之外;若太大,即使價格更高,下界反而更弱。

程式:驗證間隙與完整 KKT 條件
以下獨立計算會檢查原問題可行性、乘子符號、駐點條件、互補鬆弛,以及兩個數值相等。
程式碼 · Python · 14 行
import numpy as np
x, multiplier = 1.0, 1.0
objective = 0.5 * (x - 2)**2
dual_value = multiplier - 0.5 * multiplier**2
constraint = x - 1
stationarity = x - 2 + multiplier
complementarity = multiplier * constraint
assert constraint <= 0 and multiplier >= 0
assert abs(stationarity) < 1e-12
assert abs(complementarity) < 1e-12
assert np.isclose(objective, dual_value)
print("primal value:", objective, "dual value:", dual_value)
print("stationarity:", stationarity, "complementarity:", complementarity)強對偶與限制資格條件
白話說。 弱對偶永遠給出上下界次序。強對偶則說,最好的下界恰好等於最佳值;這需要額外條件。
強對偶(strong duality)表示 。它描述最佳值,不會自動保證最佳解存在。問題可能只有一串解逼近某個數值,卻沒有任何點真正達到它。
對具有仿射等式的凸原問題,一個標準充分條件是 Slater 條件 [1,第 5.2 節]:
是共同函數定義域, 是它的相對內部, 定義仿射等式限制。意思是存在一個點,位於適當內部、嚴格滿足不等式,並且滿足等式。
在這些假設下,強對偶成立。若最佳值有限,對偶最佳值也會達到。原問題是否達到最佳值,仍可能需要另外討論存在性。
仿射不等式有較弱的精細條件,所以要求它們全部嚴格成立,可能比必要條件更強。沒找到 Slater 點,本身不會推翻強對偶;它只表示這個充分條件尚未證明。
並非每種表示法中,凸性本身就已經足夠。定義域可能退化,限制資格條件也可能不成立。與其說「凸問題的間隙永遠是零」,應說明採用哪個條件,或直接驗證一對有效且相等的憑證。
定義域限制也是對偶的一部分
目標若包含對數或倒數,它的定義域仍要保留在拉格朗日最小化中。把它當成所有實數上都有定義的函數,會悄悄改變問題。
另一種方式是使用延伸值函數,在定義域外給正無窮。數學上這很方便,但數值程式不應把意外產生的無效浮點值當成模型慣例。
錐表示法可以一致地選擇對偶化或保留定義域與錐限制。這會影響對偶公式與符號。應從實際原問題推導下界,不要直接搬用符號不相容的公式。
零間隙也可能沒有最佳乘子
限制資格條件失敗不一定造成正對偶間隙,卻可能使乘子最佳值無法達到。考慮在 下最小化 ,其中純量 。唯一可行點是零,所以 ,而且沒有嚴格可行點。
拉格朗日函數為 。對 最小化得到
其中 是二次限制的價格, 是其對偶下界。對正 ,最小化點為 。當 無界增大, 趨近零。因此 ,但沒有任何有限乘子達到對偶最佳值。
在原問題解處,駐點條件要求 ,卻變成 。這種表示沒有 KKT 乘子。把等價限制改寫成等式 ,就有乘子 。可行決策不變,正則性與乘子描述卻改善。這正是 OPT 01 的隱藏等式與 OPT 07 的初始化值得重視的原因 [1]。
KKT 最佳性條件
白話說。 KKT 結合允許的原問題選擇、允許的價格、力的平衡,以及「有餘裕的限制不能帶正價格」這條規則。
對可微凸函數 與仿射等式 ,條件為
是原問題候選點, 是不等式乘子, 是等式乘子。最後一列是拉格朗日駐點條件。整組稱為 Karush–Kuhn–Tucker 條件。
對這個凸且可微的問題,全部條件成立,就足以證明原問題與對偶最佳性。非負乘子使拉格朗日函數對 為凸;駐點條件使 成為它的全域最小化解;可行性與互補鬆弛則使拉格朗日值等於目標值。
在適當資格條件,例如 Slater 條件下,最佳點也會存在滿足 KKT 的乘子。這提供必要性,以及前述充分性。應把兩個邏輯方向分清楚。
非凸問題的拉格朗日駐點,可能是對 的局部最大值或鞍點。KKT 在正則條件下可能必要,通常卻不能證明全域最佳性。凹二次函數的內部駐點就是簡單反例。
互補鬆弛提供單向資訊
若 ,互補鬆弛會迫使 。若 ,限制必須作用中:。
作用中的限制仍可能有零乘子。退化或冗餘限制可能使價格不唯一。因此,「作用中」與「正價格」不能互換。
在平滑受限制最佳點,負目標梯度會落在作用中限制法向量與等式法向量、搭配適當符號形成的組合裡。這解釋了駐點條件的幾何意義:可行下降方向無法降低目標。
數值上的接近作用中,依賴容許誤差。很小的餘裕搭配很小的乘子,可能難以做離散分類。若區別重要,應回報實際數值,避免硬給確定的作用中或非作用中標籤。
等式限制二次問題
白話說。 二次目標搭配線性等式時,KKT 條件形成一個線性系統,揭露後續受限制演算法需要的代數。
在 下,目標為 ,則
是對稱半正定矩陣, 是目標係數向量, 是等式矩陣, 是目標值, 是等式乘子。
即使最佳化問題是凸的,這個區塊矩陣通常仍是不定矩陣。要求正定矩陣的求解器,不能直接套用到完整 KKT 系統。
若 正定,且 的列獨立,系統就非奇異。更一般的情況,需要考慮等式零空間上的曲率,以及冗餘限制。偽逆可能給出一個解,但不應掩蓋背後的秩問題。
等式乘子會在可行仿射集合的法向方向,平衡目標梯度。它的符號不受限制。移除限制會同時改變可行集合與乘子的意義。
謹慎推導 LP 對偶
白話說。 對偶公式沒有一套通用符號。它的正負號來自實際使用的原問題慣例。
取 LP:在 下最小化 。把非負限制保留在定義域。拉格朗日函數為 。
對非負 取下確界,恰在 時有限。任一係數為負時,該座標可以無限增大,使下確界變成負無窮。
令 ,對偶變成
是符號不受限制的等式價格向量。對任何可行的原問題與對偶解,
間隙是非負原問題座標與非負對偶餘裕的內積。這是特別直觀的弱對偶表示。
改用原問題最大化,或反轉不等式,就會改變對偶符號。推導拉格朗日函數並檢查下界,比記憶不同表格更能防止錯誤。
從範數共軛建立擬合對偶
對偶可把參數懲罰變成殘差限制。考慮稀疏線性擬合,目標為 ,其中 固定、。引入殘差變數 與不受符號限制的等式乘子 :
其中 是參數向量, 的每個座標對應一筆觀測。對 最小化得到 ,殘差相關項的值為 。依 OPT 02 的範數共軛計算,對 最小化恰好在 時有限。因此對偶為
其中 是對偶變數,範數限制是對偶可行性。在最佳解處,它等於擬合殘差,而殘差與設計欄向量的相關量必須留在懲罰門檻內。這連起下界構造與稀疏擬合幾何 [1,第 5–6 章]。
對合成 、 與 ,原問題解為 ,對偶候選為 。兩者分別可行,目標值皆為 。上下界相等才證明擬合最佳;只看到零座標並不足夠。
敏感度與限制的價值
白話說。 在指定正則條件下,乘子衡量最佳成本如何隨限制變動。它的單位取決於限制的單位。
把不等式改為 ,等式改為 。以 表示最佳成本。若零擾動時強對偶成立且最佳乘子存在,
是右側擾動; 是原問題的最佳乘子。依此慣例,正 會放寬不等式。
此式給擾動最佳值一個全域仿射下界。若值函數在原問題處可微,它的導數就是 與 。
若不可微,乘子可能描述支撐斜率,而非唯一導數。大的乘子表示模型在這個局部方向敏感,不是普遍適用的物理重要性分數。
上界改變的純量例子
在 下最小化 。最佳點是 ,最佳值為
是允許的上界。在可微處,。一旦上界超過無限制目標,再放寬已沒有幫助,乘子就是零。
限制縮放會使乘子反向縮放。把 乘上正數,不會改變可行點,但會改變價格。比較敏感度時,應先處理單位與正規化。

程式:有限差分敏感度檢查
程式碼 · Python · 12 行
import numpy as np
value = lambda b: 0.5 * max(2 - b, 0)**2
b, eps = 1.2, 1e-5
multiplier = max(2 - b, 0)
derivative = (value(b + eps) - value(b - eps)) / (2 * eps)
assert np.isclose(derivative, -multiplier, atol=1e-8)
test_bounds = np.linspace(-1, 4, 50)
lower_bound = value(b) - multiplier * (test_bounds - b)
assert np.all([value(t) for t in test_bounds] >= lower_bound - 1e-12)
print("finite-difference derivative:", derivative)
print("negative multiplier:", -multiplier)從同一個下界推導敏感度
敏感度不等式不需要新原理。把原問題的最佳乘子放進擾動後的拉格朗日函數。對任何滿足 與 的點,
其中 是擾動向量,星號乘子對未擾動問題最佳。對擾動可行點取下確界,再使用原問題的強對偶,就得到前述值函數下界。負號來自在拉格朗日函數中扣除擾動後的右側。
對純量上界例子,在 時值為 、。把上界增加 ,其中 ,實際值變成 。實際下降為 ,乘子則預測一階下降 。下界預測 保持在實際值下方,差為 。
若限制改寫為 ,乘子變成 。限制對 的導數為 ,與乘子相乘仍預測斜率 。價格依賴表示方式,原成本變動的預測則一致 [1,第 5.6 節]。
不可行性憑證
白話說。 合法加權組合限制式,可以證明沒有任何選擇滿足它們。這比演算法沒找到可行點更有力。
對不等式 ,假設向量 滿足
定義不等式系統, 是非負憑證向量。若可行 存在,加權求和就會得到 ,產生矛盾。
這是 [1,第 5.8 節] 討論的擇一定理形式背後的幾何。它區分數學憑證與找不到解的搜尋。
在浮點數下,等式與嚴格負號需要相對尺度判斷。很小的轉置殘差,加上極小的負憑證值,可能受累積誤差影響而無法下結論。數值認證需要適當容許誤差分析。
程式:互不相容的純量不等式
限制為 與 。非負相加就能證明不可能。
程式碼 · Python · 10 行
import numpy as np
G = np.array([[1.], [-1.]])
h = np.array([0., -1.])
certificate = np.array([1., 1.])
assert np.all(certificate >= 0)
assert np.allclose(G.T @ certificate, 0)
assert h @ certificate < 0
print("transpose residual:", G.T @ certificate)
print("certificate contradiction:", h @ certificate)錐、鞍點與數值間隙
白話說。 從相應對偶錐選擇價格,就能把下界推理延伸到錐不等式。原問題與對偶解也可視為鞍點。
錐 的對偶錐定義為
遍歷原錐, 是價格向量。若限制寫成屬於 ,應選擇讓對偶錐內積產生正確下界的符號。正交象限、二階錐與半正定錐,在常用內積下都有熟悉的自對偶結構。
矩陣變數的內積使用跡:對對稱矩陣,。互補鬆弛因此是跡條件,不是逐元素相乘。
在適當原問題與對偶假設下,鞍點滿足
與 是最佳原問題與對偶點; 遍歷定義域,。左側在可行點最大化價格,右側在最佳價格下最小化決策。
實務上,只有兩點適當可行,且正確計算對偶值時,目標差才是有證明力的間隙。近似可行可能需要修正上下界。相對間隙應使用明確記錄的分母,在接近零或負目標值時仍有意義。
完整 LP 憑證與無效近似解
考慮在 、 下最小化 。原問題點 成本為一。依前面推導的 LP 對偶慣例,純量對偶變數 可行,因為 ,對偶值也是一。上下界相等,不需枚舉所有可行點就能證明最佳性。
對偶餘裕為 ,與原問題點的內積為零,直接呈現互補鬆弛。第二座標相對等式價格較昂貴,因此配置為零。此解釋來自係數與指定等式,不是一般特徵重要性結論。
現在取近似點 。它精確滿足等式,目標為看似更好的 0.98,卻違反非負性。與對偶值相減得到負數,不會推翻弱對偶,因為候選點在可行集合外。
只顯示等式殘差與目標的程式,可能因此回報誤導結果。應檢查所有邊界與錐限制,包括透過求解器變數邊界參數編碼、沒有放進明確矩陣列的限制。
裁切負座標得到 ,隨即違反等式。在這個特定例子,再正規化會得到 ;但裁切與正規化都不是耦合限制的通用有效修補。
近似殘差需要修正推理
對近似可行 LP 點對,代數目標差為
是原問題與對偶候選向量, 是對偶餘裕, 是原問題等式殘差。恆等式是精確代數;要得到非負且有證明力的間隙,還需要必要可行性。
若 、,但 ,殘差項可能正或負。小殘差乘上大價格,仍可能重要。因此,單靠絕對等式容許誤差,不是通用目標準確度保證。
若對偶餘裕逐分量只保證不小於 ,而 ,就有 。 衡量最壞負餘裕。大原問題向量可能放大微小對偶違反。
除非另外有所有可行原問題點的有效界,這個不等式不會把近似對偶值變成全域下界。無界可行集合尤其難以修正。不要把任意近似乘子描述為精確全域憑證。
應一起回報原問題殘差、負餘裕大小、乘子範數與目標差。若需要嚴格憑證,應依問題結構採有效修補、已驗證誤差上界,或更高精度檢查。
現代觀點
白話說。 現代大規模方法直接使用原問題與對偶結構,應用也越來越常對受限制解做微分。兩者都依賴同樣的憑證與正則性觀念。
Applegate 等人的 PDLP 報告 [2] 在 2025 年首次發布,2026 年修訂,討論實用原問題與對偶步驟及可行性修整的大規模 LP 計算。它在此的意義是:有用的系統要同時監測可行性與成本改善。若目標誤差小,卻帶著不可接受的限制違反,仍是另一種結果。
Pokutta 的 2024 年綜述 [3] 說明 Frank–Wolfe 方法的原問題與對偶收斂。對可行集合做線性最小化,能從支撐平面不等式建立一階間隙。這與下界憑證有關,但假設與計算方式不同於一般拉格朗日乘子對偶。
Agrawal 等人的可微凸最佳化層 [4],把結構化表示法與解的微分連起來。原論文發表於 2019 年,這裡把它作為現今最佳化層研究的基礎,不把它標成 2026 年新成果。退化或作用中集合改變附近,可微性與良好條件數可能失效;正確凸解不會自動保證良好的梯度。
目前問題包括超大規模的可靠憑證、限制由學習取得時的不確定性解讀、非唯一解的微分,以及精度和應用延遲的平衡。最佳化精度、模型有效性與學習泛化,應分別評估。
重點整理
- 可行原問題點給上界,可行對偶點給下界。
- 乘子符號取決於實際不等式慣例。
- 即使原問題非凸,對偶函數仍是凹的。
- 強對偶需要適當條件,或直接驗證相等的有效憑證。
- KKT 對可微凸問題是充分條件,必要性則需要正則性。
- 互補鬆弛與敏感度有明確的單向規則及符號。
- 數值殘差與間隙必須結合尺度、可行性解讀。
練習
- 在 下最小化 ,把 視為固定資料,推導對偶。
提示
先對純量最小化拉格朗日函數,再最大化乘子。
- 給一個在最佳點作用中、乘子卻為零的不等式。
提示
無限制最小化點的冗餘邊界即可。
- 保留非負變數在定義域中,推導 LP 對偶。
提示
要讓下確界有限,線性係數必須非負。
- 說明在 最小化 時,原點 KKT 駐點條件為何不能證明最佳性。
提示
原點是目標最大值。
- 建立一組非負加權矛盾,證明兩個純量不等式不可行。
提示
把低於必要下界的上界加起來。
- 把不等式乘上十,推導乘子的縮放,並說明原問題敏感度為何保持一致。
提示
保留拉格朗日函數中的乘積。
參考文獻
- Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004. 閱讀:第 5 章,涵蓋對偶、KKT、擾動、擇一定理與廣義不等式。 官方書頁,免費 PDF。
- David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue and Warren Schudy, “PDLP: A Practical First-Order Method for Large-Scale Linear Programming,” arXiv preprint, 2025, revised 2026. 已核對論文。
- Sebastian Pokutta, “The Frank-Wolfe Algorithm: A Short Introduction,” Jahresbericht der Deutschen Mathematiker-Vereinigung, 126, 2024. 開放綜述。
- Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond and J. Zico Kolter, “Differentiable Convex Optimization Layers,” NeurIPS, 2019. 官方出版頁。
檢查理解
本篇有 6 題練習。不看提示,你能解出來嗎?
前往練習 ↑下一篇 OPT 05・近似、統計估計與實驗設計 · 17 分鐘