完整搜尋頁面 →

OPT 04・對偶性、KKT 條件與證明憑證

最佳化進階16 分鐘更新於 2026年10月4日

先備知識:OPT 03・線性、二次、錐與幾何規劃

導覽:本頁與本系列: 導覽:本頁與本系列
用實驗理解本章 1 個互動實驗

調整候選點與乘數。只有滿足可行性,小差距才有意義。

你將學到

  • 從拉格朗日函數推導受限制最小化問題的下界。
  • 區分對偶可行性、弱對偶、強對偶與最佳值是否達到。
  • 寫出 KKT 條件,辨認它何時能證明全域最佳性。
  • 以正確的乘子符號解讀互補鬆弛與敏感度。
  • 建立簡單的不可行性憑證,並把對偶序關係延伸至錐。
  • 回報殘差與間隙,同時保留數值證據真正支持的範圍。

先看全貌

找到好的可行解,能給最佳成本一個上界。但是,我們怎麼知道其他地方沒有藏著更好的答案?對偶問題會產生下界。當上界與下界相遇,兩者就共同證明最佳值。

Boyd 與 Vandenberghe 的第 5 章 [1] 把這個想法連到幾何、支撐平面、乘子與數值演算法。即使已經會解原問題,對偶仍有用:它能驗證答案、說明有限資源的價值,並揭露另一種計算結構。

保證必須遵守符號與假設。任意選乘子算出的數值,不一定是下界。單靠很小的駐點殘差,也不是完整的證明。並非每個凸問題表示法都自動具備強對偶。

本章保留明確的定義域,使用能檢查精確答案的小例子推導。這套推理可以延伸至大問題,但實作細節與容許誤差仍是數值判斷的一部分。

從限制式到拉格朗日函數

白話說。 替每個不等式與等式附上一個價格,再最小化加上價格後的目標,而不直接強制這些限制。

考慮

min⁡x∈Df0(x)subject tofi(x)≤0,hj(x)=0.\min_{x\in D} f_0(x) \quad\text{subject to}\quad f_i(x)\leq0,\quad h_j(x)=0.

xx 是決策向量,DD 是最小化時保留的共同定義域,f0f_0 是目標,fif_i 是不等式,hjh_j 是等式。

拉格朗日函數為

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑j=1pνjhj(x).L(x,\lambda,\nu)= f_0(x)+\sum_{i=1}^m\lambda_if_i(x) +\sum_{j=1}^p\nu_jh_j(x).

λi\lambda_i 是不等式乘子,νj\nu_j 是等式乘子。若採用 fi≤0f_i\leq0 的慣例,就要求 λi≥0\lambda_i\geq0。等式乘子不限制符號,因為任何符號乘上可行點的等式殘差,結果都是零。

在可行點,不等式的貢獻非正,等式的貢獻為零。因此,當 λ\lambda 非負時,L(x,λ,ν)≤f0(x)L(x,\lambda,\nu)\leq f_0(x)。

把乘子稱為「懲罰」可能造成誤解。這裡的拉格朗日函數,並不是在無限制最小化時替違規加上一個很大的正成本。它的用途是建立一族下界,符號限制也由此而來。

定義對偶函數

g(λ,ν)=inf⁡x∈DL(x,λ,ν).g(\lambda,\nu)=\inf_{x\in D}L(x,\lambda,\nu).

gg 是拉格朗日對偶函數,輸入為乘子對。它對 DD 中的所有點取下確界,而非只看可行點。

對任一可行的 xx 與非負的 λ\lambda,

g(λ,ν)≤L(x,λ,ν)≤f0(x).g(\lambda,\nu)\leq L(x,\lambda,\nu)\leq f_0(x).

第一個不等式來自下確界,第二個來自原問題可行性與乘子符號。因此,gg 是原問題最佳值的下界。

若下確界為負無窮,這仍是正確、但沒有提供資訊的下界。想取得有用的憑證,必須選擇能產生適當有限對偶值的乘子。

