完整搜尋頁面 →

OPT 07・等式限制與內點法

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

先備知識:OPT 06・梯度下降、牛頓步驟與數值可靠性

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

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

你將學到

  • 把牛頓法延伸到含仿射等式的凸目標函數。
  • 推導對數障礙函數、中心路徑及其對偶間隙。
  • 實作具有明確線搜尋的小型可行障礙法求解器。
  • 區分可行、嚴格可行與不可行的限制系統。
  • 解讀原始/對偶殘差、互補性與不可行性憑證。
  • 依數值需求比較現代內點法與一階求解器。

先看全貌

限制式說明解可以做什麼。求解器改善目標時不能忽略它們。等式把每個容許步驟限制在較低維度的空間;不等式則產生必須處理的邊界。內點法(interior-point method)透過一系列問題逼近有用的邊界解,而迭代點保持在邊界內側。

本章搭配 Boyd 與 Vandenberghe 第 10–11 章 [1]:第 10 章處理等式限制下的最小化,第 11 章發展障礙函數、中心路徑、初始化與原始/對偶方法。先讀梯度與牛頓法;憑證看不懂時,回到對偶性與最適條件。Bubeck 的演算法專論 [2] 提供複雜度與求解器家族的另一種觀點。

範例使用低維度合成問題,讓每項主張都能獨立查核。程式是附有斷言、假設透明的教學實作。正式錐規劃求解器還需要尺度調整、稀疏矩陣分解、數值正則化、停止政策與不可行性處理;理解小問題有助於理解這些工程選擇。

1. 等式限制改變容許的方向

目標下降時,仿射等式仍須成立。目前點若滿足 Ax=bAx=b,步驟 Δx\Delta x 保持可行的充分必要條件是 AΔx=0A\Delta x=0。先看幾何再看矩陣:容許的步驟位於等式矩陣的零空間。

考慮凸問題:

minimize⁡xf(x)subject to⁡Ax=b.\begin{aligned} \operatorname{minimize}_x\quad &f(x)\\ \operatorname{subject\ to}\quad &Ax=b. \end{aligned}

其中 x∈Rnx\in\mathbb R^n 是變數,ff 是二次可微的凸目標函數,A∈Rp×nA\in\mathbb R^{p\times n} 與 b∈Rpb\in\mathbb R^p 是固定資料。先假設 AA 各列獨立,且等式系統有解。拉格朗日乘子 ν∈Rp\nu\in\mathbb R^p 表示等式限制的影響。

在可行迭代點,沿可行方向最小化二次近似,得到牛頓系統:

[HA⊤A0][Δxw]=−[∇f(x)0].\begin{bmatrix}H&A^\top\\A&0\end{bmatrix} \begin{bmatrix}\Delta x\\w\end{bmatrix} =-\begin{bmatrix}\nabla f(x)\\0\end{bmatrix}.

其中 H=∇2f(x)H=\nabla^2 f(x) 是 Hessian 矩陣,Δx\Delta x 是原始變數的候選步驟,ww 是局部二次子問題的等式乘子,零區塊大小為 p×pp\times p。第二個區塊方程強制 AΔx=0A\Delta x=0。ww 解的是局部模型,不一定等於另一個持續維護的乘子估計之增量。

Hessian 只須沿非零可行方向具有正曲率,受限二次模型就能表現良好;被等式排除的方向不必有正曲率。因此完整 Hessian 可能奇異,但受限最小解仍唯一。判斷奇異性是否代表多解前,先檢查真正的可行子空間。

區塊矩陣稱為 Karush–Kuhn–Tucker(KKT)矩陣 [1]。即使 HH 正定,整個矩陣通常仍是不定矩陣。不要因原目標凸,就對整個矩陣使用只適合正定矩陣的分解。其結構同時表達原始與對偶方程;小型稠密範例使用一般線性求解即可。

另一種方法是消去等式。取一個可行點 x0x_0,以及欄向量張成 AA 零空間的矩陣 FF,寫成 x=x0+Fzx=x_0+Fz,其中 z∈Rn−pz\in\mathbb R^{n-p} 是降維變數,再解 zz 的無限制問題。消去法能簡化小問題,卻可能破壞大問題的稀疏性。兩者幾何相同,計算表示決定成本。

限制子空間曲率與區塊消去

Hessian 奇異不代表受限步驟不明確。在 x2=3x_2=3 下最小化 f(x)=x12/2f(x)=x_1^2/2。Hessian 為 diag⁡(1,0)\operatorname{diag}(1,0),但可行方向只能改變 x1x_1。唯一最小解為 (0,3)(0,3):等式恰好移除平坦方向。

