拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush-Kuhn-Tucker)条件是求解约束优化问题的重要方法，在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。前提是：只有当目标函数为凸函数时，使用这两种方法才保证求得的是最优解。
对于无约束最优化问题，有很多经典的求解方法，参见无约束最优化方法。
拉格朗日乘子法
先来看拉格朗日乘子法是什么，再讲为什么。
minf(x)s.t.hi(x)=0i=1,2...,n
这个问题转换为
min[f(x)+∑i=1nλihi(x)](1)
其中λi≠0，称为拉格朗日乘子。
下面看一下wikipedia上是如何解释拉格朗日乘子法的合理性的。
现有一个二维的优化问题：
minf(x,y)s.t.g(x,y)=c
我们可以画图来辅助思考。
绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f(x,y)的等高线。箭头表示斜率，和等高线的法线平行。
从图上可以直观地看到在最优解处，f和g的斜率平行。
▽[f(x,y)+λ(g(x,y)1)]=0λ≠0
一旦求出λ的值，将其套入下式，易求在无约束极值和极值所对应的点。
F(x,y)=f(x,y)+λ(g(x,y)c)
新方程F(x,y)在达到极值时与f(x,y)相等，因为F(x,y)达到极值时g(x,y)c总等于零。
(1)取得极小值时其导数为0，即▽f(x)+▽∑ni=1λihi(x)=0，也就是说f(x)和h(x)的梯度共线。
KKT条件
先看KKT条件是什么，再讲为什么。
letL(x,μ)=f(x)+∑qk=1μkgk(x)
其中μk≥0,gk(x)≤0
∵μk≥0gk(x)≤0}=>μg(x)≤0
∴
maxμL(x,μ)=f(x)(2)
∴
minxf(x)=minxmaxμL(x,μ)(3)
maxμminxL(x,μ)=maxμ[minxf(x)+minxμg(x)]=maxμminxf(x)+maxμminxμg(x)=minxf(x)+maxμminxμg(x)
又∵μk≥0gk(x)≤0}=>minxμg(x)={0∞ifμ=0org(x)=0ifμ>0andg(x)<0
∴maxμminxμg(x)=0此时μ=0org(x)=0
∴maxμminxL(x,μ)=minxf(x)+maxμminxμg(x)=minxf(x)(4)
此时
μ=0org(x)=0联合(3),(4)我们得到minxmaxμL(x,μ)=maxμminxL(x,μ)
亦即L(x,μ)=f(x)+∑qk=1μkgk(x)μk≥0gk(x)≤0=>minxmaxμL(x,μ)=maxμminxL(x,μ)=minxf(x)
我们把maxμminxL(x,μ)称为原问题minxmaxμL(x,μ)的对偶问题，上式表明当满足一定条件时原问题、对偶的解、以及minxf(x)是相同的，且在最优解x处μ=0org(x)=0。把x代入(2)得maxμL(x,μ)=f(x)，由(4)得maxμminxL(x,μ)=f(x)，所以L(x,μ)=minxL(x,μ)，这说明x也是L(x,μ)的极值点，即L(x,μ)x|x=x=0。
最后总结一下：
L(x,μ)=f(x)+∑qk=1μkgk(x)μk≥0gk(x)≤0=>minxmaxμL(x,μ)=maxμminxL(x,μ)=minxf(x)=f(x)μkgk(x)=0L(x,μ)x|x=x=0
KKT条件是拉格朗日乘子法的泛化，如果我们把等式约束和不等式约束一并纳入进来则表现为：
L(x,λ,μ)=f(x)+∑ni=1λihi(x)+∑qk=1μkgk(x)λi≠0hi(x)=0μk≥0gk(x)≤0=>minxmaxμL(x,λ,μ)=maxμminxL(x,λ,μ)=minxf(x)=f(x)μkgk(x)=0L(x,λ,μ)x|x=x=0
注：x,λ,μ都是向量。
L(x,λ,μ)x|x=x=0表明f(x)在极值点x处的梯度是各个hi(x)和gk(x)梯度的线性组合。
