在解決最優化問題時候， Fermat 在1629年就解決了無限制最小問題， 但是一直過了靠近160年， 才有Lagrange解決等式約束的最值問題， 然後再過了160左右， 出現了四個人， Karush, John, Kuhn, 和Tucker， 他們解決了不等式約束最值問題， 這裡講的就是Fritz John, FJ是如何單挑其他三人, Karush, Kuhn, Tucker, KKT的。
FJ是什麼？
FJ是1個人的姓名的首字母， 是Fritz John, FJ，出生德國的數據家， 把偏微分方程 partial differential equations, PDE 玩的出神入化的一個人。 大家可能都沒有聽說過他， 但是他的黯然銷魂掌練出了FJ條件（conditions）， 這掌不輸於武林絕學KKT條件。 一般來說， 玩偏微分方程出生的都是牛銀， 譬如，某種意義上， 算是我的校友的，Leslie Lamport, LL, 就是搞偏微分方程出身的。 不認識LL的， 我就說幾個關鍵詞吧， Latex的La， 拜佔庭將軍問題Byzantine Generals Problem， 2013年圖靈獎。好吧， 說PDE說的激動了。
KKT是什麼？
KKT是3個人的姓的首字母， 分別是Karush, Kuhn和Tucker， 最早是有Kuhn和Tucker在1951年總結發表的， 但是後來人們發現Karush在1939年碩士論文中就發現了這個必要條件（necessary conditions）。 碩士就能做出這樣的成就也是非常不容易！ 但是由於參與了美國的曼哈頓計劃（Manhattan Project），使得Karush本人對名利追求並不熱衷，而追求和平，他對Karush和Tucker的定理的命名權並不放在心上。 以至於KT條件在10年後才重命名為KKT條件。
KKT條件（Condition）是什麼？
KKT條件是有不等式條件(inequality constrained problem)最值的充要條件（necessary & sufficient conditions）。這是對Stationary Point最值理論和Lagrange Muliplier最值理論的進一步泛化（Generalization）。
無條件(unconstraind problem)
我們先回顧一下， 無條件(unconstraind problem)最值的充要條件。
要注意的就是， 就是鞍點saddle point需要被排除。
等式限制條件（equality constrained condition）
其次， 等式限制條件（equality constrained condition）最值的充要條件。
可以看到只是把限制條件改變成了對拉格朗日量（lagrangian）梯度為零的情況。
等價於目標函數的梯度（或者導數）Gradient 和限制條件的梯度（Jacobian）在同一直線上（或者成縮放關係）
這裡面有兩個概念一個是雅克比矩陣Jacobian Matrix， 另外一個是零空間Null Space。 雅克比矩陣是一個點附近利用梯度替代曲線的本地線性化（local linearization）。
零空間，是對矩陣Ax=0的解空間， 零空間的更多細節參考「矩有四子」.
進一步理解雅克比矩陣的含義如下：
不等式限制條件（inequality constrained condition）
然後， 不等式限制條件（inequality constrained condition）最值的充要條件。
我們可以看到對比等式情況， 首先增加了對於 λ, lamda 與約束條件之間的關係限制。
等式和不等式並存的限制條件 （equality and inequality constrained condition）
如果把上面兩個不等式情況結合起來就是，我們討論的KKT條件情況下的充要關係。
KKT要注意約束規格（constraint qualification）！
從上面可以看到， KKT條件是必要條件， 並非充分條件， 如果要變成充分條件還要加上約束規格(constraint qualification)的成立。
這個特別要注意的， 這在美國空軍B-2高空轟炸機（B-2 Stealth bomber）的設計上曾經出現過設計事故。 在1980年左右， 處於裡根時代， 在設計的時候對， 空間在機翼機身分布， 燃油， 速度， 推進器（thrust）都有很大的要求。
並且存在一個最值目標： 滿油箱狀態要飛得最遠。 B-2發明之前， 其實已經有B-29和B-52機型的存在了。 很幸運， B-2找到一個KKT解， 這個解導致飛機機身極度壓縮， 使得飛機幾乎由兩個機翼組成。 飛機設計完成後， 實際測試的時候， 發現這個機型和B-29，B-52相比， 滿油箱狀態卻飛得很短。 然後就花費了上億經費驗證設計， 沒有找到設計模型上的問題。 設計模型是對的， 那為啥飛行距離很短呢？ 又花費了很多經費， 最終發現， 這個模型是一個非凸非線性模型（nonconvex nonlinear programming, nonconvex NLP）， 最後發現， 最優解其實要求機翼很小， 好比客機那樣。 所以KKT解是一個在空氣動力學（aerodynamically）上幾乎是最差勁的選擇。 但是最後B-2還是投入實用了， 為啥， 因為發現B-2有個極好的特性， 雷達很難捕捉到， 隱身功能。
什麼是全局最優解的約束規格(constraint qualification)？
雖然前面給出了代數上的表達式來給定KKT的充要條件（局部最優，local optimum）， 但是如果直接按約束規格來描述的話， 就需要了解凸函數的特性。凸函數， 可以有凸函數和嚴格凸函數， 它們之間的差異是有沒有等式。 偽凸函數（pseduoconvex）， 就是只要滿足通過導數能求最值的函數， 並不一樣要求凸函數。 還有半凸函數（quasiconvex），如下圖所示：
基於不同的凸函數的性質， 滿足KKT條件，是不是全局最優（global optimum）有如下的約束規格（constraint qualification， CO）：
幾何理解
為什麼要有 dual feasibility （ λ） >= 0？
首先，要注意λ的符號，根據Lagrange Stationarity限制， 可以知道是有-∇f與∇h方向一致不一致性來定義的。 λ>0 意味中-∇f與∇h方向一致。
另外， 因為要求最小值， 那麼根據梯度下降（gradient descent）的含義，我們就是要沿著梯度的負方向（-∇f）上走到底。
其次， 我們看一下等式限制（equality constraint）的情況， 這時候因為限制是在那條線上，所以λ的符號（-∇f與∇h方向一致不一致性）並不重要。因為只要所在直線定了， 再加上h(x)=0線的固定， 那麼對應極值點就定了。
但是在不等式限制（inequality contraint）下， λ的符號（-∇f與∇h一致性）就很重要啦。當g(x)<0， 那麼根據梯度下降， 在-∇f方向走到底， 但是必須在g(x)的可行域（feasible region）裡，這樣要在邊界取到最值， 那只能如圖所示-∇f方向指向區域外面， 這樣-∇f就固定了， 那麼在根據∇g的方向（指向g(x)大的一邊）， 來判斷λ的符號（-∇f與∇g一致性）。
所以只要g(x)<=0那麼，就要求λ>=0。 但是為什麼前面總結的c(x)>=0,還要求λ>=0呢？ 那是因為他們的拉格朗日量（lagrangian）寫的不一致。
所以相當於 -c(x)<=0。 這下理解為什麼dual feasibility的幾何意義了吧。
如何理解Complementary Slackness？
首先我們要比較一下對偶問題 duality， 有如下結論：maxi-min <= mini-max。
矮子裡面選高個 <= 高個裡面選矮子。 矮子再怎麼選都是矮子， 高個再怎麼挑也是高個， 矮子不能高於高個。
根據對偶問題， 很容易就知道弱對偶weak duality始終成立， 但是如果強對偶strong duality成立的話， 就會帶來complementary slackness性質， 反之， 也是成立的。
所以Complementary slackness其實是保證強對偶成立的條件。
假設圖示， 我們有兩個關係g(x)<=0 和 h(x)=0， 我們很容易找到primal問題的最優點，就是z左邊部分的最低點。
這時候我們再來看對偶問題maxi-min，我們先看求解最小的部分， 我們看到如果在線上表示， 過可行域裡面的任意點， 然後L=z+uy， 其中y=0的時候， z=f(x)， 那麼最優解就是直線與z軸的交點。 如果要最小化, 就要把先移到切線邊上， 這樣截距最下最小。
然後我們看要使得這個切線的截距最大， 就必須調整斜率u，使得它剛好是最低點的切線，這樣我們發現求到的maxi-min點和之前primal問題裡面的mini-max點一樣。 根據我們前面的定義， 這是強對偶strong duality的情況。
那我們就要比較， 當什麼時候不一樣了， 我們發現當不是凸的區域的時候， 這時候maxi-min的解要比mini-max的解小。 所以這時候對應的weak duality。
這樣我們進一步理解了， 什麼時候complementary slackness滿足的話， 實現了強對偶， 而一個凸的問題， 能使得complementary slackness成立。
FJ 和 KKT 的證明
一般情況下， FJ和KKT的證明比較類似， 主流的證明，需要利用到一下Farkas Lemma，或者Gordan Theorem， 本身這些定理也需要證明。
但是， 奧爾迦.布列內娃 Olga, Brezhneva，這位來自俄羅斯的美女博士，她非常希望能夠利用很簡單的知識來證明Lagrange 和 KKT 定理， 最終她發現， 如果把KKT的適用範圍稍微縮小一點（排除了， KKT對於不可導，但是次可導subdifferential的函數的適用性）， 可以有很簡單的證明， 她最終做到了， 是不是看上去很美！！！
她的這個工作，得到了最優化工作的四大天王之一的北丐（Stephen Wright）的賞識。以後有時間希望把她的工作也囊括進來。
FJ條件（Condition）是什麼？
FJ條件是也是針對等式和不等式同時約束的最優問題的條件。 並且，FJ條件也是必要條件（necessary conditions）， 和KKT類似保護了3種條件， primal feasibility， dual feasibility和complementary slackness。
FJ vs KKT
前面， 我們大概了解了FJ和KKT的工作性質， 那麼對比一下FJ和KKT工作的差異呢？
最大的差異就是FJ不如KKT嚴格， 根據前面說過的， 我們知道在線性規劃（Linear Programming）中， 滿足KKT條件，那麼一定是最優解（Optimum）， 但是LP中滿足FJ條件，卻不一定是最優解。
也正是因為FJ要比KKT稍微寬鬆一點， 所以導致人們選擇了KKT條件， 以至於有些人都沒有聽過FJ條件。
但是並不是說FJ條件就可以不要了。 因為KKT條件更嚴格就導致它的適用範圍不如FJ條件廣泛， 舉個例子如下， 很明顯這個情況中， FJ適用，但是KKT就不適用了。
主要原因就是KKT是FJ的約束規格（constraint qualification）下的例子， 這個約束規格就是要求限制條件（constraint conditions）在最值點optimum的偏導數之間是線性獨立的（linearly independent）， 如前圖所示。 而上面的例子可以看到在最優點的導數向量之間成反比， 負相關的， 不獨立。 所以FJ適用，但是KKT不適用了。
小結，這裡簡單總結了下， KKT條件中dual feasibility, complementary slackness的含義， 同時簡單對比了FJ 條件和KKT條件的差異。 讓我們看到一個牛掰的， 1挑3的FJ， 但同時也感嘆， FJ如果進一步細化， 或許今天廣泛應用的就是FJ系統（System）了！
附錄：
最優化之 東邪西毒 南帝北丐
東邪 Dimitri Bertsekas MIT
西毒 Stephen P. Boyd Stanford University
南帝 Andrzej Ruszczyński Rutgers University
北丐 Stephen J. Wright, University of Wisconsin
郭靖 Mark Schmidt, University of British Columbia
中神通 Werner Fenchel
中頑童 Jean Jacques Moreau
參考：
http://www.math.ucla.edu/~lvese/273.1.06f/Summary.pdf
https://www.math.uh.edu/~rohop/fall_06/Chapter3.pdf
https://ocw.mit.edu/courses/mechanical-engineering/2-854-introduction-to-manufacturing-systems-fall-2010/lecture-notes/MIT2_854F10_kkt_ex.pdf
https://www.cs.cmu.edu/~ggordon/10725-F12/slides/16-kkt.pdf
http://math.stackexchange.com/questions/19560/difference-between-fritz-john-and-karush-kuhn-tucker-conditions
http://www.math.chalmers.se/Math/Grundutb/CTH/tma947/1011/lecture5.pdf