第四章-約束最優(yōu)化方法-最優(yōu)化方法課件

第四章-約束最優(yōu)化方法---最優(yōu)化方法課件第一頁，共151頁。目錄第一章最優(yōu)化問題概述第二章線性規(guī)劃第三章無約束最優(yōu)化方法第四章約束最優(yōu)化方法第一頁第二頁，共151頁。第四章

約束最優(yōu)化方法第二頁第三頁，共151頁。作業(yè)P2124.4(ii),(iii)P2134.7(ii)P2144.9(ii)4.11第三頁第四頁，共151頁?！?.1約束最優(yōu)化問題的最優(yōu)性條件問題在求解問題之前,我們先討論其最優(yōu)解的必要條件,充分條件和充要條件.這些條件是最優(yōu)化理論的重要組成部分,對討論算法起著關(guān)鍵的作用.有的算法甚至可以直接用來求解問題.第四頁第五頁，共151頁。4.1.1等式約束問題的最優(yōu)性條件考慮n=2,l=1的情況.c1(x)=0表示二維平面的一條曲線.最優(yōu)點(diǎn)滿足約束,必落在這一曲線上.在最優(yōu)點(diǎn)處作曲線的切線.考慮f(x)在最優(yōu)點(diǎn)處的負(fù)梯度方向問題第五頁第六頁，共151頁。等式約束問題的最優(yōu)性條件若–g*與上述切線不垂直,則可以在曲線上移動充分小的距離,使f的函數(shù)值下降.這與”最優(yōu)點(diǎn)”矛盾.因此梯度方向與切線垂直.或,f(x)在最優(yōu)點(diǎn)處的梯度方向就是c1(x)=0在該點(diǎn)處的法向.而c1(x)=0在該點(diǎn)處的法線方向?yàn)閏1(x)=0因此,存在數(shù)l1,使得-g*x*f(x)=f*第六頁第七頁，共151頁。等式約束問題的最優(yōu)性條件同樣可以說明(-)g*與曲線的切線垂直.因此,曲面在x*處的法向量與梯度向量g*共面.存在數(shù)l1,l2,使得如果n=3,l=2,約束曲線在三維空間中曲面c1(x)=0和曲面c2(x)=0的交線.第七頁第八頁，共151頁。等式約束問題的一階必要條件定理4.1.1(一階必要條件)若(i)x*是上述問題的局部最優(yōu)解;(ii)f(x)與ci(x)(i=1,2,···,l)在x*的某鄰域內(nèi)連續(xù)可微;(iii)線性無關(guān)則存在一組不全為零的數(shù)使得第八頁第九頁，共151頁。等式約束問題的一階必要條件對于上述問題,引入n+l元的Lagrange函數(shù)其中c(x)=(c1(x),···,cl(x))T,l=(l1,···,ll)T.稱l為Lagrange乘子向量.Lagrange函數(shù)的梯度為第九頁第十頁，共151頁。等式約束問題的一階必要條件因此無約束問題minL(x,l)的最優(yōu)性條件恰好是原來問題的一階必要條件及ci(x*),i=1,···,l.所以求含n+l個未知數(shù)x1,···,xn,l1,···,ll的非線性方程組的解(x*,l*),其中x*=(x1*,···,xn*)T在一定條件下就是原來約束問題的最優(yōu)解.點(diǎn)(x*,l*)稱為Lagrange函數(shù)L(x,l)的駐點(diǎn).第十頁第十一頁，共151頁。等式約束問題的二階充分條件定理4.1.2

在上面的等式約束問題中,若(i)f(x)與ci(x)(1≤i≤l)是二階連續(xù)可微函數(shù)(ii)存在x*∈Rn與l*∈Rl使得Lagrange函數(shù)的梯度為零,即(iii)對于任意非零向量s∈Rn,且均有則x*是上面問題的嚴(yán)格局部極小點(diǎn).第十一頁第十二頁，共151頁。等式約束問題的二階充分條件定理4.1.2的幾何意義是,在Lagrange函數(shù)L(x,l)的駐點(diǎn)處,若L(x,l)函數(shù)關(guān)于x的Hesse矩陣在約束超曲面的切平面上正定(不要求在整個空間正定),則x*就是嚴(yán)格局部極小點(diǎn).s第十二頁第十三頁，共151頁。定義4.1.1若上述問題的一個可行點(diǎn)使得某個不等式約束cj(x)≥0中的等號成立,即

則該不等式約束cj(x)≥0稱為關(guān)于的有效約束.4.1.1不等式約束問題的最優(yōu)性條件否則,若對某個k,使得則該不等式約束ck(x)≥0稱為關(guān)于的非有效約束.注:有時我們也將等式約束也視為有效約束.在教材中有說法不一致的地方.稱所有在處的有效約束的指標(biāo)組成的集合.為處的有效(約束)集第十三頁第十四頁，共151頁。Fritz-John一階必要條件定理4.1.6

設(shè)x*為上述問題的局部最優(yōu)解且f(x),ci(x)(1≤i≤m)在x*點(diǎn)可微,則存在非零向量l*=(l0*,l1*,···,lm*)使得滿足上面的條件的點(diǎn)稱為Fritz-John點(diǎn).上面的條件僅僅是必要條件.第十四頁第十五頁，共151頁。Fritz-John一階必要條件證明概要設(shè)x*處的有效集為I*=I(x*)={i|ci(x*)=0,i=1,2,···,m}.對于無效約束,由于ci(x)>0,若定理的結(jié)論成立,顯然有l(wèi)i*=0.定理結(jié)論可以描述為存在l0及l(fā)i(i∈I*),使得因?yàn)閤*是局部最優(yōu)解,在”指向有效約束的內(nèi)部的方向中”不含f(x)的下降方向.第十五頁第十六頁，共151頁。如圖顯示的是三個約束的例子其中c3(x)≥0為無效約束,c1(x)≥0,

c2(x)≥0為有效約束.黑色部分為可行域.由最優(yōu)點(diǎn)指向可行域內(nèi)部的方向d都具有性質(zhì)這種方向都不是下降方向,因此因?yàn)閤*是局部最優(yōu)解,在”指向有效約束的內(nèi)部的方向中”不含f(x)的下降方向.第十六頁第十七頁，共151頁。即由可以推出因此有下面的引理引理4.1.5