一般而言,令 FF 的獨立欄向量張成 AA 的零空間。縮減 Hessian 為 F⊤HFF^\top HF。這個較小矩陣正定,就能讓可行方向上的局部二次模型有唯一最小解,即使 HH 奇異也一樣。其中 HH 是目前 Hessian、AA 是滿列秩的等式矩陣 [1,第 10 章]。

若 HH 本身正定,也可消去原問題方向來推導 KKT 步驟。寫 g=∇f(x)g=\nabla f(x),利用第一個區塊方程:

Δx=−H−1(g+A⊤w),(AH−1A⊤)w=−AH−1g.\begin{aligned} \Delta x&=-H^{-1}(g+A^\top w),\\ (AH^{-1}A^\top)w&=-AH^{-1}g. \end{aligned}

其中 Δx\Delta x 是步驟、ww 是局部等式乘子。把第一行代入 AΔx=0A\Delta x=0 即得第二行。AA 各列獨立時,這個較小矩陣為正定:對非零 vv,二次型為 (A⊤v)⊤H−1(A⊤v)>0(A^\top v)^\top H^{-1}(A^\top v)>0。

這些方程解釋區塊求解,但反矩陣符號只是代數表示。實作應透過 HH 的線性求解計算乘積,再比較消去法與直接稀疏 KKT 分解的成本。前面的奇異例子仍能使用零空間表示,卻不能使用這種完整 Hessian 消去。

2. 帶有可查核憑證的受限二次問題

二次目標讓 KKT 方程成為精確條件而非近似。區塊系統產生候選解;檢查等式可行性與駐點條件,才能判斷候選解是否構成這個凸問題的最適性憑證。

對於:

f(x)=12x⊤Qx+c⊤x,f(x)=\tfrac12x^\top Qx+c^\top x,

Q∈Rn×nQ\in\mathbb R^{n\times n} 是對稱半正定矩陣,c∈Rnc\in\mathbb R^n 是固定向量,xx 是變數。最適配對 (x∗,ν∗)(x^*,\nu^*) 滿足 Qx∗+c+A⊤ν∗=0Qx^*+c+A^\top\nu^*=0 及 Ax∗=bAx^*=b;星號代表最適值。對可行凸二次問題,這些方程足以保證最適;唯一性還需要可行方向的額外曲率。

程式碼 · Python · 17 行
import numpy as np

Q = np.diag([2.0, 4.0])
c = np.array([-2.0, -1.0])
A = np.array([[1.0, 1.0]])
b = np.array([1.0])
K = np.block([[Q, A.T], [A, np.zeros((1, 1))]])
solution = np.linalg.solve(K, np.concatenate([-c, b]))
x, nu = solution[:2], solution[2:]
primal = A @ x - b
dual = Q @ x + c + A.T @ nu
print("Primal solution:", x)
print("Equality multiplier:", nu)
print("Residual norms:", np.linalg.norm(primal), np.linalg.norm(dual))
assert np.allclose(x, [5/6, 1/6])
assert np.linalg.norm(primal) < 1e-12
assert np.linalg.norm(dual) < 1e-12

兩個座標相加為一。無限制最小解的座標則為一與四分之一,違反總量限制。乘子修正駐點方程以反映限制。目標值小不足以證明這項修正;殘差檢查把它明確表達出來。

殘差依賴單位。把等式乘上很大的常數,不改變可行集合,卻改變原始殘差與乘子的尺度。回報原限制的單位及尺度,並用有意義的容許誤差比較殘差。求解器內部的正規化停止條件須轉回應用的量測單位。

不要為了求解而明確計算矩陣反矩陣。線性求解較直接,通常也較穩定。重複求解時,矩陣結構允許才能重用分解。更新線性項與更新 Hessian 或限制矩陣不同;規劃暖啟動與快取時要區分。

非線性目標需要重新計算局部曲率,並採可行線搜尋。完整牛頓步驟即使保持等式,也可能離開目標函數定義域。對數與正定矩陣變數不是處處有定義;等式方程本身無法保護這些定義域。

3. 不等式轉成平滑的內部問題

障礙函數接近邊界時無限增大,只在嚴格可行點有限。如此平滑的受限牛頓法就能把不等式透過目標處理,同時保留明確的仿射等式。

考慮凸不等式 fi(x)≤0f_i(x)\leq0,i=1,…,mi=1,\ldots,m,以及 Ax=bAx=b,定義:

ϕ(x)=−∑i=1mlog⁡(−fi(x)),Ft(x)=tf0(x)+ϕ(x).\phi(x)=-\sum_{i=1}^{m}\log(-f_i(x)),\qquad F_t(x)=t f_0(x)+\phi(x).

其中 f0f_0 是原凸目標,fif_i 是各凸不等式函數,mm 是純量不等式數目,ϕ\phi 是對數障礙函數,t>0t\gt0 控制原目標的相對重要性。定義域要求每個 fi(x)<0f_i(x)\lt0;障礙問題在 Ax=bAx=b 下最小化 FtF_t。

限制函數應以一致單位表示,或取對數前除以正的參考尺度。正數縮放只增加障礙函數的常數項,不改變最小解,但有限精度計算仍可能受影響。數學上的不變性不能當成忽略數值尺度的理由。

二次可微不等式的障礙項,梯度為 ∇fi(x)/(−fi(x))\nabla f_i(x)/(-f_i(x)),Hessian 為:

∇fi(x)∇fi(x)⊤fi(x)2+∇2fi(x)−fi(x).\frac{\nabla f_i(x)\nabla f_i(x)^\top}{f_i(x)^2} +\frac{\nabla^2f_i(x)}{-f_i(x)}.

其中 ∇fi\nabla f_i 是梯度欄向量,∇2fi\nabla^2 f_i 是 Hessian。因 fif_i 凸,嚴格可行定義域內兩項皆半正定。式子也顯示接近活躍邊界、−fi(x)-f_i(x) 變小時,曲率迅速增加。

限制的表示影響路徑。重複同一限制會重複其障礙項,因此有限 tt 的近似問題不同,雖然精確可行集合相同。等價限制集合不一定產生相同中間迭代點;標準化與尺度調整是能觀察效果的演算法選擇。

障礙法不能從邊界開始。非負變數起點若為零,−log⁡x-\log x 無定義。自由變數可以用嚴格正值初始化;若等式強制變數為零,則需要重寫問題。任意給限制加一個正偏移會改變問題,不能當作無害的實作修正。

4. 中心路徑連接內點與對偶界限

對每個障礙權重準確求解內部問題,其最小解形成中心路徑(central path)。增加權重會減弱障礙相對原目標的影響,讓解接近可能位於邊界的受限最小解。

令 x(t)x(t) 在 Ax=bAx=b 下最小化 FtF_t,定義:

λi(t)=1t[−fi(x(t))],ν(t)=w(t)t.\lambda_i(t)=\frac{1}{t[-f_i(x(t))]},\qquad \nu(t)=\frac{w(t)}{t}.

其中 λi(t)>0\lambda_i(t)\gt0 是不等式乘子,w(t)w(t) 是縮放障礙問題的等式乘子,ν(t)\nu(t) 則是原目標尺度的乘子。tt、fif_i 與 x(t)x(t) 的定義同前。

障礙駐點條件成為原拉格朗日函數的駐點條件;互補性改為 λi(t)[−fi(x(t))]=1/t\lambda_i(t)[-f_i(x(t))]=1/t。各純量不等式貢獻相同的正乘積。真正最適點的互補鬆弛要求這些乘積為零;tt 增加時,障礙路徑逐漸逼近這項條件。

在完全置中且滿足所述假設的點,其原始/對偶間隙為:

f0(x(t))−g(λ(t),ν(t))=mt.f_0(x(t))-g(\lambda(t),\nu(t))=\frac{m}{t}.

其中 gg 是拉格朗日對偶函數,對對偶可行乘子提供最適目標的下界。原始值是上界,對偶值是下界,間隙因此限制目標次最適誤差。這是關於所建立凸問題的敘述,不保證模型符合應用。

等式需要精確置中及有效的對偶構造。駐點殘差很大的數值迭代點,不能只印出 m/tm/t 就宣稱得到精確間隙。以理論值規劃障礙排程,再檢查真實殘差,能計算時也求出真正的對偶下界。如此才不會把外迴圈計數當作憑證。

外層障礙法交替進行兩件事:解固定 tt 的內部問題,再增加 tt。以前一解作下一起點通常有幫助,因最小解往往相近;但 tt 一次改太多會使置中昂貴。依置中實際成本選擇增幅,而不是假設外層迭代越少,總計算就越少。

間隙 m/tm/t 真正從哪裡來

中心路徑間隙是明確價格乘以明確鬆弛量的總和。在精確置中的點,把障礙問題駐點方程除以 tt:

