第五章-02投影梯度法

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

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

3、向（可行方向）容許方向（可行方向） Rn中的一個(gè)非空點(diǎn)集D，xD，若對(duì)某個(gè)非0向量d，存在一個(gè)小正數(shù)，對(duì)t(0, ),總有x+td D（容許方向容許方向只與只與約束函數(shù)有關(guān)約束函數(shù)有關(guān)）x設(shè)不等式約束問(wèn)題不等式約束問(wèn)題的可行域?yàn)镈=x|si(x) 0,i=1:mx為任一容許點(diǎn), 記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處的一個(gè)容許方向容許方向的判定定理容許方向的判定定理0*)(Ii 0*)(dxhdxsTiTi進(jìn)一步，對(duì)于等式約束， hi(x)=0稍做等價(jià)變換:hi(x) 0, -hi(x) 0可得相

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

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

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為從點(diǎn) 出發(fā)的容許方向的充要條件： Ad0,Ed=0 設(shè) 是上述問(wèn)題的一個(gè)容許點(diǎn)，適當(dāng)調(diào)換A的行向量與b的相應(yīng)分量成x-(2)利用這個(gè)性質(zhì)，我們可通過(guò)解不等式組(1)利用這個(gè)性質(zhì)，我們可通過(guò)解不等式組注注00EddA來(lái)計(jì)算線性約束問(wèn)題的容許方向000EddAdxfT)(來(lái)計(jì)算

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

8、+x1x2+2x22-6x1-2x2-12x3 s.t. x1+x2+x3=2 -x1+2x2 3 x1,x2,x30求出在點(diǎn)x(0)=(1,1,0)T處的一個(gè)下降可行方向。解 Ad0,Ed=0得到的d即為一個(gè)容許方向 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解出一個(gè)d即為下降可行方向比如(1,-1,0)T下降容許方向的進(jìn)一步確定在所有的可行方向中x-找一個(gè)使得f( )Td最小的方向(即:使得f下降最多)x-意即：mi

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

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

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

12、”(iii)(iii)求解線性規(guī)劃子問(wèn)題求解線性規(guī)劃子問(wèn)題( (確定可行下降方向確定可行下降方向) ) 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)計(jì)算t=minui/(-vi)|vib”(iii)求解線性規(guī)劃子問(wèn)題以確定可行下降方向： 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)計(jì)算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)計(jì)算t=minui/(-vi)|vib”,EAN記 不妨設(shè)N行滿秩(否則可直接去掉多余行),定義Q=I-NT(NNT)-1N,若Qf(x(k) 0,則 d= -Qf(x(k)是下降容許方向。設(shè)N有r行，易驗(yàn)證 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可行： 只要驗(yàn)證Ad0,Ed=0,Nd=-NQ f(x(k) =-NI- NT(NNT)-1Nf(x(k)=-N-N f(x(k)=0ProofProof）對(duì)應(yīng)于對(duì)應(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)對(duì)應(yīng)于N可將q也加以分解這樣上式就成為一般約束問(wèn)題的最優(yōu)性條件一般約束問(wèn)題的最優(yōu)性條件設(shè)x*為混合約束問(wèn)題的一個(gè)極小點(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)線性無(wú)關(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ù))Kuh

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

17、(iii)構(gòu)造N，從而構(gòu)造Q(若N空的話，就取Q=I)(iv)計(jì)算d(k)=- Qf(x(k)(v)若d(k)=0,則計(jì)算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*,則得新的迭代點(diǎn)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解解取初始容許點(diǎn)x(0)=(0,2)T

18、,01211 010 151 1,bA01601 00 0001)(,)()()(xfQdNNNNIQTT取初始容許點(diǎn)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)作線性搜索，從而可得新點(diǎn)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(