在不等式約束問題中,假設(shè)(i)x*為問題的局部最優(yōu)解,且I*={i|ci(x*)=0,i=1,2,···,m};(ii)f(x)和ci(x)(i∈I*)在x*可微;(iii)ci(x)(i∈I\I*)在x*連續(xù);則G∩S=f.其中表示下降方向表示指向可行域內(nèi)部的方向第十七頁第十八頁，共151頁。

是這樣一組向量,它們不在過原點(diǎn)的任何超平面的同一側(cè).Fritz-John一階必要條件證明概要(續(xù))根據(jù)上述引理,不存在d∈Rn,使得即于是我們總可以適當(dāng)放大或縮小各向量的長度,使得變化后的各向量的合成向量為零向量.注:這一結(jié)論的依據(jù)是下面的Gordan引理.第十八頁第十九頁，共151頁。Gordan引理引理4.1.4

設(shè)a1,···,ar是n維向量,則不存在向量d∈Rn使得aiTd<0(i=1,···,r)成立的充要條件是,存在不全為零的非負(fù)實(shí)數(shù)組l1,···,lr,使第十九頁第二十頁，共151頁。Fritz-John一階必要條件證明概要(續(xù))根據(jù)Gordan引理,存在不全為零的數(shù)l0*≥0,li*≥0(i∈I*),使得對于i∈I\I*,只要令li*=0,即可得到Fritz-John條件.第二十頁第二十一頁，共151頁。例題

(Fritz-John條件)例4.1.1minf(x)=(x1-1)2+(x2-1)2s.t.c1(x1,x2)=(1-x1-x2)3≥0

c2(x)=x1≥0

c3(x)=x2≥0解:本問題是求點(diǎn)(1,1)T到如圖三角形區(qū)域的最短距離.顯然唯一最優(yōu)解為x*=(1/2,1/2)T.第二十一頁第二十二頁，共151頁。例題(Fritz-John條件)下面求滿足Fritz-John條件的點(diǎn).minf(x)=(x1-1)2+(x2-1)2s.t.c1(x1,x2)=(1-x1-x2)3≥0

c2(x)=x1≥0

c3(x)=x2≥0即第二十二頁第二十三頁，共151頁。例題若l0*=0,l1*=0,則根據(jù)最上面的等式可以推出l2*=0,l3*=0.不滿足Fritz-John條件.若l1*=0,l2*=0,l3*=0,則l0*>0,x=(1,1)T.該點(diǎn)雖然滿足Fritz-John條件,但不是可行點(diǎn).若l0*=0,l2*=0,l3*=0,則l1*>0,x=(u,1-u)T.當(dāng)0≤u≤1時,x為可行點(diǎn).三角形斜邊上的點(diǎn)都是可行的Fritz-John點(diǎn),但只有(1/2,1/2)T是最優(yōu)點(diǎn).第二十三頁第二十四頁，共151頁。Fritz-John條件的缺點(diǎn)對于上面的例子,可行的Fritz-John點(diǎn)對應(yīng)的l0*=0.這表明在這些點(diǎn)處的有效約束函數(shù)的梯度是線性相關(guān)的.但是目標(biāo)函數(shù)的信息并未出現(xiàn)在其中,這樣對判斷是否為最優(yōu)解就不起作用了.因?yàn)橹灰s束函數(shù)不變,改變目標(biāo)函數(shù),Fritz-John條件始終是成立的.Kuhn-Tucker條件針對這一缺點(diǎn)作了改進(jìn).第二十四頁第二十五頁，共151頁。Kuhn-Tucker一階必要條件定理4.1.6

設(shè)(i)x*為上述問題的局部最優(yōu)解,有效集

I*={i|ci(x*)=0,i=1,2,···,m};(ii)f(x),ci(x)(1≤i≤m)在x*點(diǎn)可微;(iii)對于i∈I*的線性無關(guān),則存在向量l*=(l1*,···,lm*)使得滿足左邊的條件的點(diǎn)稱為KT點(diǎn).m+n維向量向量l*稱為Lagrange乘子向量.稱為KT對.第二十五頁第二十六頁，共151頁。Kuhn-Tucker必要條件顯然,由Fritz-John條件立刻可以推出Kuhn-Tucker條件.另一證明思路:x*處不存在可行下降方向,即若d(≠0)∈Rn,且有注:此處可行方向的條件比Fritz-John條件中的證明中的條件多了等號,在此不詳細(xì)討論其中的區(qū)別.第二十六頁第二十七頁，共151頁。Kuhn-Tucker必要條件借助于Farkas引理,可推出存在li*≥0(i∈I*),使得類似與Fritz-John條件的證明,可以證明Kuhn-Tucker條件.有效約束函數(shù)的梯度線性無關(guān)稱為Kuhn-Tucker約束規(guī)范.如果該約束規(guī)范不滿足,最優(yōu)點(diǎn)不一定是KT點(diǎn).第二十七頁第二十八頁，共151頁。Farkas引理引理4.1.3

設(shè)a1,a2,···,ar和b均為n維向量,則所有滿足aiTd≥0,i=1,···,r的向量d∈Rn,同時也滿足不等式bTd≥0的充要條件是,存在非負(fù)實(shí)數(shù)l1,l2,···,lr使得注:此引理的充分性證明是顯然的.必要性的證明較為復(fù)雜,此處略去.第二十八頁第二十九頁，共151頁。Farkas引理的幾何說明考慮二維空間中兩個向量a1,a2.a1a2滿足a1Td≥0的方向d的范圍(黃色)滿足a2Td≥0的方向d的范圍(紫色)同時滿足上面兩個條件的d(黑色)要與上述黑色區(qū)域的方向交角為銳角的方向應(yīng)在a1與a2兩個方向之間(紅色).從而可以表示為這兩個向量的非負(fù)的線性組合.第二十九頁第三十頁，共151頁。Kuhn-Tucker必要條件KT條件中l(wèi)i*ci(x*)=0稱為互補(bǔ)松弛條件.它表明li*與ci(x*)不能同時不為0.當(dāng)所有的有效約束的乘子都不為零時,稱互補(bǔ)松弛條件為嚴(yán)格互補(bǔ)松弛條件.第三十頁第三十一頁，共151頁。線性規(guī)劃對于線性規(guī)劃問題minf(y)=-bTys.t.-ATy≥-c其中y∈Rm,A∈Rm×n,

