不等式約束與 KKT 條件

當圍欄可碰可不碰

上一份指南解決的是約束必須嚴格成立的問題：在 g(x, y) = 0 的條件下極小化 f(x, y)。拉格朗日乘數告訴你：最優點落在 nabla f 與 nabla g 平行之處，因為沿著曲線 g = 0，已經沒有任何被允許的方向能讓 f 繼續下降。但現實中大多數約束並非等式——它們是你不得越過的上限。預算說總成本 <= B，而非成本 = B。材料說應力 <= S。機率說 p >= 0。這些是不等式約束，寫作 g(x) <= 0，它們以一種決定性的方式改變了幾何：可行域如今是一塊有邊界的實心區域，而不再是一條細細的曲線。

有了實心的可行域，最優點可能落在兩個本質不同的位置之一，而整套理論的關鍵就在於落在哪一個。要麼最優點嚴嚴實實地落在區域內部，離每道圍欄都很遠——那麼約束什麼也沒做，問題在局部就是一個普通的無約束最佳化，你只需像第一卷那樣求解 nabla f = 0。要麼最優點緊緊貼在某道圍欄 g(x) = 0 上——那麼該約束是起作用的（緊約束），其行為與上一份指南裡的等式約束完全一樣。難點在於：你通常事先並不知道自己處在哪一種情形；而 KKT 條件正是那套記賬法，讓代數替你做出判斷。

乘數的符號如今承載了含義

假設極小值的確落在圍欄 g = 0 上。和等式約束一樣，我們仍需 nabla f = mu nabla g（mu 是某個乘數），因為在最優點處，沒有任何可行方向能讓 f 下降。但不等式是單邊的，這種不對稱性釘死了 mu 的符號——這是等式情形從不關心的。回憶：梯度 nabla g 指向 g 增大的方向，也就是越過圍欄、朝向禁區 g > 0 的向外方向。要保持可行，你只能朝 nabla g 指向內側或側向之處邁步。要使 f 在這樣一點沒有可行的下降方向，nabla f 必須與 nabla g 指向同一個向外方向，這就迫使乘數非負：mu >= 0。

把這個符號條件作物理解讀，它就不再是技術細節。乘數 mu 是一個影子價格：它度量的是，若你把圍欄放鬆一絲（把 g <= 0 鬆到 g <= epsilon），f 的最優值會改善多少。mu 非負恰恰說出了直覺所要求的——放鬆一個緊約束只可能幫到你（或毫無影響），絕不會害你。如果你的代數在某個起作用的約束上算出 mu < 0，那它就不是一個可行的極小值：這意味著只要你邁下圍欄、走進內部，f 反而會下降，所以真正的最優點在內部，而這個約束本應被判定為不起作用。符號正是抓出這一錯誤的檢驗。

互補鬆弛：那個巧妙的開關

現在來看那個把兩種情形——內部或貼欄——熔合成一個整潔系統的巧招。我們為約束保留一個乘數 mu，並強加一條額外方程：mu g(x) = 0。這就是互補鬆弛，一個優雅的邏輯開關。乘積為零，當且僅當至少有一個因子為零，所以在任何一個解處，要麼 mu = 0（乘數被關掉），要麼 g = 0（約束起作用），或兩者皆是。若最優點嚴格在內部，則 g < 0，於是該方程迫使 mu = 0，約束便從 nabla f = mu nabla g 中悄然消失，只剩下純粹的 nabla f = 0。若最優點在圍欄上，則 g = 0，mu 便可自由地取正值、去幹它的活。一條方程，讓解自己選擇所處的狀態。

把這些零件裝到一起，你就得到了完整的 Karush-Kuhn-Tucker 條件——KKT 條件——用於在若干不等式約束 g_i(x) <= 0、以及可能存在的等式約束 h_j(x) = 0 下極小化 f。構造拉格朗日量 L = f + sum mu_i g_i + sum lambda_j h_j，與上一份指南如出一轍，只是有了兩族乘數，並同時要求四件事：平穩性（對 x 有 nabla L = 0）、原始可行性（每個 g_i <= 0 且 h_j = 0）、對偶可行性（每個 mu_i >= 0——但等式乘數 lambda_j 的符號不受限制），以及互補鬆弛（每個 mu_i g_i = 0）。這兩族乘數直接由上一份指南的多重約束機制推廣而來。