為什麼對偶問題是凹的

白話說。 下界會隨價格改變。我們選擇能給最強下界的價格;這個最大化問題的目標是凹函數。

固定每個 xx 時,LL 對乘子都是仿射函數。仿射函數逐點取下確界,會得到凹函數。因此,即使原問題不是凸的,gg 仍是凹的。

對偶問題是

maximize⁡λ,νg(λ,ν)subject toλ≥0.\begin{aligned} \operatorname{maximize}_{\lambda,\nu}\quad &g(\lambda,\nu)\\ \text{subject to}\quad &\lambda\geq0. \end{aligned}

以 d∗d^* 表示對偶最佳值。弱對偶(weak duality)指出 d∗≤p∗d^*\leq p^*,其中 p∗p^* 是原問題最佳值。這個結果不要求凸性,只需要符號正確的下界構造。

最大化凹函數,符合一般凸最佳化問題的意義。但是,求對偶函數值本身可能很困難,因為它也許要求解一個難解的非凸最小化。「對偶是凹的」不等於自動擁有容易計算的查詢工具。

對偶與原問題的維度也不必相同。每個明確對偶化的限制式各產生一個變數。把部分限制留在 DD 中,而不加乘子,會改變寫出的對偶表示,但下界邏輯依然一致。

三行看懂凹性證明

對偶為凹,是因為取下確界後,混合價格的下界不會低於個別下確界的相應混合。令 z=(λ,ν)z=(\lambda,\nu) 收集乘子,取兩組容許價格 z1,z2z_1,z_2 與 θ∈[0,1]\theta\in[0,1]。拉格朗日函數對價格為仿射,因此

g(θz1+(1−θ)z2)=inf⁡x∈D[θL(x,z1)+(1−θ)L(x,z2)]≥θinf⁡x∈DL(x,z1)+(1−θ)inf⁡x∈DL(x,z2)=θg(z1)+(1−θ)g(z2).\begin{aligned} g(\theta z_1+(1-\theta)z_2) &=\inf_{x\in D}[\theta L(x,z_1)+(1-\theta)L(x,z_2)]\\ &\geq\theta\inf_{x\in D}L(x,z_1) +(1-\theta)\inf_{x\in D}L(x,z_2)\\ &=\theta g(z_1)+(1-\theta)g(z_2). \end{aligned}

其中 DD 是保留的原問題定義域、gg 是對偶函數;此比較考慮有限的對偶值。在同一 xx 處,每項都至少等於自己的下確界,因此得到中間不等式。這個步驟完全沒有假設原目標凸 [1]。

計算上必須區分:原問題非凸時,只找到 LL 的局部最小值,並不等於計算其下確界。該局部值可能高於 g(z)g(z),因而失去合法下界的意義。對偶凹性描述的是精確對偶函數,而不是任何自稱「對偶評估器」的近似程序。

完整的一維推導

白話說。 一個小例子就能看清價格、無限制最小化解與下界之間的關係。

在 x≤1x\leq1 下最小化 12(x−2)2\frac12(x-2)^2。xx 是純量。受限制最佳解是 x∗=1x^*=1,成本 p∗=1/2p^*=1/2。

使用乘子 λ≥0\lambda\geq0,

L(x,λ)=12(x−2)2+λ(x−1).L(x,\lambda)=\frac12(x-2)^2+\lambda(x-1).

拉格朗日函數的無限制最小化解滿足 x−2+λ=0x-2+\lambda=0,所以 xλ=2−λx_\lambda=2-\lambda。代回後得到

g(λ)=λ−12λ2.g(\lambda)=\lambda-\frac12\lambda^2.

xλx_\lambda 隨選擇的乘子而變,不一定是原問題可行點。對偶是一條凹拋物線,在 λ∗=1\lambda^*=1 達到最大值 g(λ∗)=1/2g(\lambda^*)=1/2。上界與下界於此相遇。