b∈Rm,c∈Rn問題有n個約束條件.各個約束條件關(guān)于y的梯度為-AT的行向量(-pi).即Ax*=b及(ATy*-c)T

x*=0若AT的各個行向量線性無關(guān).根據(jù)Kuhn-Tucker條件,在該線性規(guī)劃的最優(yōu)點(diǎn)y*處存在乘子向量x*≥0,使得對偶規(guī)劃約束條件線性規(guī)劃互補(bǔ)松弛條件第三十一頁第三十二頁，共151頁。4.1.3一般約束問題的最優(yōu)性條件定理4.1.8

在上述問題中,若(i)x*為局部最優(yōu)解,有效集I*={i|ci(x*)=0,i∈I};(ii)f(x),ci(x)(1≤i≤m)在x*點(diǎn)可微;(iii)對于i∈E∪I*,線性無關(guān),則存在向量l*=(l1*,···,lm*)使得第三十二頁第三十三頁，共151頁。一般約束問題的最優(yōu)性條件m+n維函數(shù)稱為前述問題的Lagrange函數(shù).KT條件的第一式可以寫為其中l(wèi)*稱為Lagrange乘子向量.矩陣稱為Lagrange函數(shù)在處的Hesse矩陣,記為第三十三頁第三十四頁，共151頁。(i)為KT對,且嚴(yán)格互補(bǔ)松弛條件成立;二階充分條件定理4.1.9

設(shè)f(x)和ci(x)(i∈E∪I)是二階連續(xù)可微函數(shù),若存在x*∈Rn滿足(ii)對子空間

中的任意d≠0,有dTw*d>0,則x*為上述問題的嚴(yán)格局部最優(yōu)解.第三十四頁第三十五頁，共151頁。凸規(guī)劃問題的充分條件凸規(guī)劃問題其中f(x)為凸函數(shù),ci(x)(i∈I)為凹函數(shù).定理4.1.10

設(shè)上面的凸規(guī)劃問題中f(x)和ci(x)(i∈I)為可微函數(shù),若x*為該問題的KT點(diǎn),則x*為其整體最優(yōu)解.第三十五頁第三十六頁，共151頁。例題(KT點(diǎn))例4.1.3已知約束問題試驗(yàn)證最優(yōu)點(diǎn)x*=(1,1,1)T為KT點(diǎn).解I*={1,2}令得l1=-2,l2=2,即對于無效約束,可取li*=0,故x*=(1,1,1)T為KT點(diǎn).第三十六頁第三十七頁，共151頁。§4.2罰函數(shù)法與乘子法對于一般的約束優(yōu)化問題一種常用的方法是將其轉(zhuǎn)化為無約束問題.其中的約束轉(zhuǎn)化為目標(biāo)函數(shù)的一部分.滿足約束時,對應(yīng)的函數(shù)值很小;不滿足約束時,對應(yīng)的函數(shù)值很大——”懲罰”.在求解過程中,為使得總的目標(biāo)函數(shù)值最小,得到的解一般會滿足約束.這類方法一般稱為罰函數(shù)法.第三十七頁第三十八頁，共151頁。外罰函數(shù)法例4.2.1求解約束問題解:本問題就是求原點(diǎn)到直線x1+x2-2=0上的點(diǎn)的最短距離.顯然最優(yōu)解為(1,1)T.第三十八頁第三十九頁，共151頁。外罰函數(shù)法設(shè)輔助函數(shù)為則以F(x1,x2)為目標(biāo)函數(shù)的無約束問題的極小點(diǎn)必在直線x1+x2-2=0上,且目標(biāo)函數(shù)的取值與原來問題的目標(biāo)函數(shù)的取值一致.只是該函數(shù)的性質(zhì)比較糟糕,無法用一般的算法求解.第三十九頁第四十頁，共151頁。外罰函數(shù)法考慮下面的增廣目標(biāo)函數(shù)其中s是很大的正數(shù).以其為目標(biāo)函數(shù),解無約束問題,得到最優(yōu)解為當(dāng)s→+∞時,有(x1(s),x2(s))T→(1,1)T=x*.即無約束問題最優(yōu)解的極限為原問題最優(yōu)解.注:輔助函數(shù)的目標(biāo)函數(shù)值為在s→+∞時也逼近于原問題的最優(yōu)值2.第四十頁第四十一頁，共151頁。外罰函數(shù)法(等式約束問題)對于等式約束問題,構(gòu)造如下增廣目標(biāo)函數(shù)其中s>0為參數(shù),稱為罰因子.對于懲罰項(xiàng)當(dāng)x為可行解時,當(dāng)x不是可行解時,s越大,懲罰越重.第四十一頁第四十二頁，共151頁。外罰函數(shù)法(等式約束問題)當(dāng)s充分大時,要使P(x,s)取極小值,應(yīng)充分小,即P(x,s)的極小點(diǎn)充分逼近可行域.在一定條件下,當(dāng)s→∞時,P(x,s)的極小點(diǎn)逼近于原問題的解.第四十二頁第四十三頁，共151頁。外罰函數(shù)法(不等式約束問題)可以構(gòu)造增廣目標(biāo)函數(shù)其中“懲罰項(xiàng)”的作用與等式約束時的情形類似.第四十三頁第四十四頁，共151頁。例題(不等式約束問題)例4.2.1求解約束問題問題是求點(diǎn)(0,0)T到半平面x≤-1的最短距離.顯然最優(yōu)點(diǎn)為x*=(-1,0)T.最優(yōu)值為f(x*)=1.設(shè)增廣目標(biāo)函數(shù)為第四十四頁第四十五頁，共151頁。例題(不等式約束問題)故令得它是minP(x,s)的最優(yōu)解,最優(yōu)值為當(dāng)s→+∞時,x1(s)→-1,x2(s)→0.因此x(s)→x*,P(x,s)→f(x*)=1.第四十五頁第四十六頁，共151頁。外罰函數(shù)法在上面的兩個例子中,當(dāng)s→+∞時,P(x,s)的最優(yōu)解x(s)趨向于極限x*.而x*即為原約束問題的最優(yōu)解.不過x(s)往往不滿足約束條件,在迭代過程中,x(s)從可行域的外部逐步趨于原問題的最優(yōu)解.因此上面的方法稱為外罰函數(shù)法.通過一系列無約束最優(yōu)化問題來求解約束最優(yōu)化問題稱為序列無約束極小化方法SUMT(SequentialUnconstrainedMinimizationTechnique),因此外罰函數(shù)法又稱為SUMT外點(diǎn)法.第四十六頁第四十七頁，共151頁。外罰函數(shù)法(一般約束問題)構(gòu)造如下增廣目標(biāo)函數(shù)其中稱為罰函數(shù),s>0稱為罰因子.求解原問題轉(zhuǎn)化為求解一系列的無約束問題minP(x,sk)(sk

→+∞).第四十七頁第四十八頁，共151頁。外罰函數(shù)法(算法步驟)算法4.2.1

