拉格朗日乘子法(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)梯度的線性組合。
推薦閱讀：
