OPT 07・等式限制與內點法
導覽:本頁與本系列: 導覽:本頁與本系列
本頁內容
最佳化
你將學到
- 把牛頓法延伸到含仿射等式的凸目標函數。
- 推導對數障礙函數、中心路徑及其對偶間隙。
- 實作具有明確線搜尋的小型可行障礙法求解器。
- 區分可行、嚴格可行與不可行的限制系統。
- 解讀原始/對偶殘差、互補性與不可行性憑證。
- 依數值需求比較現代內點法與一階求解器。
先看全貌
限制式說明解可以做什麼。求解器改善目標時不能忽略它們。等式把每個容許步驟限制在較低維度的空間;不等式則產生必須處理的邊界。內點法(interior-point method)透過一系列問題逼近有用的邊界解,而迭代點保持在邊界內側。
本章搭配 Boyd 與 Vandenberghe 第 10–11 章 [1]:第 10 章處理等式限制下的最小化,第 11 章發展障礙函數、中心路徑、初始化與原始/對偶方法。先讀梯度與牛頓法;憑證看不懂時,回到對偶性與最適條件。Bubeck 的演算法專論 [2] 提供複雜度與求解器家族的另一種觀點。
範例使用低維度合成問題,讓每項主張都能獨立查核。程式是附有斷言、假設透明的教學實作。正式錐規劃求解器還需要尺度調整、稀疏矩陣分解、數值正則化、停止政策與不可行性處理;理解小問題有助於理解這些工程選擇。
1. 等式限制改變容許的方向
目標下降時,仿射等式仍須成立。目前點若滿足 ,步驟 保持可行的充分必要條件是 。先看幾何再看矩陣:容許的步驟位於等式矩陣的零空間。
考慮凸問題:
其中 是變數, 是二次可微的凸目標函數, 與 是固定資料。先假設 各列獨立,且等式系統有解。拉格朗日乘子 表示等式限制的影響。
在可行迭代點,沿可行方向最小化二次近似,得到牛頓系統:
其中 是 Hessian 矩陣, 是原始變數的候選步驟, 是局部二次子問題的等式乘子,零區塊大小為 。第二個區塊方程強制 。 解的是局部模型,不一定等於另一個持續維護的乘子估計之增量。
Hessian 只須沿非零可行方向具有正曲率,受限二次模型就能表現良好;被等式排除的方向不必有正曲率。因此完整 Hessian 可能奇異,但受限最小解仍唯一。判斷奇異性是否代表多解前,先檢查真正的可行子空間。
區塊矩陣稱為 Karush–Kuhn–Tucker(KKT)矩陣 [1]。即使 正定,整個矩陣通常仍是不定矩陣。不要因原目標凸,就對整個矩陣使用只適合正定矩陣的分解。其結構同時表達原始與對偶方程;小型稠密範例使用一般線性求解即可。
另一種方法是消去等式。取一個可行點 ,以及欄向量張成 零空間的矩陣 ,寫成 ,其中 是降維變數,再解 的無限制問題。消去法能簡化小問題,卻可能破壞大問題的稀疏性。兩者幾何相同,計算表示決定成本。
限制子空間曲率與區塊消去
Hessian 奇異不代表受限步驟不明確。在 下最小化 。Hessian 為 ,但可行方向只能改變 。唯一最小解為 :等式恰好移除平坦方向。
一般而言,令 的獨立欄向量張成 的零空間。縮減 Hessian 為 。這個較小矩陣正定,就能讓可行方向上的局部二次模型有唯一最小解,即使 奇異也一樣。其中 是目前 Hessian、 是滿列秩的等式矩陣 [1,第 10 章]。
若 本身正定,也可消去原問題方向來推導 KKT 步驟。寫 ,利用第一個區塊方程:
其中 是步驟、 是局部等式乘子。把第一行代入 即得第二行。 各列獨立時,這個較小矩陣為正定:對非零 ,二次型為 。
這些方程解釋區塊求解,但反矩陣符號只是代數表示。實作應透過 的線性求解計算乘積,再比較消去法與直接稀疏 KKT 分解的成本。前面的奇異例子仍能使用零空間表示,卻不能使用這種完整 Hessian 消去。
2. 帶有可查核憑證的受限二次問題
二次目標讓 KKT 方程成為精確條件而非近似。區塊系統產生候選解;檢查等式可行性與駐點條件,才能判斷候選解是否構成這個凸問題的最適性憑證。
對於:
是對稱半正定矩陣, 是固定向量, 是變數。最適配對 滿足 及 ;星號代表最適值。對可行凸二次問題,這些方程足以保證最適;唯一性還需要可行方向的額外曲率。
程式碼 · 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. 不等式轉成平滑的內部問題
障礙函數接近邊界時無限增大,只在嚴格可行點有限。如此平滑的受限牛頓法就能把不等式透過目標處理,同時保留明確的仿射等式。
考慮凸不等式 ,,以及 ,定義:
其中 是原凸目標, 是各凸不等式函數, 是純量不等式數目, 是對數障礙函數, 控制原目標的相對重要性。定義域要求每個 ;障礙問題在 下最小化 。
限制函數應以一致單位表示,或取對數前除以正的參考尺度。正數縮放只增加障礙函數的常數項,不改變最小解,但有限精度計算仍可能受影響。數學上的不變性不能當成忽略數值尺度的理由。
二次可微不等式的障礙項,梯度為 ,Hessian 為:
其中 是梯度欄向量, 是 Hessian。因 凸,嚴格可行定義域內兩項皆半正定。式子也顯示接近活躍邊界、 變小時,曲率迅速增加。
限制的表示影響路徑。重複同一限制會重複其障礙項,因此有限 的近似問題不同,雖然精確可行集合相同。等價限制集合不一定產生相同中間迭代點;標準化與尺度調整是能觀察效果的演算法選擇。
障礙法不能從邊界開始。非負變數起點若為零, 無定義。自由變數可以用嚴格正值初始化;若等式強制變數為零,則需要重寫問題。任意給限制加一個正偏移會改變問題,不能當作無害的實作修正。
4. 中心路徑連接內點與對偶界限
對每個障礙權重準確求解內部問題,其最小解形成中心路徑(central path)。增加權重會減弱障礙相對原目標的影響,讓解接近可能位於邊界的受限最小解。
令 在 下最小化 ,定義:
其中 是不等式乘子, 是縮放障礙問題的等式乘子, 則是原目標尺度的乘子。、 與 的定義同前。
障礙駐點條件成為原拉格朗日函數的駐點條件;互補性改為 。各純量不等式貢獻相同的正乘積。真正最適點的互補鬆弛要求這些乘積為零; 增加時,障礙路徑逐漸逼近這項條件。
在完全置中且滿足所述假設的點,其原始/對偶間隙為:
其中 是拉格朗日對偶函數,對對偶可行乘子提供最適目標的下界。原始值是上界,對偶值是下界,間隙因此限制目標次最適誤差。這是關於所建立凸問題的敘述,不保證模型符合應用。
等式需要精確置中及有效的對偶構造。駐點殘差很大的數值迭代點,不能只印出 就宣稱得到精確間隙。以理論值規劃障礙排程,再檢查真實殘差,能計算時也求出真正的對偶下界。如此才不會把外迴圈計數當作憑證。
外層障礙法交替進行兩件事:解固定 的內部問題,再增加 。以前一解作下一起點通常有幫助,因最小解往往相近;但 一次改太多會使置中昂貴。依置中實際成本選擇增幅,而不是假設外層迭代越少,總計算就越少。
間隙 真正從哪裡來
中心路徑間隙是明確價格乘以明確鬆弛量的總和。在精確置中的點,把障礙問題駐點方程除以 :
其中 最小化障礙問題、 是其等式乘子、 是原目標與不等式、 是障礙權重。代入已定義的 與 ,便恰好得到原拉格朗日函數的駐點方程。
原函數凸且不等式乘子非負,因此拉格朗日函數對 凸。駐點條件使 成為其全域最小解,所以在此點評估 確實算出對偶函數。等式可行性消去等式項,得到
其中 是對偶函數、 是純量不等式數量。從可行原問題目標減去這個下界,即得間隙。中心點通常不是原最佳解:它在目標改善與正鬆弛量間取捨,但其乘子已提供憑證,而且誤差隨障礙減弱而下降 [1,第 11.2 節]。
若希望理論間隙至多為 ,選 ,再把置中問題解得足夠準確。選擇 提供目標;駐點求解才是使用公式的依據。只增加 卻不置中,就漏掉證明的關鍵等式。
5. 完整的一維障礙法實驗
使用真正最小解容易查核的二次問題:在 下最小化 。無限制最小點是二,最近的容許點是一,目標值為二分之一。障礙解嚴格位於零與一之間,逐漸接近上端點。
此例為:
其中 是純量變數, 是目標權重。一、二階導數為 與 ;障礙定義域內所有分母皆正。
程式碼 · 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-x 很小,障礙 Hessian 很大。即使數學問題不變,更小的誤差目標仍可能使數值系統更難解。達到應用單位下足夠的準確度即可停止;要求每個可表示位數都準確,可能浪費工作,或暴露應用根本不需處理的條件數問題。
6. 可行性、嚴格可行性與 Phase I
可行解可能存在,卻沒有任何嚴格可行解。原不等式表示的障礙函數此時沒有定義域。這與不可行不同,求解器必須先區分,再嘗試追蹤中心路徑。
簡單的 Phase I(第一階段)構造增加純量 :
其中 是限制最大不等式違反量的新增變數。 的點對原不等式嚴格可行;最適 有經證明的正下界,就能證明不可行。最適值零可能代表只有邊界可行;未達到下確界與數值不確定性須另外處理。有限迭代失敗本身不能證明任何一種結果。
矛盾系統 與 的違反量為 ,在 達到最小值二分之一。對兩條不等式取相同非負權重,也能產生明確的不可行性憑證。
程式碼 · 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)網格只是已推導最小值的示意,不是任意最佳化問題全域求解的證明。憑證才是關鍵論證:若 ,乘以 應得到 ,矛盾。可直接查核資料與乘子。