最佳乘子平衡了目標想增加 xx 的力量,以及作用中的上界限制。若 λ\lambda 太小,拉格朗日最小化解會落在允許區域之外;若太大,即使價格更高,下界反而更弱。

純量原問題在允許區間上的目標,以及碰到最佳值的凹對偶下界。
圖 1 — 在 x ≤ 1 下最小化 (x − 2)² / 2 的原創解析推導。可行原問題最佳解與最好的對偶下界,數值同為 1/2。

程式:驗證間隙與完整 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)表示 d∗=p∗d^*=p^*。它描述最佳值,不會自動保證最佳解存在。問題可能只有一串解逼近某個數值,卻沒有任何點真正達到它。

對具有仿射等式的凸原問題,一個標準充分條件是 Slater 條件 [1,第 5.2 節]:

∃x∈relint⁡D:fi(x)<0 for all i,Ax=b.\exists x\in\operatorname{relint}D: f_i(x)<0\ \text{for all }i,\qquad Ax=b.

DD 是共同函數定義域,relint⁡D\operatorname{relint}D 是它的相對內部,A,bA,b 定義仿射等式限制。意思是存在一個點,位於適當內部、嚴格滿足不等式,並且滿足等式。

在這些假設下,強對偶成立。若最佳值有限,對偶最佳值也會達到。原問題是否達到最佳值,仍可能需要另外討論存在性。

仿射不等式有較弱的精細條件,所以要求它們全部嚴格成立,可能比必要條件更強。沒找到 Slater 點,本身不會推翻強對偶;它只表示這個充分條件尚未證明。

並非每種表示法中,凸性本身就已經足夠。定義域可能退化,限制資格條件也可能不成立。與其說「凸問題的間隙永遠是零」,應說明採用哪個條件,或直接驗證一對有效且相等的憑證。

定義域限制也是對偶的一部分

目標若包含對數或倒數,它的定義域仍要保留在拉格朗日最小化中。把它當成所有實數上都有定義的函數,會悄悄改變問題。

另一種方式是使用延伸值函數,在定義域外給正無窮。數學上這很方便,但數值程式不應把意外產生的無效浮點值當成模型慣例。

錐表示法可以一致地選擇對偶化或保留定義域與錐限制。這會影響對偶公式與符號。應從實際原問題推導下界,不要直接搬用符號不相容的公式。

零間隙也可能沒有最佳乘子

限制資格條件失敗不一定造成正對偶間隙,卻可能使乘子最佳值無法達到。考慮在 x2≤0x^2\leq0 下最小化 xx,其中純量 x∈Rx\in\mathbb R。唯一可行點是零,所以 p∗=0p^*=0,而且沒有嚴格可行點。

拉格朗日函數為 L(x,λ)=x+λx2L(x,\lambda)=x+\lambda x^2。對 xx 最小化得到