外罰函數(shù)法得最優(yōu)解xk=x(sk).Step1

以xk-1為初始點(diǎn)解無約束問題取控制誤差e>0,罰因子放大系數(shù)c>1,初始點(diǎn)x0,初始罰因子s1,令k=1.Step2

若則以xk為問題的近似最優(yōu)解.Stop.否則,令sk+1=csk,k=k+1,轉(zhuǎn)Step1.第四十八頁第四十九頁，共151頁。外罰函數(shù)法(收斂性)對SUMT外點(diǎn)法產(chǎn)生的點(diǎn)列{xk},xk是P(x,sk)的最優(yōu)解.因此有P(xk+1,sk+1)≥P(xk,sk)第四十九頁第五十頁，共151頁。外罰函數(shù)法(收斂性)xk是P(x,sk)最優(yōu)解.xk+1是P(x,sk+1)最優(yōu)解.因此再根據(jù)上面(綠色)標(biāo)出的不等式,有我們得到書中P157引理4.2.1第五十頁第五十一頁，共151頁。外罰函數(shù)法(收斂性)如果原來約束問題有多個最優(yōu)解,那么SUMT外點(diǎn)法產(chǎn)生的點(diǎn)列不能保證收斂.例如,的最優(yōu)解有無窮多個問題的增廣目標(biāo)函數(shù)為該函數(shù)的極小點(diǎn)(無窮多)位于直線在求解過程中,雖然迭代點(diǎn)向直線x1+x2=1靠近.但是不能保證迭代點(diǎn)列收斂.第五十一頁第五十二頁，共151頁。外罰函數(shù)法(收斂性)定理4.2.2

設(shè)上面優(yōu)化問題與增廣目標(biāo)函數(shù)的整體最優(yōu)解分別是x*與xk,對于正數(shù)序列{sk},sk+1

≥

sk,且sk

→+∞,則由SUMT外點(diǎn)法產(chǎn)生的點(diǎn)列{xk}的任何聚點(diǎn)x必是約束優(yōu)化問題的整體最優(yōu)解.注:所謂聚點(diǎn),是指子序列的極限.例:點(diǎn)列1,0,-1,1,0,-1,1,0,-1,···,有三個聚點(diǎn)1,0,-1.第五十二頁第五十三頁，共151頁。外罰函數(shù)法(收斂性)證明不妨設(shè)xk

→x.由于x*和xk分別是原問題與增廣目標(biāo)函數(shù)的整體最優(yōu)解,從而xk是P(x,sk)最優(yōu)解.引理4.2.1P(xk,sk)存在極限,設(shè)為p0.單調(diào)有界數(shù)列必收斂引理4.2.1f(xk)存在極限,設(shè)為f0.單調(diào)有界數(shù)列必收斂第五十三頁第五十四頁，共151頁。注:對

兩邊取極限可得f0=p0.外罰函數(shù)法(收斂性)由于xk

→x,且連續(xù),因此即x為可行解.而x*為整體最優(yōu)解,所以f(x*)≤f(x).根據(jù)xk

→x以及得到f(x)≤f(x*).因此f(x)=f(x*).所以x也是整體最優(yōu)解.這是在算法中取

作為終止準(zhǔn)則的原因.因此第五十四頁第五十五頁，共151頁。算例(外罰函數(shù)法)例4.2.3

求解約束問題注:(1)函數(shù)中應(yīng)為(x1-2x2)2(2)表4-1中有許多打印錯誤.解取增廣目標(biāo)函數(shù)為(x1-2)4+(x1-2x2)2+s(x12-x2)2,x0=(2,1)T,s1=0.1,c=10,e=10-3.對于無約束問題,采用重新開始的PRP算法(e=10-3)求解.得到的結(jié)果見下表.第五十五頁第五十六頁，共151頁。算例(外罰函數(shù)法)精確解(0.94558299,0.89412720)T.kxkf(xk)0(2,1)T00.91(1.45388,0.76076)T0.093531.830582(1.16872,0.74067)T0.575243.909303(0.99061,0.84246)T1.520131.928224(0.95076,0.88749)T1.891230.271705(0.94611,0.89344)T1.940520.028286(0.94563,0.89405)T1.945620.002847(0.94556,0.89409)T1.946196.8e-6第五十六頁第五十七頁，共151頁。第五十七頁第五十八頁，共151頁。內(nèi)罰函數(shù)法考慮上面的不等式約束問題.當(dāng)x從可行域的內(nèi)部趨于邊界時,至少有一個ci(x)趨于零,因此我們構(gòu)造下面的增廣目標(biāo)函數(shù)其中或稱為內(nèi)罰函數(shù)或障礙函數(shù)(Barrierfunction),參數(shù)r稱為罰因子.第五十八頁第五十九頁，共151頁。內(nèi)罰函數(shù)法當(dāng)x為可行域D的內(nèi)點(diǎn)時,的值是有限的正數(shù),而r>0很小,幾乎不受懲罰.當(dāng)x接近D的邊界時,的值趨于無窮大,受懲罰很大,迫使極小點(diǎn)落在D的內(nèi)部,最終逼近f(x)的約束極小點(diǎn).令正數(shù)列{rk}逐步減小,并趨于零,則原約束問題轉(zhuǎn)化為系列無約束問題.第五十九頁第六十頁，共151頁。內(nèi)罰函數(shù)法(算法步驟)算法4.2.2

