第五章-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.基本概念基本概念起作用約束起作用約束（有效約束） 對容許點 來說，若有不等式約束si(x) 0變成等式，即si( )=0,則該不等式約束稱為關(guān)于容許點 的一個起作用約束；若si( )0則稱之為這個容許

2、點的不起作用約束。xxx則對點(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)點都是不起作用約束只有邊界上的點才可能使得某個或某些不等式約束有效按照定義可見，任一等式約束關(guān)于容許點都是起作用約束任一等式約束關(guān)于容許點都是起作用約束容許方向（可行方向）容許方向（可行方向） Rn中的一個非空點集D，x D，若對某個非0向量p，存在一個小正數(shù)，對t(0, ),總有x+tp D（容許容許方向方向只與約束函數(shù)有關(guān)只與

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

4、為任一容許點, 記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點處的下降方向。從而存在一個小正數(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*是一個極小點， 則在x*處不會有方向

5、p 滿足也就是說，這個不等式組必?zé)o解。8Kuhn-Tucker(Kuhn-Tucker(庫恩庫恩- -塔克塔克) )定理定理設(shè)x*為不等式約束問題的一個極小點函數(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ù)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*是極小點，故不等式組無解。不等式組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條件的點稱為K-TK-T點點。事實上,若0為0,1111010412111)(,)(,)()()()(xsxsxf例例min f(x)=(x1-2)2+x22 s.t. s1(x)=x1-x220 s2(x)=-x1+x20對點x(1)=(0,0)T,在該點處s1(x),s2(x)都是起作用約束，在該點處f,s1,s2的梯度分別是故x(1)必不是K-T點, 011010421設(shè)004221,即00421,解得1211212

7、222212)(,)(,)(xsxsxfmin f(x)=(x1-2)2+x22s.t. s1(x)=x1-x220 s2(x)=-x1+x20對點x(2)=(1,1)T, 在該點處s1(x),s2(x)都是起作用約束在該點處f,s1,s2的梯度分別是故x(2)是K-T點, 011212221設(shè)022022121,即2021,解得133. 3.一般約束問題的最優(yōu)性條件一般約束問題的最優(yōu)性條件將一般約束問題中的等式約束換成是hj(x) 0,-hj(x) 0從而原問題就成為一個不等式約束問題。設(shè)x*為混合約束問題的一個極小點，函數(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ù)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可正可負，但i必非負)Kuhn-TuckerKuhn-Tuck