g(λ)={−1/(4λ),λ>0,−∞,λ=0.g(\lambda)= \begin{cases} -1/(4\lambda),&\lambda>0,\\ -\infty,&\lambda=0. \end{cases}

其中 λ≥0\lambda\geq0 是二次限制的價格,gg 是其對偶下界。對正 λ\lambda,最小化點為 −1/(2λ)-1/(2\lambda)。當 λ\lambda 無界增大,g(λ)g(\lambda) 趨近零。因此 d∗=p∗=0d^*=p^*=0,但沒有任何有限乘子達到對偶最佳值。

在原問題解處,駐點條件要求 1+2λx=01+2\lambda x=0,卻變成 1=01=0。這種表示沒有 KKT 乘子。把等價限制改寫成等式 x=0x=0,就有乘子 ν=−1\nu=-1。可行決策不變,正則性與乘子描述卻改善。這正是 OPT 01 的隱藏等式與 OPT 07 的初始化值得重視的原因 [1]。

KKT 最佳性條件

白話說。 KKT 結合允許的原問題選擇、允許的價格、力的平衡,以及「有餘裕的限制不能帶正價格」這條規則。

對可微凸函數 f0,fif_0,f_i 與仿射等式 Ax=bAx=b,條件為

fi(x)≤0,Ax=b,λi≥0,λifi(x)=0,∇f0(x)+∑iλi∇fi(x)+A⊤ν=0.\begin{aligned} &f_i(x)\leq0,\qquad Ax=b,\\ &\lambda_i\geq0,\\ &\lambda_if_i(x)=0,\\ &\nabla f_0(x)+\sum_i\lambda_i\nabla f_i(x)+A^\top\nu=0. \end{aligned}

xx 是原問題候選點,λ\lambda 是不等式乘子,ν\nu 是等式乘子。最後一列是拉格朗日駐點條件。整組稱為 Karush–Kuhn–Tucker 條件。

對這個凸且可微的問題,全部條件成立,就足以證明原問題與對偶最佳性。非負乘子使拉格朗日函數對 xx 為凸;駐點條件使 xx 成為它的全域最小化解;可行性與互補鬆弛則使拉格朗日值等於目標值。

在適當資格條件,例如 Slater 條件下,最佳點也會存在滿足 KKT 的乘子。這提供必要性,以及前述充分性。應把兩個邏輯方向分清楚。

非凸問題的拉格朗日駐點,可能是對 xx 的局部最大值或鞍點。KKT 在正則條件下可能必要,通常卻不能證明全域最佳性。凹二次函數的內部駐點就是簡單反例。

互補鬆弛提供單向資訊

若 fi(x)<0f_i(x)<0,互補鬆弛會迫使 λi=0\lambda_i=0。若 λi>0\lambda_i>0,限制必須作用中:fi(x)=0f_i(x)=0。

作用中的限制仍可能有零乘子。退化或冗餘限制可能使價格不唯一。因此,「作用中」與「正價格」不能互換。

在平滑受限制最佳點,負目標梯度會落在作用中限制法向量與等式法向量、搭配適當符號形成的組合裡。這解釋了駐點條件的幾何意義:可行下降方向無法降低目標。

數值上的接近作用中,依賴容許誤差。很小的餘裕搭配很小的乘子,可能難以做離散分類。若區別重要,應回報實際數值,避免硬給確定的作用中或非作用中標籤。

等式限制二次問題

白話說。 二次目標搭配線性等式時,KKT 條件形成一個線性系統,揭露後續受限制演算法需要的代數。

在 Ax=bAx=b 下,目標為 12x⊤Qx+c⊤x\frac12x^\top Qx+c^\top x,則

[QA⊤A0][xν]=[−cb].\begin{bmatrix}Q&A^\top\\A&0\end{bmatrix} \begin{bmatrix}x\\\nu\end{bmatrix} =\begin{bmatrix}-c\\b\end{bmatrix}.

QQ 是對稱半正定矩陣,cc 是目標係數向量,AA 是等式矩陣,bb 是目標值,ν\nu 是等式乘子。

即使最佳化問題是凸的,這個區塊矩陣通常仍是不定矩陣。要求正定矩陣的求解器,不能直接套用到完整 KKT 系統。

若 QQ 正定,且 AA 的列獨立,系統就非奇異。更一般的情況,需要考慮等式零空間上的曲率,以及冗餘限制。偽逆可能給出一個解,但不應掩蓋背後的秩問題。

等式乘子會在可行仿射集合的法向方向,平衡目標梯度。它的符號不受限制。移除限制會同時改變可行集合與乘子的意義。

謹慎推導 LP 對偶

白話說。 對偶公式沒有一套通用符號。它的正負號來自實際使用的原問題慣例。

取 LP:在 Ax=b, x≥0Ax=b,\ x\geq0 下最小化 c⊤xc^\top x。把非負限制保留在定義域。拉格朗日函數為 c⊤x+ν⊤(Ax−b)c^\top x+\nu^\top(Ax-b)。

對非負 xx 取下確界,恰在 c+A⊤ν≥0c+A^\top\nu\geq0 時有限。任一係數為負時,該座標可以無限增大,使下確界變成負無窮。

令 y=−νy=-\nu,對偶變成

max⁡yb⊤ysubject toA⊤y≤c.\max_y b^\top y\quad\text{subject to}\quad A^\top y\leq c.

yy 是符號不受限制的等式價格向量。對任何可行的原問題與對偶解,

c⊤x−b⊤y=x⊤(c−A⊤y)≥0.c^\top x-b^\top y=x^\top(c-A^\top y)\geq0.

間隙是非負原問題座標與非負對偶餘裕的內積。這是特別直觀的弱對偶表示。

改用原問題最大化,或反轉不等式,就會改變對偶符號。推導拉格朗日函數並檢查下界,比記憶不同表格更能防止錯誤。

從範數共軛建立擬合對偶

對偶可把參數懲罰變成殘差限制。考慮稀疏線性擬合,目標為 12∥Ax−b∥22+λ∥x∥1\frac12\|Ax-b\|_2^2+\lambda\|x\|_1,其中 A,bA,b 固定、λ>0\lambda>0。引入殘差變數 r=Ax−br=Ax-b 與不受符號限制的等式乘子 yy:

L(x,r,y)=12∥r∥22+λ∥x∥1+y⊤(Ax−b−r).L(x,r,y)=\frac12\|r\|_2^2+\lambda\|x\|_1 +y^\top(Ax-b-r).

其中 xx 是參數向量,yy 的每個座標對應一筆觀測。對 rr 最小化得到 r=yr=y,殘差相關項的值為 −∥y∥22/2-\|y\|_2^2/2。依 OPT 02 的範數共軛計算,對 xx 最小化恰好在 ∥A⊤y∥∞≤λ\|A^\top y\|_\infty\leq\lambda 時有限。因此對偶為

maximize⁡y−12∥y∥22−b⊤ysubject to∥A⊤y∥∞≤λ.\operatorname{maximize}_y\quad-\frac12\|y\|_2^2-b^\top y \qquad\text{subject to}\quad\|A^\top y\|_\infty\leq\lambda.

其中 yy 是對偶變數,範數限制是對偶可行性。在最佳解處,它等於擬合殘差,而殘差與設計欄向量的相關量必須留在懲罰門檻內。這連起下界構造與稀疏擬合幾何 [1,第 5–6 章]。

對合成 A=IA=I、b=(2,−0.3,0.1)b=(2,-0.3,0.1) 與 λ=0.4\lambda=0.4,原問題解為 x=(1.6,0,0)x=(1.6,0,0),對偶候選為 y=x−b=(−0.4,0.3,−0.1)y=x-b=(-0.4,0.3,-0.1)。兩者分別可行,目標值皆為 0.770.77。上下界相等才證明擬合最佳;只看到零座標並不足夠。

敏感度與限制的價值

白話說。 在指定正則條件下,乘子衡量最佳成本如何隨限制變動。它的單位取決於限制的單位。

把不等式改為 fi(x)≤uif_i(x)\leq u_i,等式改為 Ax−b=vAx-b=v。以 p∗(u,v)p^*(u,v) 表示最佳成本。若零擾動時強對偶成立且最佳乘子存在,

p∗(u,v)≥p∗(0,0)−λ∗⊤u−ν∗⊤v.p^*(u,v)\geq p^*(0,0)-\lambda^{*\top}u-\nu^{*\top}v.

u,vu,v 是右側擾動;λ∗,ν∗\lambda^*,\nu^* 是原問題的最佳乘子。依此慣例,正 uiu_i 會放寬不等式。

此式給擾動最佳值一個全域仿射下界。若值函數在原問題處可微,它的導數就是 −λ∗-\lambda^* 與 −ν∗-\nu^*。

若不可微,乘子可能描述支撐斜率,而非唯一導數。大的乘子表示模型在這個局部方向敏感,不是普遍適用的物理重要性分數。

上界改變的純量例子

在 x≤bx\leq b 下最小化 12(x−2)2\frac12(x-2)^2。最佳點是 min⁡(2,b)\min(2,b),最佳值為

p∗(b)=12max⁡(2−b,0)2,λ∗(b)=max⁡(2−b,0).p^*(b)=\frac12\max(2-b,0)^2,\qquad \lambda^*(b)=\max(2-b,0).

bb 是允許的上界。在可微處,dp∗/db=−λ∗(b)dp^*/db=-\lambda^*(b)。一旦上界超過無限制目標,再放寬已沒有幫助,乘子就是零。

限制縮放會使乘子反向縮放。把 x−b≤0x-b\leq0 乘上正數,不會改變可行點,但會改變價格。比較敏感度時,應先處理單位與正規化。

上界改變時的最佳值,以及對應非負乘子。
圖 2 — 原創解析敏感度例子。限制仍有效時,放寬上界會降低成本;允許無限制目標之後,最佳值與乘子都為零。

程式:有限差分敏感度檢查

程式碼 · 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)