內(nèi)罰函數(shù)法得最優(yōu)解xk=x(rk).Step1

以xk-1為初始點(diǎn)解無約束問題取控制誤差e>0,罰因子縮小系數(shù)0<c<1,初始點(diǎn)x0∈D0(可行域內(nèi)部),初始罰因子r1,令k=1.Step2

若則以xk為問題的近似最優(yōu)解.Stop.否則,令rk+1=crk,k=k+1,轉(zhuǎn)Step1.第六十頁第六十一頁，共151頁。內(nèi)罰函數(shù)法(算例)例4.2.4

用內(nèi)點(diǎn)法求解解增廣目標(biāo)函數(shù)為令得當(dāng)r→0時,得x*=(1,0)T.f*=8/3.第六十一頁第六十二頁，共151頁。內(nèi)罰函數(shù)法(算例)一般而言,B(x,r)的最優(yōu)點(diǎn)要用無約束問題的算法來求解.x0=(3,4)T,r1=10,c=10,e=10-3.對于無約束問題,采用重新開始的PRP算法(e=10-3)求解.得到的結(jié)果見下表.注:在求解無約束問題時,要注意限制一維搜索的初始區(qū)間,即保證迭代點(diǎn)始終在可行域之內(nèi).在本問題中,如果對一維搜索的初始區(qū)間不加限制,函數(shù)值會趨于負(fù)無窮.第六十二頁第六十三頁，共151頁。算例(內(nèi)罰函數(shù)法)精確解(1,0)T.kxkf(xk)0(3,4)T25.33332501(2.04017,3.16226)T12.52861.277612(1.41421,1.00007)T5.690420.341413(1.14727,0.31630)T3.616480.099524(1.04881,0.10004)T2.966740.030485(1.01569,0.03162)T2.761540.009546(1.00499,0.01000)T2.696670.003007(1.00158,0.00316)T2.676150.00095第六十三頁第六十四頁，共151頁。第六十四頁第六十五頁，共151頁。內(nèi)罰函數(shù)法(收斂性)關(guān)于內(nèi)罰函數(shù)法,有類似于外罰函數(shù)法的收斂性結(jié)論.引理4.2.3

對于由SUMT內(nèi)點(diǎn)法產(chǎn)生的點(diǎn)列{xk},總有B(xk+1,rk+1)≤B(xk,rk).定理4.2.4

設(shè)可行域內(nèi)點(diǎn)集D0={x∈Rn|ci(x)>0,i∈I}非空,f(x)在D上存在整體極小點(diǎn)x*,對于嚴(yán)格單調(diào)遞減正數(shù)序列{rk},rk+1

<rk,且rk→0,則由SUMT內(nèi)點(diǎn)法產(chǎn)生的點(diǎn)列{xk}的任何聚點(diǎn)必是不等式約束優(yōu)化問題的整體最優(yōu)解.第六十五頁第六十六頁，共151頁。4.2.4乘子法考慮上面的等式約束問題.設(shè)x*為該問題的最優(yōu)解,在一定條件下,存在l*使(x*,l*)為Lagrange函數(shù)

的駐點(diǎn),即一個自然的問題是,能否找到l*使得(x*,l*)是Lagrange函數(shù)的極小點(diǎn).那樣的話,約束問題就轉(zhuǎn)化為無約束問題.第六十六頁第六十七頁，共151頁。乘子法例4.2.5

