嚴(yán)格局部解的二階充分條件證明

嚴(yán)格局部解的二階充分條件證明1內(nèi)容回顧f(x),gi(x),i=1,...,m

均為凸函數(shù)hi(x),i=1,...,l

為線性函數(shù)且

x?

是KKT點【即滿足五條性質(zhì)】，則

x?

是最優(yōu)解那么當(dāng)上述條件中1或2中有一個條件不滿足時，

x?

仍滿足是KKT點，什么情況下

x?

會使是最優(yōu)解呢？2.問題分析假設(shè)

x?

滿足KKT條件，則滿足▽f(x?)+∑i=1mλi▽gi(x?)+∑i=1lμi▽hi(x?)=0(1)λi≥0i=1,...,m(2)gi(x)≤0i=1,...,m(3)hi(x)=0i=1,...,l(4)λigi(x?)=0i=1,...,m(5)記一個新函數(shù)L(x)=f(x)+∑i=1mλigi(x)+∑i=1lμihi(x)其中

λi,μi

為KKT條件中的Lagrange系數(shù)由KKT條件中的

(1)

可得：

▽L(x?)=0由KKT條件中的

(4)(5)

可得：

L(x?)=f(x?)+∑i=1mλigi(x?)+∑i=1lμihi(x?)=f(x?)?x∈S,L(x)≤f(x)3.的證明：x∈S

，則

hi(x)=0,gi(x)≤0

，因此∑i=1lμihi(x?)=0又因為

i∈I,λi≥0,i?I,λi=0

，則∑i=1mλigi(x)≤0所以L(x)≤f(x)其他結(jié)論：由2,3可知，若

x?

是

L(x)

的最優(yōu)解，則

x?

是問題

(P)

的最優(yōu)解，并且這個最優(yōu)解可以是局部最優(yōu)解，也可以是全局最優(yōu)解證明：假設(shè)

x?

是全局最優(yōu)解，則

?x∈S,L(x?)≤L(x)

，由2,3可得f(x?)=L(x?)≤L(x)≤f(x)因此

x?是

f(x)

的全局最優(yōu)解同理可證若

x∈S∩Nδ(x?)

，則

x?

是局部最優(yōu)解假設(shè)

x?

是KKT點L(x)=f(x)+∑i=1mλigi(x)+∑i=1lμihi(x)則滿足

▽L(x?)=0

，由前面學(xué)習(xí)所學(xué)知識可以得若

▽2L(x)?0,?x∈S

，則

x?

是問題

(P)

的全局最優(yōu)解若

▽2L(x)?0,?x∈S∩Nδ(x?)

，則

x?

是問題

(P)

的局部最優(yōu)解若

▽2L(x?)?0

，則

x?

是問題(P)

的嚴(yán)格局部最優(yōu)解其中1,2是根據(jù)凸函數(shù)的性質(zhì)得到的，而3是無約束優(yōu)化問題的充分條件，由3可知?d≠0,dT▽2L(x?)d>0但在約束優(yōu)化中，并不要求對所有的

d

都成立。假設(shè)對

?d∈F1(x?)

成立，之所以選擇

F1(x?)

是因為其與集合

D(x?)

，

T(x?)

和

F(x?)

相比更直觀好判斷。因為目標(biāo)函數(shù)是求最小值，因此可以將

F1(x?)

中使目標(biāo)函數(shù)值上升的方向排除掉。再來回顧一下

F1(x?)

的定義：F1(x?)={d|▽gi(x?)Td≤0,i∈I,▽hi(x?)Td=0,i=1,...,l}由KKT條件可以得到

λi≥0當(dāng)

▽gi(x?)Td<0

時，沿著

d

方向gi(x)

值將變小，原來的約束條件為

gi(x)≤0

，

gi(x)

變小相當(dāng)于對不等式右端做了一個擾動變?yōu)間i(x)≤ε其中ε<0由上一節(jié)Lagrange乘子的意義可以得到目標(biāo)函數(shù)

f(x)

的值將改變

?λiε

，若

λi=0

，目標(biāo)函數(shù)值將不變，若

λi>0

，目標(biāo)函數(shù)值將變大

?λiε記I+={i|λi>0,i∈I}I0={i|λi=0,i∈I}則I=I+∪I0因此

F1(x?)

中明顯不可行的方向為▽gi(x?)Td<0且

λi>0

的方向，記

F1(x?)

排除不可行方向后的集合記為

F2(x?)

，則F2(x?)={d|▽gi(x?)Td≤0,i∈I0,▽gi(x?)Td=0,i∈I+,▽hi(x?)Td=0,i=1,...,l}同時可以得到

F2(x?)?F1(x?)3.二階充分條件千呼萬喚始出來，猶抱琵琶半遮面，前面鋪墊了這么多，終于要引出這一節(jié)最重要的二階充分條件！假設(shè)

x?

滿足KKT條件L(x)=f(x)+∑i=1mλigi(