從同一個下界推導敏感度

敏感度不等式不需要新原理。把原問題的最佳乘子放進擾動後的拉格朗日函數。對任何滿足 fi(x)≤uif_i(x)\leq u_i 與 hj(x)=vjh_j(x)=v_j 的點,

f0(x)≥g(λ∗,ν∗)−λ∗⊤u−ν∗⊤v.f_0(x)\geq g(\lambda^*,\nu^*) -{\lambda^*}^\top u-{\nu^*}^\top v.

其中 u,vu,v 是擾動向量,星號乘子對未擾動問題最佳。對擾動可行點取下確界,再使用原問題的強對偶,就得到前述值函數下界。負號來自在拉格朗日函數中扣除擾動後的右側。

對純量上界例子,在 b=1b=1 時值為 1/21/2、λ∗=1\lambda^*=1。把上界增加 δ\delta,其中 0<δ<10\lt \delta\lt 1,實際值變成 (1−δ)2/2(1-\delta)^2/2。實際下降為 δ−δ2/2\delta-\delta^2/2,乘子則預測一階下降 δ\delta。下界預測 1/2−δ1/2-\delta 保持在實際值下方,差為 δ2/2\delta^2/2。

若限制改寫為 10(x−b)≤010(x-b)\leq0,乘子變成 1/101/10。限制對 bb 的導數為 −10-10,與乘子相乘仍預測斜率 −1-1。價格依賴表示方式,原成本變動的預測則一致 [1,第 5.6 節]。

