1. 從線性規(guī)劃到凸優(yōu)化
線性規(guī)劃相對比較簡單，比如：
min y = x1 + x2
s.t. x1 + 3*x2 ≥ 5
2*x1 + x2 ≥ 6
x1,x2≥0
求解步驟嘛，首先添加剩余變量x3消除不等式約束，將問題轉(zhuǎn)化為：
max y = x1 + x2
s.t. x1 + 3*x2 - x3 = 5
2*x1 + x2 - x3 = 6
x1,x2,x3≥0
然后使用消元法：
x1 =(13 + 2*x3)/5 ,x2 = (4 + x3)/5
帶入目標(biāo)函數(shù)，得到
min y = (17 + 3*x3)/5
顯然在x3 = 0時(shí)取得最優(yōu)值 y = 3.4，對應(yīng)的x1 = 2.6, x2 = 0.8。
如果變量出現(xiàn)二次方，三次方怎么辦？這時(shí)候問題變?yōu)榱恕胺蔷€性規(guī)劃”，對于這類問題，我們能求解的范圍是有限的，一般都要求目標(biāo)函數(shù)和約束條件是“凸函數(shù)”（什么是凸函數(shù)？請參考https://blog.csdn.net/xueyingxue001/article/details/51858037），這時(shí)候的優(yōu)化問題稱為“凸優(yōu)化”問題。
2. 最簡單的凸優(yōu)化問題
只有目標(biāo)函數(shù)，沒有約束條件。比如：
min y = x^2
求解方法就是對x求導(dǎo)，在導(dǎo)數(shù)為0處取得最優(yōu)值：
y'|x = 0
=> 2*x = 0
=> x = 0
=> 最優(yōu)值 y = x^2 = 0
3. 拉格朗日乘子法
如果問題有約束條件怎么辦？比如在上面問題的基礎(chǔ)上，加上等式約束條件：
min y = x^2
s.t. x = 2
可以使用拉格朗日乘子法是將等式（注意是等式！等式?。┘s束條件去除，比如上面的問題可以轉(zhuǎn)化為：
min y = x^2 + λ * (x - 2)
這里引入了新的變量λ。求解方法：對變量x和λ求導(dǎo)：
y'|x = 0, y'|λ = 0
=> 2*x + λ = 0, x - 2 = 0
=> x = 2, λ = -4
=> 最優(yōu)值 y = x^2 = 4
4. 來個(gè)復(fù)雜點(diǎn)的例子
上面的例子有點(diǎn)簡單過頭了，下面來個(gè)稍微復(fù)雜點(diǎn)的：
min y = x1^2 + x2^2
s.t. x1 + x2 = 2
首先來看看我們都會用的方法——消元法：
將約束條件轉(zhuǎn)化為 x2 = 2 - x1，代入目標(biāo)函數(shù)
=> min y = x1^2 + (2-x1)^2 = 2*x1^2 - 4*x1 + 8，成功消除約束條件
在導(dǎo)數(shù)為0處取得最優(yōu)值：
y'|x1 = 0
=> 4*x1 - 4 = 0
=> x1 = 1
=> x2 = 1, 最優(yōu)值 y = 2
再來看新介紹的方法——拉格朗日乘子法：
將約束條件乘上一個(gè)新變量代入目標(biāo)函數(shù)
=> min L = x1^2 + x2^2 + λ*(x1+x2-2)，成功消除約束條件
在導(dǎo)數(shù)為0處取得最優(yōu)值
L'|x1 = 0,L'|x2 = 0, L'|λ = 0
=> 2*x1 + λ = 0, 2*x2 + λ = 0, x1+x2 - 2 = 0
=> x1 = 1, x2 = 1, λ = -2, 最優(yōu)值 y = 2
拉格朗日乘子法好麻煩，為什么要用這個(gè)方法？因?yàn)椤覀冞€會碰到難以消元的情形，比如約束條件里面帶著2次方的問題：
min y = x1^2 + x2^2
s.t. x1^2 + 3*x1 + x2^2 - 4*x2 = 2
這種情況下，用拉格朗日乘子法消除約束條件更合適。
4. 不等式約束下的KKT條件
如果約束條件中有不等式約束怎么辦？添加不等式約束后問題變?yōu)椋?/p>
min y =f(x)
s.t. g(x) ≤ 0
添加變量s（后面會把s消除掉的），并使用拉格朗日乘子法將約束轉(zhuǎn)入目標(biāo)函數(shù)：
min L =f(x) + λ*(g(x) + s^2)
最優(yōu)解需滿足：
（1）L'|x = 0 => f' + λ*g' =0
（2）L'|λ = 0 => g + s^2 = 0
（3）L'|s = 0 => λ*s = 0
(2)和(3)等價(jià)于：g≤0, λ*g = 0（這里是關(guān)鍵！關(guān)鍵！），條件變?yōu)椋?/p>
（1）L' = 0（定常方程）
（2）g ≤ 0（原始可行）
（3）λ*g = 0（互補(bǔ)剩余）
另外，為了使得min存在，還需要有
（4）λ ≥ 0（對偶可行）
簡單來說，λ ≥ 0的意思是最優(yōu)值必須在約束條件構(gòu)成的可行域范圍內(nèi)。關(guān)于對偶可行的圖解，可以參考https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
以上稱為KKT條件。KKT條件將lagrange乘子法中的等式約束優(yōu)化問題推廣至不等式約束。在凸優(yōu)化的情況下，KKT條件是取得最優(yōu)解的充要條件。
5. 如果不等式和等式混合在一起……
假設(shè)問題既包含等式約束，也包含不等式約束：
min y =f(x)
s.t. g(x) ≤ 0
h(x) = 0
KKT條件加上h(x) = 0就行了：
（1）L' =0（定常方程）
（2）g ≤ 0, h = 0（原始可行）
（3）λ*g = 0（互補(bǔ)剩余）
（4）λ ≥ 0（對偶可行）
6. 最后來個(gè)超簡單的例子
min y = x^2
s.t. x + 1 ≤ 0
使用拉格朗日乘子法，目標(biāo)函數(shù)變?yōu)?/p>
min L = x^2 + λ*(x+1)
使用KKT條件，問題轉(zhuǎn)化為求解：
（1）L' =0 => 2*x+λ = 0
（2）g ≤ 0 => x ≤ -1
（3）λ*g = 0 => λ*(x+1) = 0
（4）λ ≥ 0
若λ = 0，由(1)得到x = 0，不滿足(2)；
若λ ≠ 0，由(3)得到x = -1，由(1)得到λ = 2，滿足所有4個(gè)條件，此時(shí)最優(yōu)值y = 1。