求解約束問題此問題的最優(yōu)解為(0,0)T.Lagrange函數(shù)為對于任何l,L(x,l)關(guān)于x的極小點(diǎn)不存在.對于等式約束問題,我們構(gòu)造了輔助函數(shù)然后令s→∞,在一定條件下求得原問題的解.第六十七頁第六十八頁，共151頁。乘子法另一個問題是,能否找到s*,使得P(x,s*)的無約束極小點(diǎn)是原約束問題的極小點(diǎn).如果x*是P(x,s*)的極小點(diǎn),則有由于x*是可行點(diǎn),ci(x*)=0,因此這在一般情況下是不成立的.第六十八頁第六十九頁，共151頁。等式約束問題的乘子法我們將上述兩種思路結(jié)合起來,即考慮問題,能否找到l*,s*,使得x*是下面的增廣Lagrange函數(shù)的極小點(diǎn).考慮例4.2.5中的問題增廣Lagrange函數(shù)為取當(dāng)l*=-3,s≥s*=2時,原問題最優(yōu)解(0,0)T是增廣Lagrange函數(shù)的最優(yōu)解.第六十九頁第七十頁，共151頁。等式約束問題的乘子法反之,求解無約束問題得令要求x0滿足約束條件x2=0,必須取l=-3,從而x0=(0,0)T=x*,得到原約束問題的最優(yōu)解.第七十頁第七十一頁，共151頁。等式約束問題的乘子法考慮等式約束問題其中C(x)=(c1(x),···,cl(x))T,目標(biāo)函數(shù)和約束函數(shù)二次連續(xù)可微.設(shè)l∈Rl為Lagrange乘子向量,則上面問題的Lagrange函數(shù)為對任意的x*∈D,有因此,原約束問題等價于下面的約束問題第七十一頁第七十二頁，共151頁。等式約束問題的乘子法對左邊問題,構(gòu)造增廣Lagrange函數(shù)定理4.2.6設(shè)在上面等式約束問題中,x*∈Rn和l*∈Rn滿足二階充分條件(Th4.1.2),則存在一個數(shù)s*>0,對所有的s≥s*,x*是增廣目標(biāo)函數(shù)的嚴(yán)格局部極小點(diǎn);反之,若C(x0)=0且x0對某個l0是增廣目標(biāo)函數(shù)的局部極小點(diǎn),則x0是等式約束問題的局部極小點(diǎn).第七十二頁第七十三頁，共151頁。等式約束問題的乘子法乘子法并不要求s趨于無窮大.只要s大于某個正數(shù)s*,就能保證無約束問題minM(x,l*,s)的最優(yōu)解為原問題的最優(yōu)解.要解決的問題是,如何確定l*?我們采用迭代的方法求出l*.求解無約束問題minM(x,lk,s),其解為xk,然后修正lk為lk+1,再求解minM(x,lk+1,s).得到兩個點(diǎn)列{xk},{lk},希望xk→x*,lk→l*.第七十三頁第七十四頁，共151頁。等式約束問題的乘子法如何對lk進(jìn)行修正?設(shè)已有l(wèi)k和xk,由M(x,l,s)的定義希望xk→x*,lk→l*,又采取公式lk+1=lk-sC(xk)是比較合理的.若{lk}收斂,則有C(xk)→0.若xk→x*,則有C(x*)=0,即x*為可行解.第七十四頁第七十五頁，共151頁。等式約束問題的乘子法——PH算法Step1選定初始點(diǎn)x0,初始乘子向量l1,初始罰因子s1,放大系數(shù)c>1,控制誤差e,常數(shù)q∈(0,1),令k=1;Step2以x1為初始點(diǎn)求解無約束問題得到的最優(yōu)解即為xk;Step3當(dāng)||C(xk)||<e時,xk為所求的最優(yōu)解,Stop;Step4當(dāng)||C(xk)||/||C(xk-1)||>q時,令sk+1=csk;Step5令lk+1=lk-skC(xk),k=k+1,轉(zhuǎn)Step2.第七十五頁第七十六頁，共151頁。例題(等式約束問題的乘子法)解增廣Lagrange函數(shù)為例4.2.7求解約束問題令得將其中的l視為lk,根據(jù)乘子迭代公式第七十六頁第七十七頁，共151頁。例題(等式約束問題的乘子法)當(dāng)s>0時,{lk}收斂.設(shè)lk→l*,對上式取極限得因此l*=2.在中,令l=2,得原問題的最優(yōu)解x*=(1,1)T.第七十七頁第七十八頁，共151頁。不等式約束問題的乘子法對不等式約束問題,引進(jìn)輔助變量zi(i=1,2,···,m),上面的問題轉(zhuǎn)化為等價的等式約束問題.其增廣Lagrange函數(shù)為第七十八頁第七十九頁，共151頁。不等式約束問題的乘子法先考慮這一函數(shù)關(guān)于z的極小化函數(shù),關(guān)于變量zi,它是zi2的二次函數(shù)當(dāng)時,要使函數(shù)取最小,否則zi=0.因此得到增廣的目標(biāo)函數(shù)第七十九頁第八十頁，共151頁。不等式約束問題的乘子法乘子迭代公式終止準(zhǔn)則對于一般約束問題,只要綜合等式約束和不等式約束的情況寫出增廣目標(biāo)函數(shù)來求解.其算法稱為PHR算法.第八十頁第八十一頁，共151頁。例題(PHR算法)例4.2.8用PHR算法求解解增廣目標(biāo)函數(shù)為當(dāng)時,令得當(dāng)s充分大時,該點(diǎn)不滿足從而不是極小點(diǎn).第八十一頁第八十二頁，共151頁。例題(PHR算法)當(dāng)時,令得當(dāng)s充分大時,該點(diǎn)滿足將其中的l視為lk,采用下面的公式得出lk+1.若給定l1>0,且s>0,則以下過程同例4.2.7.第八十二頁第八十三頁，共151頁。§4.3投影梯度法第八十三頁第八十四頁，共151頁。4.3.1可行方向及其性質(zhì)本節(jié)研究左邊的線性不等式約束問題.對于線性約束aiTx≥bi,在幾何上表示半空間.其邊界是一個超平面aiTx=bi,其法向量指向ai半空間的內(nèi)部.對于超平面上的一點(diǎn),指向半空間內(nèi)部的方向是可行方向,易見可行方向d與ai的夾角為銳角或直角,即aiTd≥0.aid若aiTd=0,則沿該方向的點(diǎn)在邊界上.第八十四頁第八十五頁，共151頁。投影梯度法例4.3.2

求解第八十五頁第八十六頁，共151頁。負(fù)梯度指向可行域內(nèi)部仿照單純形方法,我們沿著邊界使函數(shù)值下降.由于負(fù)梯度方向沿方向(0,1)T的分量較大,我們先沿此方向p1=(0,1)T進(jìn)行一維搜索.第八十六頁第八十七頁，共151頁。為了保證迭代點(diǎn)在可行域內(nèi)部,顯然步長ak的最大值為1.p1=(0,1)T作線性搜索,即求解得a1=1,x2=x1+a1p1=(0,1)T.第八十七頁第八十八頁，共151頁。在x2處沿邊界指向可行域的方向?yàn)?0,-1)T和(5,-1)T.因此我們下一步沿著方向p2=(5,-1)T搜索.可以求得步長ak的最大值為1/4.第八十八頁第八十九頁，共151頁。作線性搜索,即求解得a2=7/31,x3=x2+a2p2=(35/31,24/31)T.可以驗(yàn)證x3為KT點(diǎn).又f(x)為凸函數(shù),x3為最優(yōu)點(diǎn)第八十九頁第九十頁，共151頁。投影梯度法上述思路的總結(jié)方法:在任一點(diǎn),找出有效約束,沿著與梯度成銳角的邊界方向向可行域內(nèi)搜索.問題:不是極點(diǎn)的點(diǎn)如何搜索?(最優(yōu)點(diǎn)可能在內(nèi)部)沿邊界的方向通過什么方法確定?如何確定已達(dá)到最優(yōu)?第九十頁第九十一頁，共151頁。我們根據(jù)是否可以寫為{ai(i∈I*)}的線性組合來分情況討論迭代方法以及乘子向量的計(jì)算方法.投影梯度法如何判斷是否達(dá)到最優(yōu)?通常用KT條件來判斷.假設(shè)當(dāng)前的迭代點(diǎn)為x,設(shè)I*為有效約束集,即有aiTx=bi(i∈I*),下面假設(shè){ai(i∈I*)}線性無關(guān),第九十一頁第九十二頁，共151頁。情形一令如果li≥0,則x為KT點(diǎn).如何求組合系數(shù)li?其中Aq是以{ai(i∈I*)}為列向量構(gòu)成的矩陣.若Aq為方陣.則Aq非奇異,且可以寫為可以寫為{ai(i∈I*)}的線性組合.第九十二頁第九十三頁，共151頁。情形一注:Aq+為Aq的廣義逆矩陣,

