第五章-02投影梯度法

1、 可行方向法 & 投影梯度法（Feasible Direction Method & Gradient Projection Method）南京郵電大學(xué)理學(xué)院南京郵電大學(xué)理學(xué)院 2008-05-122008-05-12求解算法分類求解算法分類(1)將這種約束問題轉(zhuǎn)化為無約束問題進行求解(因無約束問題已有較好的求解方法比如BFGS,DFP等)(2)直接從這種約束問題出發(fā)來求解數(shù)學(xué)模型數(shù)學(xué)模型min f(x)s.t. s1(x) 0sm(x) 0h1(x)=0hl(x)=01 1 知識回顧知識回顧起作用約束（有效約束）起作用約束（有效約束） 對容許點 來說，若有不等式約束si(x)

2、 0變成等式，即si( )=0,則該不等式約束稱為關(guān)于容許點 的一個起作用約束；若si( )0則稱之為這個容許點的不起作用約束。xxx則對點則對點(1,0)(1,0)T T來說來說1 1，4 4為有效約束，為有效約束，2 2，3 3為不起作用約束為不起作用約束ABx1x2P例例：某問題的約束函數(shù)分別為：s1(x)=1-x12-x22 0s2(x)=x1-x2 0s3(x)=x1 0s4(x)=x2 0易見易見：不等式約束關(guān)于容許集的任意內(nèi)點都是不起作用約束只有邊界上的點才可能使得某個或某些不等式約束有效按照定義可見，任一等式約束關(guān)于容許點都是起作用約束任一等式約束關(guān)于容許點都是起作用約束容許方