∇f0(x(t))+∑i∇fi(x(t))t[−fi(x(t))]+A⊤w(t)t=0.\nabla f_0(x(t))+ \sum_i\frac{\nabla f_i(x(t))}{t[-f_i(x(t))]} +A^\top\frac{w(t)}t=0.

其中 x(t)x(t) 最小化障礙問題、w(t)w(t) 是其等式乘子、f0,fif_0,f_i 是原目標與不等式、t>0t>0 是障礙權重。代入已定義的 λi(t)=1/[t(−fi(x(t)))]\lambda_i(t)=1/[t(-f_i(x(t)))] 與 ν(t)=w(t)/t\nu(t)=w(t)/t,便恰好得到原拉格朗日函數的駐點方程。

原函數凸且不等式乘子非負,因此拉格朗日函數對 xx 凸。駐點條件使 x(t)x(t) 成為其全域最小解,所以在此點評估 LL 確實算出對偶函數。等式可行性消去等式項,得到

g(λ(t),ν(t))=f0(x(t))+∑iλi(t)fi(x(t))=f0(x(t))−mt.g(\lambda(t),\nu(t)) =f_0(x(t))+\sum_i\lambda_i(t)f_i(x(t)) =f_0(x(t))-\frac mt.

其中 gg 是對偶函數、mm 是純量不等式數量。從可行原問題目標減去這個下界,即得間隙。中心點通常不是原最佳解:它在目標改善與正鬆弛量間取捨,但其乘子已提供憑證,而且誤差隨障礙減弱而下降 [1,第 11.2 節]。

若希望理論間隙至多為 ε>0\varepsilon>0,選 t≥m/εt\geq m/\varepsilon,再把置中問題解得足夠準確。選擇 tt 提供目標;駐點求解才是使用公式的依據。只增加 tt 卻不置中,就漏掉證明的關鍵等式。

5. 完整的一維障礙法實驗

使用真正最小解容易查核的二次問題:在 0≤x≤10\leq x\leq1 下最小化 12(x−2)2\tfrac12(x-2)^2。無限制最小點是二,最近的容許點是一,目標值為二分之一。障礙解嚴格位於零與一之間,逐漸接近上端點。

此例為:

Ft(x)=t2(x−2)2−log⁡x−log⁡(1−x).F_t(x)=\tfrac{t}{2}(x-2)^2-\log x-\log(1-x).

其中 x∈(0,1)x\in(0,1) 是純量變數,t>0t\gt0 是目標權重。一、二階導數為 Ft′(x)=t(x−2)−1/x+1/(1−x)F_t'(x)=t(x-2)-1/x+1/(1-x) 與 Ft′′(x)=t+1/x2+1/(1−x)2F_t''(x)=t+1/x^2+1/(1-x)^2;障礙定義域內所有分母皆正。

程式碼 · Python · 36 行
import numpy as np

def center(t, x):
    def value(z):
        return 0.5*t*(z-2)**2 - np.log(z) - np.log1p(-z)
    for _ in range(100):
        grad = t*(x-2) - 1/x + 1/(1-x)
        hess = t + 1/x**2 + 1/(1-x)**2
        step = -grad/hess
        if grad*grad/hess < 1e-16:
            break
        alpha = 1.0
        for _ in range(100):
            trial = x + alpha*step
            if 0 < trial < 1 and value(trial) <= value(x) + 0.01*alpha*grad*step:
                break
            alpha *= 0.5
        else:
            raise RuntimeError("Line search failed")
        x = trial
    else:
        raise RuntimeError("Centering iteration limit reached")
    return x
x = 0.5
for t in [1., 4., 16., 64., 256., 1024.]:
    x = center(t, x)
    lower, upper = 1/(t*x), 1/(t*(1-x))
    stationarity = x-2-lower+upper
    primal = 0.5*(x-2)**2
    dual = 2-upper-0.5*(-2-lower+upper)**2
    gap = primal-dual
    print(int(t), round(x, 6), round(gap, 7), round(2/t, 7))
    assert 0 < x < 1
    assert abs(stationarity) < 1e-5
    assert abs(gap-2/t) < 1e-8
    assert primal-0.5 <= gap + 1e-8

可行回溯檢查在目標比較前執行,避免於定義域外計算對數。充分下降條件使用方向導數,牛頓遞減量則用於置中停止條件。迭代上限讓意外失敗變成明確錯誤,而非無窮迴圈。

障礙權重增加時,中心路徑的純量解接近上界;計算出的目標誤差保持低於對偶間隙。
圖 1 — 合成受限二次問題讓中心路徑憑證可見:解從內部接近一,計算出的對偶間隙限制其目標誤差。