A+A=I.但是AA+=I不一定成立.當(dāng)A為非奇異方陣時,A+=A-1.在的兩邊同時左乘Aq+,得在Aq為列滿秩時,AqTAq為可逆矩陣.記Aq+=(AqTAq)-1AqT,則Aq+Aq=I.此時如何求下降方向進(jìn)行迭代在后面討論.第九十三頁第九十四頁，共151頁。此時,可以分解成兩個正交的向量,一個可以寫為上述向量的線性組合,一個垂直于上述向量,即情形二不能寫為{ai(i∈I*)}的線性組合.Aqu表示{ai(i∈I*)}的一個線性組合AqTv=0表示與{ai(i∈I*)}中每個向量正交由圖形可以看出-v是一個沿著x點(diǎn)有效約束邊界的可行下降方向.第九十四頁第九十五頁，共151頁。情形二根據(jù)上面的等式有因此下面求出梯度的分解中的兩個向量Aqu與v.第九十五頁第九十六頁，共151頁。顯然p與的夾角是銳角,因此是下降方向.情形二的可行下降方向令從圖形上可以看出下面從理論上給出推導(dǎo).第九十六頁第九十七頁，共151頁。情形二的可行下降方向考察矩陣有另外因此方向p是下降方向.第九十七頁第九十八頁，共151頁。情形二的可行下降方向那么p是否是可行方向呢?從圖形上可以看出p是位于有效約束的邊界上.即有效約束對應(yīng)的超平面的法向量與方向p均是正交的.第九十八頁第九十九頁，共151頁。情形二的可行下降方向?qū)τ邳c(diǎn)x+ap,有因此點(diǎn)x+ap依然滿足有效約束的相關(guān)不等式.對于無效約束,只要a取值足夠小,不等式就能夠成立.第九十九頁第一百頁，共151頁。a的取值上限為了保證x+ap在可行域內(nèi),a取值必須足夠小,使得在x點(diǎn)處的無效約束依然成立.對約束aiTx≥bi,將點(diǎn)x+ap代入此不等式有即由于在aiTp≥0時,上式對a≥0成立.若aiTp<0,則有因此a的取值上限為第一百頁第一百零一頁，共151頁。情形一的可行下降方向其中若l≥0,顯然x為KT點(diǎn).第一百零一頁第一百零二頁，共151頁。情形一的可行下降方向其中若l至少有一個分量小于0,設(shè)為li<0.此時負(fù)梯度投影到ai上的分量是指向可行域之外的.第一百零二頁第一百零三頁，共151頁。情形一的可行下降方向因此此時不考慮li對應(yīng)的約束,而將負(fù)梯度分解為兩個垂直的向量,一個是aj(j∈I*,j≠i)的線性組合,由圖形上可以看出,我們得到一個可行的下降方向,而且是沿著有效約束(去掉ai對應(yīng)的約束)的邊界的.可行的下降方向一個與這些向量垂直.第一百零三頁第一百零四頁，共151頁。情形一的可行下降方向設(shè){aj,j∈I*,j≠i}構(gòu)成的矩陣為Aq-1,Aq-1為Aq去掉列向量ai得到的矩陣.再設(shè)l去掉分量li得到的向量為lq-1.現(xiàn)在將負(fù)梯度寫為如下的形式類似與情形二的推導(dǎo),有顯然有第一百零四頁第一百零五頁，共151頁。情形一的可行下降方向設(shè)可行的下降方向由圖形可以看出第一百零五頁第一百零六頁，共151頁。

說明ai可以寫為aj(j∈I*,j≠i)的線性組合,這與Aq列滿秩矛盾.情形一的可行下降方向若pq-1=0,則下面證明pq-1為可行的下降方向.首先證pq-1≠0.是一個向量第一百零六頁第一百零七頁，共151頁。情形一的可行下降方向其次證pq-1為下降方向.類似與情形二中的討論,有因此注:若有效約束只有一個,對應(yīng)矩陣取為單位陣I,此時下降方向即為負(fù)梯度方向.第一百零七頁第一百零八頁，共151頁。情形一的可行下降方向最后證pq-1為可行方向.關(guān)于x點(diǎn)處的有效約束對應(yīng)的方向aj與pq-1的夾角為銳角或直角,因此pq-1為可行方向.第一百零八頁第一百零九頁，共151頁。情形一或情形二的判斷?前面在兩種情形下討論了如何確定迭代的可行下降方向.關(guān)于屬于何種情形是通過描述性的語言”梯度可以寫為有效約束對應(yīng)的向量的線性組合”來定義的.那么如何通過數(shù)據(jù)特征來區(qū)分兩種情形?根據(jù)前面的討論,我們可以通過梯度的投影是否為零向量來判斷.第一百零九頁第一百一十頁，共151頁。投影梯度法已知迭代點(diǎn)x,根據(jù)有效約束集I*={i|aiTx=bi(i∈I)}寫出對應(yīng)的矩陣Aq及投影矩陣Pq=I-AqAq+.情形二以為可行下降方向進(jìn)行迭代情形一求乘子向量l,若l≥0,終止迭代否則,選取一個負(fù)分量,給出Aq-1,Pq-1以為可行下降方向進(jìn)行迭代第一百一十頁第一百一十一頁，共151頁。Y給出初始可行點(diǎn)x1,控制誤差e>0,令k=1Ik={i|aiTxk=bi,i=1,2,···,m},若Ik=f,令Pq=I,Ik≠f,令Pq=I-AqAq+,令pk=-Pqgk.||pk||<e?Nl=Aq+gkl≥0?STOP計(jì)算amax,一維搜索求ak,

