07.2 KKT 條件、拉格朗日對偶性與內點法#

從 Lagrange 乘數法說起#

1788 年，Joseph-Louis Lagrange 出版《分析力學》，把牛頓力學改寫成純粹的解析語言。書中提出的「乘數法」是處理約束極值的優雅工具：想在約束 \(g(x)=0\) 下極小化 \(f(x)\)，就構造

令其梯度為零。一階條件從此成為「拉格朗日條件」。這個方法在十九世紀被物理學家大量使用，但它的舞台是等式約束與光滑世界，直到二十世紀，經濟學與戰爭才逼出不等式約束的一般理論。

Karush 1939 與 Kuhn-Tucker 1951#

1939 年，芝加哥大學碩士生 William Karush 在未發表的碩士論文中，寫下了不等式約束極值的一階必要條件。但當時最優化還不是一門學科，這份論文在圖書館裡沉睡了十餘年。

1951 年，Harold Kuhn 與 Albert Tucker 在 Berkeley 的數學與經濟學研討會上發表論文，正式提出同樣的條件，從此被稱為 Kuhn-Tucker 條件。這個時間差並非偶然：二次大戰後，經濟學界正急於把資源配置問題數學化，Koopmans、Dantzig 等人的線性規劃讓「約束最優化」成為顯學，Kuhn-Tucker 條件恰逢其時。後來學界補上了 Karush 的功勞，稱之為 KKT 條件：

最後那個互補鬆弛條件有一個漂亮的經濟解讀：乘數 \(\lambda_i\) 是「影子價格」——約束資源的邊際價值。資源用不滿（\(g_i<0\)）則影子價格為零，資源吃緊則價格為正。對偶性理論由此成為連接最優化與經濟學的橋樑：原始問題求最好的方案，對偶問題求最準的價格。

Dantzig 與 simplex：RAND 公司與冷戰後勤#

1947 年，George Dantzig 在為美國空軍規劃後勤時發明線性規劃與 simplex 法。空軍隨後成立 SCOOP 計畫（Scientific Computation of Optimum Programs），Dantzig 於 1952 年轉入蘭德公司（RAND），simplex 在當時的電腦上跑出實用的解。線性規劃的原始—對偶結構，正是 Lagrange 對偶性最成熟的教科書案例，石油煉製、飼料配比、運輸排程全面採用。

數學家也曾追問：simplex 會不會很慢？1972 年，Klee 與 Minty 構造出一族「扭曲的立方體」，使 simplex 的路徑長度呈指數成長。這個反例震動學界，卻沒有動搖 simplex 的實用地位——它平均而言極快，但理論上的最壞情況成為懸案，也成為推動新演算法的動力。

橢球法：蘇聯學派的迴響#

1979 年，蘇聯數學家 Leonid Khachiyan 證明橢球法（ellipsoid method，源自 1970 年代蘇聯學者 Shor、Nemirovski、Yudin 的工作）能在多項式時間內解線性規劃。《紐約時報》以頭版報導「蘇聯數學發現震驚數學界」，在冷戰氛圍下，這被賦予了政治想像。然而實際計算中，橢球法慢得乏善可陳——理論與實務的落差，正是下一場革命的引信。

Karmarkar 內點法：貝爾實驗室與專利爭議#

1984 年，任職 AT&T 貝爾實驗室的印度裔數學家 Narendra Karmarkar 發表內點法：沿著問題內部投影變換的路徑走，同時達到多項式複雜度與實務上的高效率，雙雙超越橢球法與 simplex。AT&T 為此申請專利，並推出專屬的 KORBX 系統販售給航空與軍方，引發學界關於「數學演算法能否被壟斷」的激烈爭論。這場爭議反而促成了商業優化軟體產業的成熟：CPLEX（1988 年創立，1997 年被 ILOG 併購，後歸 IBM）、Gurobi 等公司，讓內點法與 simplex 在同一套求解器內並存。

現代凸優化#

1990 年代起，Nesterov 與 Nemirovski 建立內點法的一般凸優化理論；Stephen Boyd 在 Stanford 的著作《Convex Optimization》（2004）與其開放課程，把對偶性、KKT 條件與內點法打包成工程師的標準工具箱，支撐了控制、機器學習、金融與 5G 通訊中無數的模型。今天從支撐向量機的對偶問題到資源調度的影子價格，KKT 條件仍在每一行求解器程式碼深處運轉。

小結#

Lagrange 的力學、Karush 沉睡的論文、Kuhn-Tucker 的經濟學動機、Dantzig 的戰後後勤、Klee-Minty 的反例、冷戰兩岸的橢球法與內點法——約束最優化的歷史，正是數學、經濟、軍事與產業互相驅動的縮影。