1. 从线性规划到凸优化

线性规划相对比较简单，比如：

min y = x1 + x2
s.t. x1 + 3*x2 ≥ 5
     2*x1 + x2 ≥ 6
    x1,x2≥0

求解步骤嘛，首先添加剩余变量x3消除不等式约束，将问题转化为：

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

带入目标函数，得到

min y = (17 + 3*x3)/5

显然在x3 = 0时取得最优值 y = 3.4，对应的x1 = 2.6, x2 = 0.8。
如果变量出现二次方，三次方怎么办？这时候问题变为了“非线性规划”，对于这类问题，我们能求解的范围是有限的，一般都要求目标函数和约束条件是“凸函数”（什么是凸函数？请参考https://blog.csdn.net/xueyingxue001/article/details/51858037），这时候的优化问题称为“凸优化”问题。

2. 最简单的凸优化问题

只有目标函数，没有约束条件。比如：

min y = x^2

求解方法就是对x求导，在导数为0处取得最优值：

y'|x = 0
=> 2*x = 0
=> x = 0
=> 最优值 y = x^2 = 0

3. 拉格朗日乘子法

如果问题有约束条件怎么办？比如在上面问题的基础上，加上等式约束条件：

min y = x^2
s.t. x = 2

可以使用拉格朗日乘子法是将等式（注意是等式！等式！）约束条件去除，比如上面的问题可以转化为：

min y = x^2 + λ * (x - 2)

这里引入了新的变量λ。求解方法：对变量x和λ求导：

y'|x = 0, y'|λ = 0
=> 2*x + λ = 0, x - 2 = 0
=> x = 2, λ = -4
=> 最优值 y = x^2 = 4

4. 来个复杂点的例子

上面的例子有点简单过头了，下面来个稍微复杂点的：

min y = x1^2 + x2^2
s.t. x1 + x2 = 2

首先来看看我们都会用的方法——消元法：

将约束条件转化为 x2 = 2 - x1，代入目标函数
=> min  y = x1^2 + (2-x1)^2 = 2*x1^2 - 4*x1 + 8，成功消除约束条件
在导数为0处取得最优值：
y'|x1 = 0
=> 4*x1 - 4 = 0
=> x1 = 1
=> x2 = 1, 最优值 y = 2

再来看新介绍的方法——拉格朗日乘子法：

将约束条件乘上一个新变量代入目标函数
=> min L = x1^2 + x2^2 + λ*(x1+x2-2)，成功消除约束条件
在导数为0处取得最优值
L'|x1 = 0,L'|x2 = 0, L'|λ = 0
=> 2*x1 + λ = 0, 2*x2 + λ = 0, x1+x2 - 2 = 0
=> x1 = 1, x2 = 1, λ = -2, 最优值 y = 2

拉格朗日乘子法好麻烦，为什么要用这个方法？因为……我们还会碰到难以消元的情形，比如约束条件里面带着2次方的问题：

min y = x1^2 + x2^2
s.t. x1^2 + 3*x1 + x2^2 - 4*x2 = 2

这种情况下，用拉格朗日乘子法消除约束条件更合适。

4. 不等式约束下的KKT条件

如果约束条件中有不等式约束怎么办？添加不等式约束后问题变为：

min y =f(x)
s.t. g(x) ≤ 0

添加变量s（后面会把s消除掉的），并使用拉格朗日乘子法将约束转入目标函数：

min L =f(x) + λ*(g(x) + s^2)
最优解需满足：
（1）L'|x = 0 => f' + λ*g' =0
（2）L'|λ = 0 => g + s^2 = 0
（3）L'|s = 0 => λ*s = 0

(2)和(3)等价于：g≤0, λ*g = 0（这里是关键！关键！），条件变为：

（1）L' = 0（定常方程）
（2）g ≤ 0（原始可行）
（3）λ*g = 0（互补剩余）

另外，为了使得min存在，还需要有

（4）λ ≥ 0（对偶可行）

简单来说，λ ≥ 0的意思是最优值必须在约束条件构成的可行域范围内。关于对偶可行的图解，可以参考https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
以上称为KKT条件。KKT条件将lagrange乘子法中的等式约束优化问题推广至不等式约束。在凸优化的情况下，KKT条件是取得最优解的充要条件。

5. 如果不等式和等式混合在一起……

假设问题既包含等式约束，也包含不等式约束：

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（互补剩余）
（4）λ ≥ 0（对偶可行）

6. 最后来个超简单的例子

min y = x^2
s.t. x + 1 ≤  0

使用拉格朗日乘子法，目标函数变为

min L = x^2 + λ*(x+1)

使用KKT条件，问题转化为求解：

（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个条件，此时最优值y = 1。