實驗透過純量拉格朗日函數的無限制最小值計算真正對偶值,因此能獨立比較間隙與指定的 2/t2/t。大型非線性問題中,對偶函數本身可能需要另一個最佳化問題才能求值。原始/對偶殘差檢查此時有用,但必須說明它在何種正則條件下證明什麼。

接近端點時,1-x 很小,障礙 Hessian 很大。即使數學問題不變,更小的誤差目標仍可能使數值系統更難解。達到應用單位下足夠的準確度即可停止;要求每個可表示位數都準確,可能浪費工作,或暴露應用根本不需處理的條件數問題。

6. 可行性、嚴格可行性與 Phase I

可行解可能存在,卻沒有任何嚴格可行解。原不等式表示的障礙函數此時沒有定義域。這與不可行不同,求解器必須先區分,再嘗試追蹤中心路徑。

簡單的 Phase I(第一階段)構造增加純量 ss:

minimize⁡x,sssubject to⁡fi(x)≤s(i=1,…,m),Ax=b.\begin{aligned} \operatorname{minimize}_{x,s}\quad&s\\ \operatorname{subject\ to}\quad&f_i(x)\leq s\quad(i=1,\ldots,m),\\ &Ax=b. \end{aligned}

其中 ss 是限制最大不等式違反量的新增變數。s<0s\lt0 的點對原不等式嚴格可行;最適 ss 有經證明的正下界,就能證明不可行。最適值零可能代表只有邊界可行;未達到下確界與數值不確定性須另外處理。有限迭代失敗本身不能證明任何一種結果。

矛盾系統 x≤0x\leq0 與 x≥1x\geq1 的違反量為 max⁡(x,1−x)\max(x,1-x),在 x=1/2x=1/2 達到最小值二分之一。對兩條不等式取相同非負權重,也能產生明確的不可行性憑證。

程式碼 · Python · 18 行
import numpy as np

A = np.array([[1.0], [-1.0]])
b = np.array([0.0, -1.0])
y = np.array([0.5, 0.5])
print("A transpose y:", A.T @ y)
print("b transpose y:", b @ y)
assert np.all(y >= 0)
assert np.allclose(A.T @ y, 0)
assert b @ y < 0
# If A x <= b existed, multiplying by y would imply 0 <= b@y < 0.
grid = np.linspace(-1, 2, 301)
violation = np.maximum(grid, 1-grid)
assert np.isclose(violation.min(), 0.5)
# A different system is feasible only on its boundary.
A_boundary = np.array([[1.0], [-1.0]])
b_boundary = np.zeros(2)
assert np.all(A_boundary @ np.array([0.0]) <= b_boundary)

網格只是已推導最小值的示意,不是任意最佳化問題全域求解的證明。憑證才是關鍵論證:若 Ax≤bAx\leq b,乘以 y≥0y\geq0 應得到 0=y⊤Ax≤y⊤b<00=y^\top Ax\leq y^\top b\lt0,矛盾。可直接查核資料與乘子。

矛盾區間與只有邊界可行點的違反量函數,標出各自最小值。
圖 2 — 正的最小違反量證明矛盾區間不可行;第二例的零最小值則指出一個沒有嚴格內部的可行點。

只有邊界可行的系統 x≤0x\leq0、−x≤0-x\leq0,唯一可行點是零。消去被固定的變數,或把條件寫成等式。起點稍微移動沒有用,因往任一方向移都會違反其中一條。相關內部是把強制等式處理後的相對內部。

Phase I 也依賴 fif_i 定義域。放寬不等式值不會自動讓對數、矩陣反矩陣或其他運算有定義。須在函數定義域內初始化,或採合適改寫。函數定義域可行性與仿射、不等式殘差應分開檢查。

Phase I 的對偶價格會正規化

最大違反量形式把初始化連到對偶憑證。對 fi(x)−s≤0f_i(x)-s\leq0 附乘子 λi≥0\lambda_i\geq0,對 Ax−b=0Ax-b=0 附乘子 ν\nu。其拉格朗日函數為

LI(x,s,λ,ν)=(1−∑iλi)s+∑iλifi(x)+ν⊤(Ax−b).L_I(x,s,\lambda,\nu) =\left(1-\sum_i\lambda_i\right)s +\sum_i\lambda_i f_i(x)+\nu^\top(Ax-b).