3、向（可行方向）容許方向（可行方向） Rn中的一個非空點集D，xD，若對某個非0向量d，存在一個小正數(shù)，對t(0, ),總有x+td D（容許方向容許方向只與只與約束函數(shù)有關(guān)約束函數(shù)有關(guān)）x設(shè)不等式約束問題不等式約束問題的可行域為D=x|si(x) 0,i=1:mx為任一容許點, 記I=i|si(x)=0,i=1:m當(dāng)iI,si(x)在x處有一階偏導(dǎo)數(shù)，且si(x)Td 0當(dāng)iI,si(x)在x處連續(xù), 則d是x處的一個容許方向容許方向的判定定理容許方向的判定定理0*)(Ii 0*)(dxhdxsTiTi進一步，對于等式約束， hi(x)=0稍做等價變換:hi(x) 0, -hi(x) 0可得相

4、應(yīng)結(jié)果。h hi i(x)(x)T Td=0d=0容許方向容許方向d d的數(shù)學(xué)表達式的數(shù)學(xué)表達式容許下降方向容許下降方向方向d既是點x處的容許方向，又是下降方向0*)(Ii 0*)(0*)(dxhdxsdxfTiTiT容許下降方向容許下降方向d d的數(shù)學(xué)表達式的數(shù)學(xué)表達式(1)如果某點x不是極小點，則繼續(xù)尋優(yōu)時的搜索方向就應(yīng)該從該點的一個可行下降方向上去找（因為這樣就既保證函數(shù)值的下降，又能確保找到的好點是一個可行的）(2)如果某點x*是一個極小點，則在該點就不會有容在該點就不會有容許下降方向許下降方向. .基本迭代格式基本迭代格式(i)從容許點x(0)開始迭代，設(shè)已迭代到x(k)(ii)在x

5、(k)處用某種方法確定一個下降容許方向d(k)(iii)在d(k)方向上尋找一個新的迭代點x(k+1)=x(k)+tkd(k),使得x(k+1)是容許點且f(x(k+1)f(x(k)(iv)判斷終止？ (v)置k：=k+1，轉(zhuǎn)(ii)可行方向法就是一種沿著下降容許方向搜索并保持新的迭代點為容許點的迭代算法。簡要概述簡要概述可行方向法是求解約束問題的一類方法,它一般從線性約束問題開始討論,然后在推廣到非線性約束問題上去,雖然理論上可行方向法對非線性約束問題有效,但實際使用時，一般不使用可行方向法,(一個重要的原因就是工作量太大)所以我們對于可行方向法的重點放在線性約束重點放在線性約束上。（對非線

6、性約束情形不作推廣）ZoutendijkZoutendijk容許方向法容許方向法 (Feasible Direction) (Feasible Direction)min f(x)s.t. Axb Ex=eARmn,ERln,bRm,eRl,f:RnR1有一階偏導(dǎo)數(shù), ,bxAbxAbbbAAA使得定理定理x-則非0向量d為從點 出發(fā)的容許方向的充要條件： Ad0,Ed=0 設(shè) 是上述問題的一個容許點，適當(dāng)調(diào)換A的行向量與b的相應(yīng)分量成x-(2)利用這個性質(zhì)，我們可通過解不等式組(1)利用這個性質(zhì)，我們可通過解不等式組注注00EddA來計算線性約束問題的容許方向000EddAdxfT)(來計算

7、線性約束問題在點 的容許下降方向x)(),(,211100031 0 00 1 00 0 10 2- 1eEbA同時易得例 考慮問題 min x12+x1x2+2x22-6x1-2x2-12x3 s.t. x1+x2+x3=2 -x1+2x23 x1,x2,x30求出在點x(0)=(1,1,0)T處的一個可行方向。這個問題的不等式約束有四個，從而可寫出在x(0)處可看出它的有效約束：A=(0,0,1),b=(0)解不等式：Ad0,Ed=00d1+ 0d2+ 1d3 0,1d1+1d2+1d3=0比如d=(1,-1,0)T就是一個容許方向(但未必是下降方向！)解例(自作) 考慮問題min x12

8、+x1x2+2x22-6x1-2x2-12x3 s.t. x1+x2+x3=2 -x1+2x2 3 x1,x2,x30求出在點x(0)=(1,1,0)T處的一個下降可行方向。解 Ad0,Ed=0得到的d即為一個容許方向 0d1+ 0d2+ 1d3 0, 1d1+1d2+1d3=0再結(jié)合下降的要求 f(x(0)Td0即(-3,3,-12) d0即 -3d1+3d2-12d30從而由d3 0, d1+d2+d3=0 -d1+d2-4d30解出一個d即為下降可行方向比如(1,-1,0)T下降容許方向的進一步確定在所有的可行方向中x-找一個使得f( )Td最小的方向(即:使得f下降最多)x-意即：mi

9、n f( )Td s.t. Ad0 Ed=0(1)求一個下降容許方向就轉(zhuǎn)化為一個子問題的求解，子問題是一個線性規(guī)劃問題，可調(diào)用單純形法求解.(2)這個子問題得到的將是一個無界解,需對這個問題加以修正.則td也滿足此三式,t可無窮大x-d滿足f( )Td0,Ad0,Ed=0由于我們關(guān)心的是確定d的方向，而不是具體長度所以，我們在上述問題中可加上對方向d的長度的限制從而得子問題x-minf( )Td s.t. Ad0 Ed=0 -1dj1，j=1:n因d=0是容許解且f( )T0=0 x-此子問題最優(yōu)值必非正( )（* *）直線搜索直線搜索 從從x x(k)(k)出發(fā)，確定新的迭代點出發(fā)，確定新的

10、迭代點x x(k+1)(k+1) 。使得：。使得： (1) (1) 在下降容許方向在下降容許方向d d上目標(biāo)函數(shù)值下降上目標(biāo)函數(shù)值下降 (2) (2) 新的點新的點x x(k+1)(k+1)是一個容許點是一個容許點. .這也就是這樣的一個一元問題：min f(x(k)+td) s.t. A(x(k)+td) b E(x(k)+td)=e事實上這個問題還可以簡化：首先，由x(k)是容許點，d是容許方向,知:E(x(k)+td)=e恒成立。故上述問題中的第二組等式約束可以直接去掉。min f(x(k)+td) s.t. A(x(k)+td) b其次：對現(xiàn)在所得的這個一元問題還可簡化.不等式約束分為

11、兩部分：A(x(k)+td) b,A”(x(k)+td) b”由Ad0,Ax(k)=b知第一部分也可以直接去掉。從而得一個約束已大大減少的一元問題min f(x(k)+td)s.t. A”(x(k)+td) b”分析： A”(x(k)+td) b”,即A”x(k)-b” -tA”d 設(shè)A”x(k)-b”=u=(u1,u)T,A”d=v=(v1,v)T,從而要u -tv 當(dāng)v0時，顯然問題變成min f(x（k）+td),對t無要求； 當(dāng)v 0不成立即v有分量0,而為使ui -tvi,i=1: 都成立 ， 就必須 tuj/(-vj),jj|vj0 也就是:令t=minuj/(-vj)|vjb”b

12、”(iii)(iii)求解線性規(guī)劃子問題求解線性規(guī)劃子問題( (確定可行下降方向確定可行下降方向) ) min min f(xf(x(k)(k) )T Td d s.t. Ad0 s.t. Ad0 Ed=0 Ed=0 -1d -1dj j11，j=1:nj=1:n 得最優(yōu)解設(shè)為得最優(yōu)解設(shè)為d d(k)(k)ZoutendijkZoutendijk算法算法( (不完整不完整) )(v)若v0,則作e.l.s.得x(k+1)=x(k)+tkd(k),置k:=k+1,轉(zhuǎn)(ii)(vi)計算t=minui/(-vi)|vib”(iii)求解線性規(guī)劃子問題以確定可行下降方向： min f(x(k)Td

13、s.t. Ad0 Ed=0 -1dj1，j=1:n得最優(yōu)解設(shè)為d(k)(iv)若| f(x(k)Td|,則x(k) 即為最優(yōu)解，stop.(v)計算u=A”x(k)-b”,v=A”d(k)(vi)若v0,則作e.l.s.得x(k+1)=x(k)+tkd(k),置k:=k+1,轉(zhuǎn)(ii)(vii)計算t=minui/(-vi)|vib”,EAN記 不妨設(shè)N行滿秩(否則可直接去掉多余行),定義Q=I-NT(NNT)-1N,若Qf(x(k) 0,則 d= -Qf(x(k)是下降容許方向。設(shè)N有r行，易驗證 QTQ=I-NT(NNT)-1NTI-NT(NNT)-1N=I-2 NT(NNT)-1N+ N

14、T(NNT)-1N NT(NNT)-1N=I- 2 NT(NNT)-1N+ NT(NNT)-1N=I- NT(NNT)-1N=Q下降： f(x(k)Td= -f(x(k)TQf(x(k)= - |Qf(x(k)|220可行： 只要驗證Ad0,Ed=0,Nd=-NQ f(x(k) =-NI- NT(NNT)-1Nf(x(k)=-N-N f(x(k)=0ProofProof）對應(yīng)于對應(yīng)于EzAyzyq, (00zEyAxfzyEAxfTTkTk)()()()(即Q Qf(xf(x(k)(k) =0) =0的情況的情況Qf(x(k)=I- NT(NNT)-1Nf(x(k)= f(x(k)- NT(N

15、NT)-1Nf(x(k)= f(x(k)- NTq=0 記 q=(NNT)-1Nf(x(k)對應(yīng)于N可將q也加以分解這樣上式就成為一般約束問題的最優(yōu)性條件一般約束問題的最優(yōu)性條件設(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必非負)Kuh

16、n-TuckerKuhn-Tucker定理定理I=i|si(x*)=0,i=1:m但若y0,即y中有負分量比如yj(可能會有多個，任取一個)，這時將A中與yj相對應(yīng)的那個行整個刪去，仍記刪去該行后的矩陣為N,用這個新的矩陣N構(gòu)造Q，從而構(gòu)造d，這時這個必為下降容許方向(不證)。從而,若y0的話,則上式就是K-T條件，從而知x(k)為KT點。else 0v|vumin-0 v iiit直線搜索直線搜索min f(x(k)+td) s.t. 0tt其中設(shè)得t*,則得新的迭代點x(k+1)=x(k)+t*d投影梯度算法投影梯度算法(i)取初始可行點x(0)，置k:=0(ii)在x(k)處將A，b分解

17、(iii)構(gòu)造N，從而構(gòu)造Q(若N空的話，就取Q=I)(iv)計算d(k)=- Qf(x(k)(v)若d(k)=0,則計算q=(NNT)-1Nf(x(k)并相應(yīng)分解為兩塊y,z 若y0,stop。 否則，修正A，轉(zhuǎn)(iii)(vi)若d(k)0,則求解 min f(x(k)+td(k) s.t. 0tt 設(shè)得t*,則得新的迭代點x(k+1)=x(k)+t*d(k)置k:=k+1,轉(zhuǎn)(ii)0012118221bAxxxf,1 00 110 151 ,)(例例min f(x)=x12+4x22s.t. x1+x21 15x1+10 x212 x1 0 x20解解取初始容許點x(0)=(0,2)T

18、,01211 010 151 1,bA01601 00 0001)(,)()()(xfQdNNNNIQTT取初始容許點x(0)=(0,2)T,第一次迭代：第一次迭代：x x(0)(0)x x(1)(1)在x0處A=(1 0),b=(0)從而N=(1 0)要先生成尋優(yōu)方向d(0),先求解投影矩陣Qx(0)沿著方向d(0)作線性搜索，從而可得新點x(1)=(0,1.2)T.011 01 10120 110 15 ,bAbA000 110 150 101 150 110 150 101 151 00 10 110 15111)()(,)(xfQdNNNNIQNTT從而第二次迭代：第二次迭代：x x(1)(1)x x(2)(2)在x(