不可行性憑證

白話說。 合法加權組合限制式,可以證明沒有任何選擇滿足它們。這比演算法沒找到可行點更有力。

對不等式 Gx≤hGx\leq h,假設向量 yy 滿足

y≥0,G⊤y=0,h⊤y<0.y\geq0,\qquad G^\top y=0,\qquad h^\top y<0.

G,hG,h 定義不等式系統,yy 是非負憑證向量。若可行 xx 存在,加權求和就會得到 0=y⊤Gx≤y⊤h<00=y^\top Gx\leq y^\top h<0,產生矛盾。

這是 [1,第 5.8 節] 討論的擇一定理形式背後的幾何。它區分數學憑證與找不到解的搜尋。

在浮點數下,等式與嚴格負號需要相對尺度判斷。很小的轉置殘差,加上極小的負憑證值,可能受累積誤差影響而無法下結論。數值認證需要適當容許誤差分析。

程式:互不相容的純量不等式

限制為 x≤0x\leq0 與 x≥1x\geq1。非負相加就能證明不可能。

程式碼 · 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)

錐、鞍點與數值間隙

白話說。 從相應對偶錐選擇價格,就能把下界推理延伸到錐不等式。原問題與對偶解也可視為鞍點。

錐 KK 的對偶錐定義為