其中 x,sx,s 是 Phase I 變數、λ,ν\lambda,\nu 是其乘子、fi,A,bf_i,A,b 是原限制資料。因為 ss 不受符號限制,其下確界只在 ∑iλi=1\sum_i\lambda_i=1 時有限。因此不等式價格形成正規化非負權重。剩下加權函數的有限下界,會界定原限制的最大違反量 [1,第 11.4 節]。

對 f1(x)=xf_1(x)=x、f2(x)=1−xf_2(x)=1-x,取 λ1=λ2=1/2\lambda_1=\lambda_2=1/2。加權和對每個 xx 都恰為 1/21/2。因此 Phase I 最佳值至少為 1/21/2,而 x=1/2,s=1/2x=1/2,s=1/2 達到該值。原問題與對偶值相等,證明原不等式不可行。

對只有邊界可行的 f1(x)=xf_1(x)=x、f2(x)=−xf_2(x)=-x,相同正規化加權和為零。可行 Phase I 點 x=0,s=0x=0,s=0 匹配它,卻不可能有負的 ss。零違反量可證明普通可行性,卻無法提供對數障礙需要的嚴格內部。消去被強制的等式,是適當的下一個建模步驟。

7. 原始/對偶步驟與可靠停止

原始/對偶方法直接處理近似最適方程,不必完全解完每個獨立障礙問題。它維護正的不等式乘子與鬆弛量,再解線性化系統,同時降低駐點、可行性與互補性誤差。

令不等式 ii 的鬆弛量為 si=−fi(x)>0s_i=-f_i(x)\gt0,乘子 λi>0\lambda_i\gt0。原問題的殘差包括:

rdual=∇f0(x)+∑iλi∇fi(x)+A⊤ν,rpri=Ax−b,η=∑iλisi.\begin{aligned} r_{\mathrm{dual}}&=\nabla f_0(x)+\sum_i\lambda_i\nabla f_i(x)+A^\top\nu,\\ r_{\mathrm{pri}}&=Ax-b,\\ \eta&=\sum_i\lambda_i s_i. \end{aligned}

其中 rdualr_{\mathrm{dual}} 是駐點殘差,rprir_{\mathrm{pri}} 是等式殘差,η\eta 是互補乘積總和。函數、矩陣、乘子與鬆弛量定義同前。仿射不等式可以明確加入獨立的鬆弛量方程;非線性表示則可透過 fi(x)f_i(x) 表達。

η\eta 很小但可行性殘差很大,不是有效的近似解。無限制座標中的梯度很小,也不能證明受限最適。所有相關殘差、乘子符號與定義域條件都要通過。原始點與乘子可行且滿足駐點時,互補乘積總和對應對偶間隙;否則需要限定解讀。

保留邊界距離的線搜尋(fraction-to-boundary)限制步幅,保持鬆弛量與乘子為正。它是演算法定義域的數值保護,不是新增的解限制。不可行起點法可以一開始違反仿射等式,同時保留公式所需的內部條件;其評價函數須減少殘差,而不能只在不可行點比較原目標。

稀疏線性代數往往占主要成本。非零樣式決定分解填入、記憶體及可否重用。少量迭代也可能每一步都很昂貴。比較方法時,除迭代次數外也記錄分解時間與尖峰記憶體。稠密教學實作隱藏這些成本,不宜預測大型問題效能。

標準化求解後,須回到原問題查核解。求解器可能引入輔助變數、錐限制,正規化資料或移除冗餘列。這些操作有助計算,但應用需要原單位限制與可解讀的目標。記錄狀態、殘差、容許誤差、模型版本,以及任何改動回傳點的後處理。

線性化原始/對偶方程

原始/對偶牛頓步驟同時處理最適方程。對 Q⪰0Q\succeq0 的二次目標、仿射不等式 Gx+s=hGx+s=h 與等式 Ax=bAx=b,使用正鬆弛向量 ss 和正乘子向量 λ\lambda。令 cc 為目標線性係數,ν\nu 為等式乘子。

定義 rd=Qx+c+G⊤λ+A⊤νr_d=Qx+c+G^\top\lambda+A^\top\nu、rg=Gx+s−hr_g=Gx+s-h、ra=Ax−br_a=Ax-b。選定互補性目標 τ>0\tau>0 後,線性化得到

QΔx+G⊤Δλ+A⊤Δν=−rd,GΔx+Δs=−rg,AΔx=−ra,ΛΔs+SΔλ=τ1−Sλ.\begin{aligned} Q\Delta x+G^\top\Delta\lambda+A^\top\Delta\nu&=-r_d,\\ G\Delta x+\Delta s&=-r_g,\\ A\Delta x&=-r_a,\\ \Lambda\Delta s+S\Delta\lambda&=\tau\mathbf1-S\lambda. \end{aligned}

