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

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

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

為線性函數(shù)且

x?

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

x?

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

x?

仍滿足是KKT點(diǎn)，什么情況下

x?

會(huì)使是最優(yōu)解呢？2.問(wèn)題分析假設(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)記一個(gè)新函數(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又因?yàn)?/p>

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?

是問(wèn)題

(P)

的最優(yōu)解，并且這個(gè)最優(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點(diǎn)L(x)=f(x)+∑i=1mλigi(x)+∑i=1lμihi(x)則滿足

▽L(x?)=0

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

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

，則

x?

是問(wèn)題

(P)

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

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

，則

x?

是問(wèn)題

(P)

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

▽2L(x?)?0

，則

x?

是問(wèn)題(P)

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

d

都成立。假設(shè)對(duì)

?d∈F1(x?)

成立，之所以選擇

F1(x?)

是因?yàn)槠渑c集合

D(x?)

，

T(x?)

和

F(x?)

相比更直觀好判斷。因?yàn)槟繕?biāo)函數(shù)是求最小值，因此可以將

F1(x?)

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

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

時(shí)，沿著

d

方向gi(x)

值將變小，原來(lái)的約束條件為

gi(x)≤0

，

gi(x)

變小相當(dāng)于對(duì)不等式右端做了一個(gè)擾動(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?)

中明顯不可行的方向?yàn)楱実i(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}同時(shí)可以得到

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

x?

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