K∗={y:y⊤z≥0 for every z∈K}.K^*=\{y:y^\top z\geq0\ \text{for every }z\in K\}.

zz 遍歷原錐,yy 是價格向量。若限制寫成屬於 KK,應選擇讓對偶錐內積產生正確下界的符號。正交象限、二階錐與半正定錐,在常用內積下都有熟悉的自對偶結構。

矩陣變數的內積使用跡:對對稱矩陣,⟨X,Y⟩=tr⁡(XY)\langle X,Y\rangle=\operatorname{tr}(XY)。互補鬆弛因此是跡條件,不是逐元素相乘。

在適當原問題與對偶假設下,鞍點滿足

L(x∗,λ,ν)≤L(x∗,λ∗,ν∗)≤L(x,λ∗,ν∗).L(x^*,\lambda,\nu)\leq L(x^*,\lambda^*,\nu^*) \leq L(x,\lambda^*,\nu^*).

x∗x^* 與 (λ∗,ν∗)(\lambda^*,\nu^*) 是最佳原問題與對偶點;xx 遍歷定義域,λ≥0\lambda\geq0。左側在可行點最大化價格,右側在最佳價格下最小化決策。

實務上,只有兩點適當可行,且正確計算對偶值時,目標差才是有證明力的間隙。近似可行可能需要修正上下界。相對間隙應使用明確記錄的分母,在接近零或負目標值時仍有意義。

完整 LP 憑證與無效近似解

考慮在 x1+x2=1x_1+x_2=1、x≥0x\geq0 下最小化 x1+3x2x_1+3x_2。原問題點 (1,0)(1,0) 成本為一。依前面推導的 LP 對偶慣例,純量對偶變數 y=1y=1 可行,因為 (y,y)≤(1,3)(y,y)\leq(1,3),對偶值也是一。上下界相等,不需枚舉所有可行點就能證明最佳性。

對偶餘裕為 (0,2)(0,2),與原問題點的內積為零,直接呈現互補鬆弛。第二座標相對等式價格較昂貴,因此配置為零。此解釋來自係數與指定等式,不是一般特徵重要性結論。

現在取近似點 (1.01,−0.01)(1.01,-0.01)。它精確滿足等式,目標為看似更好的 0.98,卻違反非負性。與對偶值相減得到負數,不會推翻弱對偶,因為候選點在可行集合外。

只顯示等式殘差與目標的程式,可能因此回報誤導結果。應檢查所有邊界與錐限制,包括透過求解器變數邊界參數編碼、沒有放進明確矩陣列的限制。

裁切負座標得到 (1.01,0)(1.01,0),隨即違反等式。在這個特定例子,再正規化會得到 (1,0)(1,0);但裁切與正規化都不是耦合限制的通用有效修補。

近似殘差需要修正推理

對近似可行 LP 點對,代數目標差為

c⊤x−b⊤y=x⊤s+y⊤r,s=c−A⊤y,r=Ax−b.c^\top x-b^\top y=x^\top s+y^\top r,\qquad s=c-A^\top y,\quad r=Ax-b.

x,yx,y 是原問題與對偶候選向量,ss 是對偶餘裕,rr 是原問題等式殘差。恆等式是精確代數;要得到非負且有證明力的間隙,還需要必要可行性。

若 x≥0x\geq0、s≥0s\geq0,但 r≠0r\ne0,殘差項可能正或負。小殘差乘上大價格,仍可能重要。因此,單靠絕對等式容許誤差,不是通用目標準確度保證。

若對偶餘裕逐分量只保證不小於 −ε-\varepsilon,而 x≥0x\geq0,就有 x⊤s≥−ε∥x∥1x^\top s\geq-\varepsilon\|x\|_1。ε≥0\varepsilon\geq0 衡量最壞負餘裕。大原問題向量可能放大微小對偶違反。