xk+1=xk+akpk,k=k+1Yll=min{li},給出Aq-1,令

Pq-1=I-Aq-1Aq-1+,令pk=-Pq-1gk.N計(jì)算流程投影梯度法第一百一十一頁第一百一十二頁，共151頁。算例(投影梯度法)例4.3.2

求解解取初始點(diǎn)x1=(0,0)T.有效集為{3,4}.可逆.因此第一次迭代第一百一十二頁第一百一十三頁，共151頁。算例(投影梯度法)乘子向量取l2=-6,從A2取中去掉第二列,得到第一百一十三頁第一百一十四頁，共151頁。算例(投影梯度法)作線性搜索得第一百一十四頁第一百一十五頁，共151頁。amax的手工計(jì)算在手算時,可以解下面的不等式來確定amax.即得因此第一百一十五頁第一百一十六頁，共151頁。算例(投影梯度法)第二次迭代可逆.乘子向量取l2=-28/5<0,從A2取中去掉第二列,得到第一百一十六頁第一百一十七頁，共151頁。算例(投影梯度法)取l2=-28/5<0,從A2取中去掉第二列,得到不妨取p2=(5,-1)T.第一百一十七頁第一百一十八頁，共151頁。算例(投影梯度法)作線性搜索得第一百一十八頁第一百一十九頁，共151頁。算例(投影梯度法)因此x3=(35/31,24/31)T為KT點(diǎn).本問題是凸規(guī)劃問題,x3是最優(yōu)解.第三次迭代第一百一十九頁第一百二十頁，共151頁?！?.4約束變尺度法第一百二十頁第一百二十一頁，共151頁。4.4.1二次規(guī)劃目標(biāo)函數(shù)是二次函數(shù),約束函數(shù)為線性函數(shù)的規(guī)劃問題稱為二次規(guī)劃,其一般形式為其中G為n階對稱矩陣.當(dāng)G正定時,(QP)為嚴(yán)格凸二次規(guī)劃.第一百二十一頁第一百二十二頁，共151頁。二次規(guī)劃KT條件定理4.4.1

點(diǎn)x*是嚴(yán)格凸二次規(guī)劃(QP)的嚴(yán)格整體最優(yōu)解的充要條件是x*滿足KT條件,即存在乘子向量l*=(l1*,···,lm*),使得其中I*是x*處的有效集.第一百二十二頁第一百二十三頁，共151頁。等式約束二次規(guī)劃對于僅含等式約束的嚴(yán)格凸二次規(guī)劃其中A=(a1,···,al)的秩為l.顯然,x是上述問題的解的充要條件是第一百二十三頁第一百二十四頁，共151頁。等式約束二次規(guī)劃令b=(b1,···,bl)T,l=(l1,···,ll)T,上式可以記為由于G正定,A列滿秩,該線性方程組有唯一解.第一百二十四頁第一百二十五頁，共151頁。等式約束二次規(guī)劃(算例)例4.4.1

求解嚴(yán)格凸二次規(guī)劃

minf(x)=x12+x22+x32

(QP)s.t. x1+2x2-x3-4=0

x1-x2+x3+2=0解

(QP)的最優(yōu)解及乘子滿足該方程組有唯一解因此最優(yōu)解x*=(2/7,10/7,-6/7)T,最優(yōu)乘子向量l*=(8/7,-4/7)T.第一百二十五頁第一百二十六頁，共151頁。嚴(yán)格凸二次規(guī)劃的有效集方法定理4.4.2

設(shè)x*是上面問題的最優(yōu)解,且在x*處的有效集為I*,則x*也是下列問題的最優(yōu)解(4.86)(4.82)第一百二十六頁第一百二十七頁，共151頁。有效集方法證明:由于x*是(4.82)問題的最優(yōu)解,存在乘子向量l*滿足顯然有這是問題(4.86)的最優(yōu)解的充要條件.第一百二十七頁第一百二十八頁，共151頁。有效集方法例:解二次規(guī)劃minf(x)=(x1-1)2+(x1-2.5)2s.t. x1-2x2+2≥0 -x1-2x2+6≥0 -x1+2x2+2≥0

x1 ≥0

x2≥0解:取初始可行點(diǎn)x0=(2,0)T.有效集為I0={3,5}.第一百二十八頁第一百二十九頁，共151頁。有效集方法我們首先來求解等式約束二次規(guī)劃minf(x)=(x1-1)2+(x1-2.5)2

s.t. -x1+2x2+2=0

x2=0顯然求得的最優(yōu)解x1=x0.我們來判斷x1是否是原來的二次規(guī)劃的KT點(diǎn).第一百二十九頁第一百三十頁，共151頁。有效集方法g1=(2,-5)T,a3=(-1,2)T,a5=(0,1)T,令g1=l3a3+l5a5,則有l(wèi)3=-2,l5=-1.因此x1=(2,0)T不是KT點(diǎn).事實(shí)上,a3=(-1,2)T,a5=(0,1)T都是可行的下降方向.第一百三十頁第一百三十一頁，共151頁。a3a5-g1約束3約束5g1=-2a3-a5第一百三十一頁第一百三十二頁，共151頁。有效集方法去掉約束i1=3,得有效集I1={5},求解下面的二次規(guī)劃minf(x)=(x1-1)2+(x1-2.5)2s.t. x2=0令x=xk+d,gk=Gxk+C,則f(x)=xTGx/2+CTx=(xk+d)TG(xk+d)/2+CT(xk+d)=dTGd/2+xkTGd+xkTGxk/2+CTxk+CTd=dTGd/2+gkTd+xkTGxk/2+CTd第一百三十二頁第一百三十三頁，共151頁。有效集方法約束ajTx≥bj等價于ajT(xk+d)≥bj,即ajTd=0.一般的,若已知可行解xk,有效集Ik,我們求解二次規(guī)劃它等價于求解第一百三十三頁第一百三十四頁，共151頁。有效集方法為了求得最優(yōu)得x,只要求得對應(yīng)的最優(yōu)的d,因此,我們只要求解下面的二次規(guī)劃mindTGd/2+g1Td

s.t.x2=0其中求解:因此d1=(-1,0)Tx2=x1+d1