KKT條件第一項是說最優點必須滿足所有等式及不等式限制條件,也就是說最優點必須是一個可行解,這一點自然是毋庸置疑的。第二項表明在最優點 x*, ?f 必須是 ?hj 和 ?gk 的線性組合,和都叫作拉格朗日乘子。所不同的是不等式限制條件有方向性,所以每一個 kμ都必須大於或等於零,而等式限制條件沒有方向性,所 以 jλ沒有符號的限制,其符號要視等式限制條件的寫法而定。
設想我們優化如下的目標函數:
minimize? ? f_0(x)
s.t.? ?? ???f_i(x)<=0,??i=1,2,...,m
h_i(x)=0,? ?i=1,2,...,p
我們把這個目標函數稱為原函數
構造該函數的對偶函數如下:
maximize
g(r,v)=inf_x {f_0(x)+sum_{i=1}^m r_i*f_i(x)+sum_{i=1}^p v_i*h_i(x)}
s.t.? ? r_i>=0??i=1,2,...,m
假設x'是原函數的一個可行點(滿足原函數的約束),r',v'是對偶函數的一個可行點
因為r'_i>=0,f_i(x')<=0,所以sum_{i=1}^m r'_i*f_i(x')<=0,同理
sum_{i=1}^p v'_i*h_i(x')=0
因此,我們有,對于任意的滿足原函數約束的x和滿足對偶函數約束的r,v
g(r,v)<={f_0(x)+sum_{i=1}^m r_i*f_i(x)+sum_{i=1}^p v_i*h_i(x)}
<=f_0(x)
記x^* 為原函數的一個最優點,最優值為p^*
r^*,v^*為對偶函數的一個最優點,最優值為d^*
我們有
p^*>=d^*(weak duality)
如果x^*,r^*,v^*能夠使得p^*=d^*成立,
則稱strong duality成立,即
f_0(x^*)=g(r^*,v^*)
現在假設strong duality能夠成立,并且假設x^*是原函數的最優解,r^*,v^*為對偶函數
的一個最優點,那么
f_0(x^*)=g(r^*,v^*)
=inf_x {f_0(x)+sum_{i=1}^m r^*_i*f_i(x)+sum_{i=1}^p v^*_i*h_i(x)}
<=f_0(x^*)+sum_{i=1}^m r^*_i*f_i(x^*)+sum_{i=1}^p v^*_i*h_i(x^*)
<=f_0(x^*)
第一個等式是strong duality,第二行等式是對偶函數的定義,第三行不等式是inf的定
義,第四行不等式是因為r^*_i>=0,f_i(x^*)<=0,h_i(x^*)=0
因此,我們有sum_{i=1}^m r^*_i*f_i(x^*)=0,
因為對每個i, r^*_i*f_i(x^*)<=0,
所以有
r^*_i*f_i(x^*)=0(Complementary slackness)
因為x^*是使得g(r^*,v^*)最小的點,(注意上面的第三行等式成立)
所以g(r^*,v^*)關于x的導數在x^*處為0
f_0'(x^*)+sum_{i=1}^m r^*_i*f_i'(x^*)+sum_{i=1}^p v^*_i*h_i'(x^*)=0
綜上所述我們得到了f_0(x^*)=g(r^*,v^*)的條件:
f_i(x^*)<=0? ???i=1,2,...,m
h_i(x^*)=0? ?? ?i=1,2,...,p
r^*_i>=0? ?? ???i=1,2,...,m
r^*_i*f_i(x^*)=0? ? i=1,2,...,m
f_0'(x^*)+sum_{i=1}^m r^*_i*f_i'(x^*)+sum_{i=1}^p v^*_i*h_i'(x^*)=0
這就是KKT條件~~
以上是摘自Information Retrieval Blog的部分內容,希望對你能有點點啟發~~