除非另外有所有可行原問題點的有效界,這個不等式不會把近似對偶值變成全域下界。無界可行集合尤其難以修正。不要把任意近似乘子描述為精確全域憑證。

應一起回報原問題殘差、負餘裕大小、乘子範數與目標差。若需要嚴格憑證,應依問題結構採有效修補、已驗證誤差上界,或更高精度檢查。

現代觀點

白話說。 現代大規模方法直接使用原問題與對偶結構,應用也越來越常對受限制解做微分。兩者都依賴同樣的憑證與正則性觀念。

Applegate 等人的 PDLP 報告 [2] 在 2025 年首次發布,2026 年修訂,討論實用原問題與對偶步驟及可行性修整的大規模 LP 計算。它在此的意義是:有用的系統要同時監測可行性與成本改善。若目標誤差小,卻帶著不可接受的限制違反,仍是另一種結果。

Pokutta 的 2024 年綜述 [3] 說明 Frank–Wolfe 方法的原問題與對偶收斂。對可行集合做線性最小化,能從支撐平面不等式建立一階間隙。這與下界憑證有關,但假設與計算方式不同於一般拉格朗日乘子對偶。

Agrawal 等人的可微凸最佳化層 [4],把結構化表示法與解的微分連起來。原論文發表於 2019 年,這裡把它作為現今最佳化層研究的基礎,不把它標成 2026 年新成果。退化或作用中集合改變附近,可微性與良好條件數可能失效;正確凸解不會自動保證良好的梯度。

目前問題包括超大規模的可靠憑證、限制由學習取得時的不確定性解讀、非唯一解的微分,以及精度和應用延遲的平衡。最佳化精度、模型有效性與學習泛化,應分別評估。

重點整理

  • 可行原問題點給上界,可行對偶點給下界。
  • 乘子符號取決於實際不等式慣例。
  • 即使原問題非凸,對偶函數仍是凹的。
  • 強對偶需要適當條件,或直接驗證相等的有效憑證。
  • KKT 對可微凸問題是充分條件,必要性則需要正則性。
  • 互補鬆弛與敏感度有明確的單向規則及符號。
  • 數值殘差與間隙必須結合尺度、可行性解讀。

練習

  1. 在 x≤bx\leq b 下最小化 12(x−a)2\frac12(x-a)^2,把 a,ba,b 視為固定資料,推導對偶。
提示

先對純量最小化拉格朗日函數,再最大化乘子。

  1. 給一個在最佳點作用中、乘子卻為零的不等式。
提示

無限制最小化點的冗餘邊界即可。

  1. 保留非負變數在定義域中,推導 LP 對偶。
提示

要讓下確界有限,線性係數必須非負。

  1. 說明在 [−1,1][-1,1] 最小化 −x2-x^2 時,原點 KKT 駐點條件為何不能證明最佳性。
提示

原點是目標最大值。

  1. 建立一組非負加權矛盾,證明兩個純量不等式不可行。
提示

把低於必要下界的上界加起來。

  1. 把不等式乘上十,推導乘子的縮放,並說明原問題敏感度為何保持一致。
提示

保留拉格朗日函數中的乘積。

參考文獻

  1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004. 閱讀:第 5 章,涵蓋對偶、KKT、擾動、擇一定理與廣義不等式。 官方書頁,免費 PDF。
  2. 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. 已核對論文。
  3. Sebastian Pokutta, “The Frank-Wolfe Algorithm: A Short Introduction,” Jahresbericht der Deutschen Mathematiker-Vereinigung, 126, 2024. 開放綜述。
  4. Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond and J. Zico Kolter, “Differentiable Convex Optimization Layers,” NeurIPS, 2019. 官方出版頁。

檢查理解

本篇有 6 題練習。不看提示,你能解出來嗎?

前往練習 ↑

下一篇 OPT 05・近似、統計估計與實驗設計 · 17 分鐘