其中 G,hG,h 指定仿射不等式係數與界限;A,bA,b 指定等式;rd,rg,rar_d,r_g,r_a 分別為駐點、不等式可行性與等式可行性殘差,τ\tau 是互補性目標。Δx,Δs,Δλ,Δν\Delta x,\Delta s,\Delta\lambda,\Delta\nu 是增量;S=diag⁡(s)S=\operatorname{diag}(s)、Λ=diag⁡(λ)\Lambda=\operatorname{diag}(\lambda),1\mathbf1 是全一向量。最後一列線性化乘積 siλi=τs_i\lambda_i=\tau,只省略增量的二階乘積。相較完整障礙置中求解,一步就同時降低可行性、駐點與互補性誤差 [1,第 11.7 節]。

若某個鬆弛增量為負,該座標要求步長 α<−si/Δsi\alpha\lt -s_i/\Delta s_i 才能保持正值。負乘子增量也套用相同規則,取最小容許界限並略留在內側。這便推導出朝邊界比例限制,而非任意裁切規則。仍須加上殘差下降測試:只保持正值並不保證收斂。

8. 在應用邊界解讀憑證

最適性憑證回答指定模型的數學問題。應用決策還取決於模型是否納入正確的限制、量與不確定性。最終報告分開查核兩者:數值正確不能補救遺漏的需求。

假設資源分配模型限制總功率,卻漏掉個別裝置上限。求解器可能得到全域最適且精確證明的分配,但某台裝置無法執行。補上遺漏限制再解,不要把先前結果叫作求解器失敗。相反,限制都已納入,回傳點卻超出容許誤差,問題屬於數值驗收或求解本身。

看到答案前先選容許誤差。溫度上界、預算等式與無因次機率限制需要不同解讀。先用原單位寫出可接受偏差,再連接求解器誤差與尺度設定。後續四捨五入若改變變數,須再次查核可行性;未四捨五入向量的憑證,不會自動證明顯示或實際執行的決策。

符合對偶章節假設時,乘子可解釋敏感度。緊限制的大乘子表示局部小幅放寬可能明顯影響目標;它不是任意大幅變動的預測,尤其活躍限制改變時。小幅擾動、重解問題,並比較實際目標變化與局部預測。

近退化問題須謹慎解讀。幾條幾乎冗餘的限制可能使乘子難以穩定決定,原始決策卻很穩定。乘子變化此時可能誇大決策本身的不確定性。原始與對偶敏感度都要看,影子價格的精度不可超過資料與條件數能支持的程度。

暖啟動也屬於這個邊界。昨天的解可能靠近今天的最小解,卻違反更新後的限制。可行起點障礙法須先找新的內點;原始/對偶或齊次嵌入求解器則可能採其他初始化策略。只有方法支援該可行性狀態才傳入暖啟動;耦合等式存在時,不要逐座標裁切。

有用的結果組合包含模型與資料版本、原目標、原始變數、相關乘子、原單位最大違反量、有效的間隙或下界,以及停止狀態。效能重要時再附實測時間與記憶體。讀者才能區分可信的近似最小解、不可行性憑證、尚未解決的數值結果,以及需要修正的模型。

現代觀點

內點理論仍有用,現代求解器則在精度、記憶體與硬體上採不同選擇。以下資料提供演算法分類與截至 2026 年 10 月 4 日查核的現代證據。

Bubeck 專論 [2] 依 oracle 提供的資訊、幾何與結構整理一階、結構式及內點方法。比較應同時考慮每步成本,以及 oracle 與假設附帶的保證。本章綜合觀點是依問題中便宜的運算選方法:矩陣向量乘法、投影、近端映射或矩陣分解。

Parikh 與 Boyd 的近端綜述 [3] 用小型凸子問題整理非平滑、受限與分散式演算法,補足障礙觀點:投影或近端運算可以不透過對數內部表示就處理限制。其成本依集合不同而變;數學凸性不決定哪個運算便宜。

Goulart 與 Chen 的 2026 年 Clarabel 論文 [4] 描述使用齊次嵌入、支援多種錐及二次目標的內點求解器,把教科書原理連接到處理不可行性與計算結構的軟體。比較結果屬於所測問題與設定,不代表每個凸模型都有同一個全面贏家。