只有邊界可行的系統 、,唯一可行點是零。消去被固定的變數,或把條件寫成等式。起點稍微移動沒有用,因往任一方向移都會違反其中一條。相關內部是把強制等式處理後的相對內部。
Phase I 也依賴 定義域。放寬不等式值不會自動讓對數、矩陣反矩陣或其他運算有定義。須在函數定義域內初始化,或採合適改寫。函數定義域可行性與仿射、不等式殘差應分開檢查。
Phase I 的對偶價格會正規化
最大違反量形式把初始化連到對偶憑證。對 附乘子 ,對 附乘子 。其拉格朗日函數為
其中 是 Phase I 變數、 是其乘子、 是原限制資料。因為 不受符號限制,其下確界只在 時有限。因此不等式價格形成正規化非負權重。剩下加權函數的有限下界,會界定原限制的最大違反量 [1,第 11.4 節]。
對 、,取 。加權和對每個 都恰為 。因此 Phase I 最佳值至少為 ,而 達到該值。原問題與對偶值相等,證明原不等式不可行。
對只有邊界可行的 、,相同正規化加權和為零。可行 Phase I 點 匹配它,卻不可能有負的 。零違反量可證明普通可行性,卻無法提供對數障礙需要的嚴格內部。消去被強制的等式,是適當的下一個建模步驟。
7. 原始/對偶步驟與可靠停止
原始/對偶方法直接處理近似最適方程,不必完全解完每個獨立障礙問題。它維護正的不等式乘子與鬆弛量,再解線性化系統,同時降低駐點、可行性與互補性誤差。
令不等式 的鬆弛量為 ,乘子 。原問題的殘差包括:
其中 是駐點殘差, 是等式殘差, 是互補乘積總和。函數、矩陣、乘子與鬆弛量定義同前。仿射不等式可以明確加入獨立的鬆弛量方程;非線性表示則可透過 表達。
很小但可行性殘差很大,不是有效的近似解。無限制座標中的梯度很小,也不能證明受限最適。所有相關殘差、乘子符號與定義域條件都要通過。原始點與乘子可行且滿足駐點時,互補乘積總和對應對偶間隙;否則需要限定解讀。
保留邊界距離的線搜尋(fraction-to-boundary)限制步幅,保持鬆弛量與乘子為正。它是演算法定義域的數值保護,不是新增的解限制。不可行起點法可以一開始違反仿射等式,同時保留公式所需的內部條件;其評價函數須減少殘差,而不能只在不可行點比較原目標。
稀疏線性代數往往占主要成本。非零樣式決定分解填入、記憶體及可否重用。少量迭代也可能每一步都很昂貴。比較方法時,除迭代次數外也記錄分解時間與尖峰記憶體。稠密教學實作隱藏這些成本,不宜預測大型問題效能。
標準化求解後,須回到原問題查核解。求解器可能引入輔助變數、錐限制,正規化資料或移除冗餘列。這些操作有助計算,但應用需要原單位限制與可解讀的目標。記錄狀態、殘差、容許誤差、模型版本,以及任何改動回傳點的後處理。
線性化原始/對偶方程
原始/對偶牛頓步驟同時處理最適方程。對 的二次目標、仿射不等式 與等式 ,使用正鬆弛向量 和正乘子向量 。令 為目標線性係數, 為等式乘子。
定義 、、。選定互補性目標 後,線性化得到
其中 指定仿射不等式係數與界限; 指定等式; 分別為駐點、不等式可行性與等式可行性殘差, 是互補性目標。 是增量;、, 是全一向量。最後一列線性化乘積 ,只省略增量的二階乘積。相較完整障礙置中求解,一步就同時降低可行性、駐點與互補性誤差 [1,第 11.7 節]。
若某個鬆弛增量為負,該座標要求步長 才能保持正值。負乘子增量也套用相同規則,取最小容許界限並略留在內側。這便推導出朝邊界比例限制,而非任意裁切規則。仍須加上殘差下降測試:只保持正值並不保證收斂。
8. 在應用邊界解讀憑證
最適性憑證回答指定模型的數學問題。應用決策還取決於模型是否納入正確的限制、量與不確定性。最終報告分開查核兩者:數值正確不能補救遺漏的需求。
假設資源分配模型限制總功率,卻漏掉個別裝置上限。求解器可能得到全域最適且精確證明的分配,但某台裝置無法執行。補上遺漏限制再解,不要把先前結果叫作求解器失敗。相反,限制都已納入,回傳點卻超出容許誤差,問題屬於數值驗收或求解本身。
看到答案前先選容許誤差。溫度上界、預算等式與無因次機率限制需要不同解讀。先用原單位寫出可接受偏差,再連接求解器誤差與尺度設定。後續四捨五入若改變變數,須再次查核可行性;未四捨五入向量的憑證,不會自動證明顯示或實際執行的決策。
符合對偶章節假設時,乘子可解釋敏感度。緊限制的大乘子表示局部小幅放寬可能明顯影響目標;它不是任意大幅變動的預測,尤其活躍限制改變時。小幅擾動、重解問題,並比較實際目標變化與局部預測。
近退化問題須謹慎解讀。幾條幾乎冗餘的限制可能使乘子難以穩定決定,原始決策卻很穩定。乘子變化此時可能誇大決策本身的不確定性。原始與對偶敏感度都要看,影子價格的精度不可超過資料與條件數能支持的程度。
暖啟動也屬於這個邊界。昨天的解可能靠近今天的最小解,卻違反更新後的限制。可行起點障礙法須先找新的內點;原始/對偶或齊次嵌入求解器則可能採其他初始化策略。只有方法支援該可行性狀態才傳入暖啟動;耦合等式存在時,不要逐座標裁切。
有用的結果組合包含模型與資料版本、原目標、原始變數、相關乘子、原單位最大違反量、有效的間隙或下界,以及停止狀態。效能重要時再附實測時間與記憶體。讀者才能區分可信的近似最小解、不可行性憑證、尚未解決的數值結果,以及需要修正的模型。
現代觀點
內點理論仍有用,現代求解器則在精度、記憶體與硬體上採不同選擇。以下資料提供演算法分類與截至 2026 年 10 月 4 日查核的現代證據。
Bubeck 專論 [2] 依 oracle 提供的資訊、幾何與結構整理一階、結構式及內點方法。比較應同時考慮每步成本,以及 oracle 與假設附帶的保證。本章綜合觀點是依問題中便宜的運算選方法:矩陣向量乘法、投影、近端映射或矩陣分解。
Parikh 與 Boyd 的近端綜述 [3] 用小型凸子問題整理非平滑、受限與分散式演算法,補足障礙觀點:投影或近端運算可以不透過對數內部表示就處理限制。其成本依集合不同而變;數學凸性不決定哪個運算便宜。
Goulart 與 Chen 的 2026 年 Clarabel 論文 [4] 描述使用齊次嵌入、支援多種錐及二次目標的內點求解器,把教科書原理連接到處理不可行性與計算結構的軟體。比較結果屬於所測問題與設定,不代表每個凸模型都有同一個全面贏家。
Applegate 等人的 PDLP 手稿 [5] 於 2025 年首次發布、2026 年修訂,以矩陣向量運算為基礎,加入前處理、尺度調整與自適應策略,發展大型線性規劃的一階方法。它是預印本,效能主張是所報工作負載上的實驗證據。與內點法比較時,納入要求精度、記憶體預算與原單位殘差。
| 求解器家族 | 昂貴運算 | 結構問題 | 須驗證什麼 |
|---|---|---|---|
| 等式限制牛頓法 | KKT 線性求解 | 能否重用稀疏結構與分解? | 可行性與駐點條件 |
| 障礙/內點法 | 改變的曲率與受限求解 | 是否有合適內部與錐表示? | 定義域、殘差、間隙或憑證 |
| 投影/近端方法 | 投影或近端子問題 | 限制或非平滑項是否易處理? | 迭代殘差與可行輸出 |
| 大型一階線性規劃 | 矩陣向量乘法 | 其他方法是否受記憶體或分解限制? | 指定準確度下的縮放與原始殘差 |
目前方法論的重點不限於偏好一階或二階。模型表示、前處理、尺度、線性代數與停止政策都是實際演算法行為的一部分。只比較命名的更新公式,會漏掉決定可靠度的許多系統工作。
未解問題包括尺度不良模型的準確憑證、幾乎低維可行區域的穩健性、大型分解的記憶體限制,以及限制改變時的有效暖啟動。學習式預測可以提供起點,但仍須查核可行性與最適性。近似解的誤差若能用應用可容忍的量表示,就有價值。
求解器實驗可建立只改變一項性質的問題族:條件數、活躍限制數、稀疏性或要求誤差。盡可能保留已知最小解或獨立查核的界限。除了時間,也回報失敗與不準確狀態。這類控制問題族比一次預設成功求解更有教學價值。
重點整理
- 等式限制牛頓步驟保持在等式矩陣的零空間。
- 即使目標凸,KKT 矩陣通常仍不定。
- 對數障礙需要相關定義域中的嚴格可行性。
- 完全置中點在所述假設下產生間隙為 的對偶構造。
- 數值迭代點須檢查真實可行性、駐點條件與互補性。
- 只有邊界可行與不可行不同;Phase I 須用憑證可靠區分。
- 在原問題單位下比較求解成本、精度與記憶體。
練習
- 受限曲率。建立完整 Hessian 奇異、但在仿射等式集合上有唯一最小解的半正定二次問題。
提示
讓零曲率方向被等式排除,只檢查滿足齊次等式的非零向量之曲率。
- 等式縮放。將二次範例的等式乘以 1000,比較解、乘子與殘差尺度,說明哪些量應保持不變。
提示
可行集合不變;乘子反向縮放,原始殘差隨限制列縮放。兩個表示都要查核駐點條件。
- 重複障礙。複製純量範例的上界不等式,比較有限 中心路徑與理論間隙使用的項數。
提示
可行集合相同,但上界對數出現兩次,現在有三個純量障礙項。
- 初始化。讓純量求解器從零開始,解釋失敗。對此問題及等式強制為零的變數,分別給出有原則的修正。
提示
自由非負變數能從嚴格正值開始;被固定為零的變數須消去或改用等式表示,不能只微調數值。
- 不可行性憑證。把矛盾區間推廣成 與 ,。推導最大違反量的最小值及非負憑證。
提示
中點平衡兩項違反量。相同權重消掉變數,留下負的右側總和。
- 停止政策。求解器回報互補性很小,等式殘差卻非零。寫出接受結果前須加的檢查,解釋只回報目標為何不足。
提示
納入原單位等式與不等式殘差、定義域、乘子符號、駐點條件,以及能取得時的有效下界。
參考文獻
- S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004, Chapters 10–11. Book and official PDF
- S. Bubeck, “Convex Optimization: Algorithms and Complexity,” Foundations and Trends in Machine Learning, 2015. Monograph
- N. Parikh and S. Boyd, “Proximal Algorithms,” Foundations and Trends in Optimization, 2014. Author page and article
- 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
- 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 分鐘