第五章-01 約束最優(yōu)條件

1、1 Chapter 5 Chapter 5 約約 束束 問問 題題 的的 最最 優(yōu)優(yōu) 性性 條條 件件南京郵電大學(xué)南京郵電大學(xué) 信息與計算科學(xué)系信息與計算科學(xué)系2數(shù)學(xué)模型數(shù)學(xué)模型min f(x)s.t. s1(x) 0sm(x) 0h1(x)=0hl(x)=0 與無約束問題中有一階必要條件f(x)=0一樣，在約束問題中我們也要找出這種問題的最優(yōu)解必須滿足的條件，從而決定迭代過程何時終止！31.1.基本概念基本概念起作用約束起作用約束（有效約束） 對容許點(diǎn) 來說，若有不等式約束si(x) 0變成等式，即si( )=0,則該不等式約束稱為關(guān)于容許點(diǎn) 的一個起作用約束；若si( )0則稱之為這個容許

2、點(diǎn)的不起作用約束。xxx則對點(diǎn)(1,0)T來說1，4為有效約束，2，3為不起作用約束ABx1x2P例例：某問題的約束函數(shù)分別為：s1(x)=1-x12-x22 0s2(x)=x1-x2 0s3(x)=x1 0s4(x)=x2 04易見易見：不等式約束關(guān)于容許集的任意內(nèi)點(diǎn)都是不起作用約束只有邊界上的點(diǎn)才可能使得某個或某些不等式約束有效按照定義可見，任一等式約束關(guān)于容許點(diǎn)都是起作用約束任一等式約束關(guān)于容許點(diǎn)都是起作用約束容許方向（可行方向）容許方向（可行方向） Rn中的一個非空點(diǎn)集D，x D，若對某個非0向量p，存在一個小正數(shù)，對t(0, ),總有x+tp D（容許容許方向方向只與約束函數(shù)有關(guān)只與

3、約束函數(shù)有關(guān)）x5容許下降方向容許下降方向 方向d既是點(diǎn)x處的容許方向，又是點(diǎn)x處的下降方向(1)如果某點(diǎn)x不是極小點(diǎn)，則繼續(xù)尋優(yōu)時的搜索方向就應(yīng)該從該點(diǎn)的一個可行下降方向上去找（因?yàn)檫@樣就既保證函數(shù)值的下降，又能確保找到的好點(diǎn)是一個可行的）(2)如果某點(diǎn)x*是一個極小點(diǎn)，則在該點(diǎn)就不會有可在該點(diǎn)就不會有可行下降方向行下降方向。因否則若有的話比如d，則x*沿著d稍微走一點(diǎn)點(diǎn)就會得到一個可行點(diǎn)，且該點(diǎn)的函數(shù)值必x*的函數(shù)值小。這當(dāng)然與x*為極小點(diǎn)矛盾！62.2.不等式約束問題的最優(yōu)性條件不等式約束問題的最優(yōu)性條件引理引理設(shè)不等式約束問題不等式約束問題的可行域?yàn)镈=x|si(x) 0,i=1:mx

4、為任一容許點(diǎn), 記I=i|si(x)=0,i=1:m當(dāng)iI,si(x)在x處有一階偏導(dǎo)數(shù)，且si(x)Td0當(dāng)iI,si(x)在x處連續(xù), 則d是x處的一個容許方向Proof對i I：由-si(x)Tp0知:p是函數(shù)-si(x)在x點(diǎn)處的下降方向。從而存在一個小正數(shù)i，對t(0, i),總有-si(x+tp)0對iI, si(x)0, 由si(x)在x處連續(xù)，故存在一個小正數(shù)i ,使t(0, i) ,均有si(x+tp)0取=min1, m,對t(0, ) ,均有si(x+tp)0,i=1:m。7Ii 00pxspxfTiT*)(*)(由這個引理可知道若x*是一個極小點(diǎn)， 則在x*處不會有方向

5、p 滿足也就是說，這個不等式組必?zé)o解。8Kuhn-Tucker(Kuhn-Tucker(庫恩庫恩- -塔克塔克) )定理定理設(shè)x*為不等式約束問題的一個極小點(diǎn)函數(shù)f(x),s1(x),sm(x)在x*處都有一階偏導(dǎo)數(shù)I=i|si(x*)=0,i=1:m， 當(dāng)iI,si(x*)線性無關(guān)則存在實(shí)數(shù)1, m，滿足：f(x*)- 1s1(x*)+ 2s2(x*)+ msm(x*)=0isi(x*)=0,i=1:mi0,i=1:mK-TK-T條件條件9Proof即Ii *)(*)(00pxspxfTiTIi *)(*)(00pxspxfTiT因x*是極小點(diǎn)，故不等式組無解。不等式組a(i) Tb0)則由

6、0f(x*)-i si(x*)=0,iI知si(x*)， iI,線性相關(guān),與已知矛盾！這樣在上式兩端同時除以0f(x*)-(i /0 ) si(x*)=0即得結(jié)論。滿足K-T條件的點(diǎn)稱為K-TK-T點(diǎn)點(diǎn)。事實(shí)上,若0為0,1111010412111)(,)(,)()()()(xsxsxf例例min f(x)=(x1-2)2+x22 s.t. s1(x)=x1-x220 s2(x)=-x1+x20對點(diǎn)x(1)=(0,0)T,在該點(diǎn)處s1(x),s2(x)都是起作用約束，在該點(diǎn)處f,s1,s2的梯度分別是故x(1)必不是K-T點(diǎn), 011010421設(shè)004221,即00421,解得1211212

7、222212)(,)(,)(xsxsxfmin f(x)=(x1-2)2+x22s.t. s1(x)=x1-x220 s2(x)=-x1+x20對點(diǎn)x(2)=(1,1)T, 在該點(diǎn)處s1(x),s2(x)都是起作用約束在該點(diǎn)處f,s1,s2的梯度分別是故x(2)是K-T點(diǎn), 011212221設(shè)022022121,即2021,解得133. 3.一般約束問題的最優(yōu)性條件一般約束問題的最優(yōu)性條件將一般約束問題中的等式約束換成是hj(x) 0,-hj(x) 0從而原問題就成為一個不等式約束問題。設(shè)x*為混合約束問題的一個極小點(diǎn)，函數(shù)f(x),s1(x),sm(x), h1(x), hl(x)在x*處都有一階偏導(dǎo)數(shù)當(dāng)h1(x*), hl(x*),si(x*)(iI)線性無關(guān)，則存在實(shí)數(shù)1, m,1, ,l使得f(x*)- 1s1(x*)+ 2s2(x*)+ msm(x*) - 1h1(x*)+ 2h2(x*)+ lhl(x*) =0isi(x*)=0,i=1:mi0,i=1:m(即j可正可負(fù)，但i必非負(fù))Kuhn-TuckerKuhn-Tuck