Applegate 等人的 PDLP 手稿 [5] 於 2025 年首次發布、2026 年修訂,以矩陣向量運算為基礎,加入前處理、尺度調整與自適應策略,發展大型線性規劃的一階方法。它是預印本,效能主張是所報工作負載上的實驗證據。與內點法比較時,納入要求精度、記憶體預算與原單位殘差。

求解器家族昂貴運算結構問題須驗證什麼
等式限制牛頓法KKT 線性求解能否重用稀疏結構與分解?可行性與駐點條件
障礙/內點法改變的曲率與受限求解是否有合適內部與錐表示?定義域、殘差、間隙或憑證
投影/近端方法投影或近端子問題限制或非平滑項是否易處理?迭代殘差與可行輸出
大型一階線性規劃矩陣向量乘法其他方法是否受記憶體或分解限制?指定準確度下的縮放與原始殘差

目前方法論的重點不限於偏好一階或二階。模型表示、前處理、尺度、線性代數與停止政策都是實際演算法行為的一部分。只比較命名的更新公式,會漏掉決定可靠度的許多系統工作。

未解問題包括尺度不良模型的準確憑證、幾乎低維可行區域的穩健性、大型分解的記憶體限制,以及限制改變時的有效暖啟動。學習式預測可以提供起點,但仍須查核可行性與最適性。近似解的誤差若能用應用可容忍的量表示,就有價值。

求解器實驗可建立只改變一項性質的問題族:條件數、活躍限制數、稀疏性或要求誤差。盡可能保留已知最小解或獨立查核的界限。除了時間,也回報失敗與不準確狀態。這類控制問題族比一次預設成功求解更有教學價值。

重點整理

  • 等式限制牛頓步驟保持在等式矩陣的零空間。
  • 即使目標凸,KKT 矩陣通常仍不定。
  • 對數障礙需要相關定義域中的嚴格可行性。
  • 完全置中點在所述假設下產生間隙為 m/tm/t 的對偶構造。
  • 數值迭代點須檢查真實可行性、駐點條件與互補性。
  • 只有邊界可行與不可行不同;Phase I 須用憑證可靠區分。
  • 在原問題單位下比較求解成本、精度與記憶體。

練習

  1. 受限曲率。建立完整 Hessian 奇異、但在仿射等式集合上有唯一最小解的半正定二次問題。
提示

讓零曲率方向被等式排除,只檢查滿足齊次等式的非零向量之曲率。

  1. 等式縮放。將二次範例的等式乘以 1000,比較解、乘子與殘差尺度,說明哪些量應保持不變。
提示

可行集合不變;乘子反向縮放,原始殘差隨限制列縮放。兩個表示都要查核駐點條件。

  1. 重複障礙。複製純量範例的上界不等式,比較有限 tt 中心路徑與理論間隙使用的項數。
提示

可行集合相同,但上界對數出現兩次,現在有三個純量障礙項。

  1. 初始化。讓純量求解器從零開始,解釋失敗。對此問題及等式強制為零的變數,分別給出有原則的修正。
提示

自由非負變數能從嚴格正值開始;被固定為零的變數須消去或改用等式表示,不能只微調數值。

  1. 不可行性憑證。把矛盾區間推廣成 x≤ax\leq a 與 x≥bx\geq b,a<ba\lt b。推導最大違反量的最小值及非負憑證。
提示

中點平衡兩項違反量。相同權重消掉變數,留下負的右側總和。

  1. 停止政策。求解器回報互補性很小,等式殘差卻非零。寫出接受結果前須加的檢查,解釋只回報目標為何不足。
提示

納入原單位等式與不等式殘差、定義域、乘子符號、駐點條件,以及能取得時的有效下界。

參考文獻

  1. S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004, Chapters 10–11. Book and official PDF
  2. S. Bubeck, “Convex Optimization: Algorithms and Complexity,” Foundations and Trends in Machine Learning, 2015. Monograph
  3. N. Parikh and S. Boyd, “Proximal Algorithms,” Foundations and Trends in Optimization, 2014. Author page and article
  4. P. J. Goulart and Y. Chen, “Clarabel: An Interior-Point Solver for Conic Programs with Quadratic Objectives,” Mathematical Programming Computation, 2026. Published paper · Author manuscript
  5. D. Applegate, M. Díaz, O. Hinder, H. Lu, M. Lubin, B. O’Donoghue and W. Schudy, “PDLP: A Practical First-Order Method for Large-Scale Linear Programming,” arXiv preprint, 2025, revised 2026. Paper

檢查理解

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

前往練習 ↑

下一篇 OPT 08・幾何應用、分裂法與現代方法 · 18 分鐘