KKT conditions  (minimize f, constraints g_i(x) <= 0, h_j(x) = 0)

Lagrangian:   L = f + sum_i mu_i g_i + sum_j lambda_j h_j

  (1) stationarity           nabla_x L = nabla f + sum mu_i nabla g_i + sum lambda_j nabla h_j = 0
  (2) primal feasibility     g_i(x) <= 0   and   h_j(x) = 0       (stay legal)
  (3) dual feasibility       mu_i >= 0                            (lambda_j free in sign)
  (4) complementary slack    mu_i * g_i(x) = 0  for every i       (the switch)

Reading (4):  g_i < 0 (slack)  => mu_i = 0   (constraint idle)
              mu_i > 0         => g_i = 0     (constraint active, on the fence)

KKT 的四個模塊。平穩性與原始可行性你在等式情形已見過；對偶可行性（mu >= 0）與互補鬆弛（mu g = 0）才是不等式新添的部分。

動手做：逐一枚舉各情形

實踐中，互補鬆弛把一個帶不等式的問題變成了一次小小的有限搜索：對每個約束，你先猜它起作用還是不起作用，解出相應的等式系統，再用它沒有假定的那些條件來核驗這個猜測。來看一個乾淨的兩變量例子——極小化 f(x, y) = (x - 2)^2 + (y - 2)^2，即到點 (2, 2) 的距離平方，約束為 x + y <= 2。無約束的極小值顯然在 (2, 2)，但那裡 x + y = 4 > 2，不可行，所以圍欄必然咬住。約束是 g = x + y - 2 <= 0；我們檢驗它起作用的情形。

先猜約束不起作用（mu = 0）：則 nabla f = 0 給出 (x, y) = (2, 2)。檢驗可行性：x + y = 4，違反了 x + y <= 2。否決——內部情形不成立。
再猜約束起作用（g = 0）：寫下平穩性 nabla f + mu nabla g = 0。這裡 nabla f = (2(x - 2), 2(y - 2))、nabla g = (1, 1)，得到 2(x - 2) + mu = 0 與 2(y - 2) + mu = 0。
兩式相減得 x = y；再由起作用的約束 x + y = 2，迫使 x = y = 1。於是候選點為 (1, 1)。
解出乘數：2(1 - 2) + mu = 0 給出 mu = 2。檢驗對偶可行性：mu = 2 >= 0。通過。於是 (1, 1) 配 mu = 2 滿足每一條 KKT 條件，即為約束極小值。

圖景與代數完美吻合：半平面 x + y <= 2 中離目標 (2, 2) 最近的點，正是從 (2, 2) 向邊界直線所作垂線的垂足，即 (1, 1)；而正乘數 mu = 2 記錄著：把圍欄向外推，會讓你更靠近 (2, 2)——一次嚴格有益的放鬆，恰如一個非負影子價格應有的讀法。當約束有好幾個時，你會對「被宣布為起作用的約束」的每一個子集重複這套逐情形枚舉，但每一情形內部的邏輯完全相同。

必要、充分，與誠實的邊界

要精確說明 KKT 條件給出了什麼，因為這裡很容易誇大其詞。一般而言，這些條件是必要而非充分的：在一個真正的局部極小值處它們成立（所以任何極小值都是 KKT 點），然而一個點可以滿足全部四條而仍是極大值、鞍點，或僅僅是某個局部最優——這與第一卷無約束微積分裡的 nabla f = 0 如出一轍，後者標出了臨界點卻不告訴你它的類型。KKT 把搜索縮小到一份有限的候選清單上；你仍須逐一檢驗，才能找出真正的極小值點。

有兩點重要的告誡。第一，必要性本身需要一個溫和的正則性假設——約束規範（最常見的一種是：在該點處，起作用約束的梯度線性無關）。沒有它，即便在真正的極小值處乘數也可能不存在，於是 KKT 會悄悄漏掉它；這類退化的角點在實踐中罕見，卻真實存在。第二，也令人寬慰得多的是凸的情形：當 f 與每個 g_i 都是凸函數、且等式約束為線性時，KKT 條件就同時成為充分且必要的，任何滿足它們的點都是全局極小值，而非僅僅局部。這正是凸問題中局部對全局最優的焦慮得以蒸發的結構性原因，也是工程師與機器學習從業者把凸性看得幾乎高於一切的緣由。