無(wú)約束優(yōu)化方法

第四章無(wú)約束最優(yōu)化方法第一節(jié)概述第二節(jié)最速下降法第三節(jié)牛頓法第四節(jié)共軛方向法第五節(jié)變尺度法第六節(jié)坐標(biāo)輪換法第七節(jié)powell法作業(yè)第一節(jié)概述一、求解問題二、方法分類解析法數(shù)值法間接法：用導(dǎo)數(shù)信息構(gòu)造搜索方向d(k)直接法：用函數(shù)信息構(gòu)造搜索方向d(k)三、數(shù)值法的基本問題顯然，若使數(shù)值法切實(shí)可行，必需首先解決以下四個(gè)問題：如何確定某點(diǎn)處的搜索方向？如何確定步長(zhǎng)？如何確定迭代過程的終止準(zhǔn)則？如何衡量數(shù)值算法的好壞？

下降性簡(jiǎn)便性收斂性四、算法的收斂性這里X*是無(wú)約束問題的局部解。所謂收斂，是指序列{X(k)}或它的一個(gè)子列(不妨仍記為{X(k)})滿足若對(duì)于某些算法來(lái)說,只有當(dāng)初始點(diǎn)X(0)充分靠近極小點(diǎn)X*時(shí)，才能保證序列{X(k)}收斂到X*，則稱這類算法為局部收斂。反之，若對(duì)任意的初始點(diǎn)X(0)，產(chǎn)生的序列{X(k)}收斂到X*，則稱這類算法為全局收斂.如果算法產(chǎn)生的序列{X(k)}雖然收斂到X*，但收斂的太“慢”，以致于在計(jì)算機(jī)允許的時(shí)間內(nèi)仍得不到滿意的結(jié)果，那么，這類算法也稱不上好算法.五、算法的收斂速率設(shè)序列{X(k)}收斂到x*,若極限存在，當(dāng)0<β<1時(shí)，則稱{X(k)}為線性收斂；當(dāng)β=0，則稱{X(k)}為超線性收斂；因?yàn)榇尉€性收斂的收斂速度太慢，一般不考慮它。設(shè)序列{X(k)}收斂到x*，存在某個(gè)p≥1，若極限存在則稱{X(k)}為p階收斂。當(dāng)p>1時(shí)，p階收斂必為超線性收斂，但反之不一定成立。在最優(yōu)化算法中，通?？紤]線性收斂、超線性收斂和二階收斂。上面談到的收斂性和收斂速率能夠較為準(zhǔn)確地刻劃出算法的優(yōu)劣程度，但使用起來(lái)比較困難。特別是證明一個(gè)算法是否收斂或具有什么樣的收斂速率，需要很強(qiáng)的理論知識(shí)。在這里給出一較為簡(jiǎn)單地判斷算法優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)——算法的二次終止性。定義：若某個(gè)算法對(duì)于任意的正定二次函數(shù)，從任意的初始點(diǎn)出發(fā)，都能經(jīng)有限步迭代達(dá)到其極小點(diǎn)，則稱該算法具有二次終止性。六、算法的二次終止性從某一點(diǎn)X(k)出發(fā)，以該點(diǎn)的最速下降方向：即負(fù)梯度方向－f(X(k))，進(jìn)行一維搜索，得最優(yōu)步長(zhǎng)k，從而獲得新的迭代點(diǎn)X(k+1)，如此重復(fù)迭代，即得到無(wú)約束問題的最優(yōu)解.第二節(jié)最速下降法一、方法說明二、幾何說明相鄰兩次搜索方向正交，由得(1)取初始點(diǎn)X(0)，精度指標(biāo)，置k=0.三、算法步驟(2)若則停止計(jì)算，將X(k)作為無(wú)約束問題的最優(yōu)解輸出；否則置(3)求解一維問題(4)置k=k+1，轉(zhuǎn)(2).得3.若一維搜索是精確的，則最速下降法產(chǎn)生的相鄰兩次的搜索方向是相互正交的。四、算法特點(diǎn)由此表明，最速下降法相鄰的兩次迭代的前進(jìn)方向是相互垂直的，因而整個(gè)行進(jìn)路徑呈鋸齒形，因此從全局來(lái)看,收斂較慢。從前面的分析可以得到這樣一個(gè)結(jié)論：最速下降法不最速。換句話說，最速下降方向未必是最好的搜索方向。應(yīng)該考慮其它的下降方向作為搜索方向。1.要求目標(biāo)函數(shù)連續(xù)可導(dǎo)；2.當(dāng)初始點(diǎn)遠(yuǎn)離最優(yōu)點(diǎn)時(shí)，或目標(biāo)函數(shù)形態(tài)。接近于圓（或球）時(shí)，步長(zhǎng)較大，收斂較快；1Newton法的基本思想若x*是無(wú)約束問題的局部解，則x*滿足第三節(jié)牛頓法因此,可以通過求解該方程組來(lái)得到無(wú)約束最優(yōu)化問題解。注意到該方程組是非線性的，處理起來(lái)比較困難，因此考慮原目標(biāo)函數(shù)在點(diǎn)X(k)處的一個(gè)二次逼近：該二次函數(shù)的極小點(diǎn)可由下式求得：即：將二次函數(shù)的這個(gè)極小點(diǎn)作為原目標(biāo)函數(shù)極小點(diǎn)的近似，即：由此可見，牛頓法的搜索方向?yàn)椋翰介L(zhǎng)為：(1)取初始點(diǎn)X(0)，精度指標(biāo)，置k=0.(2)若則停止計(jì)算，將X(k)作為無(wú)約束問題的最優(yōu)解輸出；否則置(3)求新的迭代點(diǎn)(4)置k=k+1，轉(zhuǎn)(2).2算法步驟：3例題Newton法的優(yōu)點(diǎn):(1)Newton法產(chǎn)生的點(diǎn)列{X(k)}若收斂，則收斂速度快，具有二階收斂速率(證明略)。(2)Newton法具有二次終止性。4算法特點(diǎn)：Newton法的缺點(diǎn):(1)可能會(huì)出現(xiàn)在某步迭代時(shí)目標(biāo)函數(shù)值上升，即存在k，使得f(X(k+1))>f(X(k))。如在上例中,取x(1)=(1，1)T，f(x(1))=4，由Newton法得到的x(2)=(-0.75,-1.25)T，此時(shí)，f(x(2))=4.5156函數(shù)值上升。(2)當(dāng)初始點(diǎn)x(1)距x*較遠(yuǎn)時(shí)，產(chǎn)生的點(diǎn)列{X(k)}可能不收斂；或者收斂到鞍點(diǎn)；或者H(x(k))奇異無(wú)法計(jì)算。(3)需要計(jì)算Hesse矩陣,計(jì)算量大。修正Newton法是針對(duì)缺點(diǎn)(1)提出改進(jìn)方案的。為了避免函數(shù)值上升，在算法中增加一維搜索策略，即將d(k)作為搜索方向(此時(shí)稱d(k)為Newton方向)，而不是作為增量，由此得到如下算法.5.修正Newton法修正Newton法保持了Newton法的優(yōu)點(diǎn),，如算法的二次終止性等，克服了目標(biāo)函數(shù)值上升的缺點(diǎn)，由于增加了一維搜索，對(duì)缺點(diǎn)(2)有所改善，但不能完全克服。對(duì)于缺點(diǎn)(3)沒有任何改進(jìn)，因?yàn)樾拚齆ewton法仍需要計(jì)算Hesse矩陣。另一種修正方案是將Newton方向與最速下降方向相結(jié)合。設(shè)d(k)N是Newton方向，即d(k)N滿足這里假設(shè)H(X(k))非奇異。設(shè)θk是dN(k)與-f(X(k))之間的夾角。當(dāng)然希望θk不要大于π/2,即存在正數(shù)0<η<1,使得cosθk≥η.Goldstein和Price在1967年提出的修正方案是令這樣得到的d(k)總是下降方向，并滿足cosθk≥ηcosθk≥η其他第四節(jié)共軛方向法一、共軛方向的概念對(duì)于一個(gè)二維二次函數(shù)其等值線為同心橢圓族兩次一維搜索即可達(dá)到最優(yōu)點(diǎn)，兩次搜索方向滿足什么條件？由無(wú)約束最優(yōu)點(diǎn)的必要條件得：即上式兩邊同左乘以d(0)，得：又由于故得稱方向d(0)與方向d(1)關(guān)于矩陣A共軛二、共軛方向的定義設(shè)矩陣A為nn的對(duì)稱正定矩陣，若n維空間中有m個(gè)非零向量d(0)，d(1)，，d(m-1)，滿足則稱向量d(0)，d(1)，，d(m-1)關(guān)于矩陣A相互共軛；當(dāng)矩陣A為單位矩陣時(shí)，則稱向量d(0)，d(1)，，d(m-1)相互正交。三、共軛方向的性質(zhì)1.若m個(gè)非零向量d(0)，d(1)，，d(m-1)關(guān)于矩陣A相互共軛，則這m個(gè)非零向量線性無(wú)關(guān)。2.從任意初始點(diǎn)出發(fā)X(0)，順次沿n個(gè)關(guān)于矩陣A共軛方向d(0)，d(1)，，d(n-1)進(jìn)行一維搜索，最多經(jīng)過n次迭代，就可求得n維二次函數(shù)的理論極小點(diǎn)X*，即以共軛方向d(0)，d(1)，，d(n-1)作為搜索方向的方法具有二次收斂性。即證明：X(0)為任意初始點(diǎn)。若d(0)，d(1)，，d(n-1)為n個(gè)關(guān)于矩陣A的共軛方向，則它們可作為n維空間的一組基向量，則有設(shè)n維二次函數(shù)的理論極小點(diǎn)為X*兩邊左乘d(0)TA，得：又由于：故得：記：則同理可得下面證明，由X(k)出發(fā)，沿共軛方向d(k)進(jìn)行一維搜索，得點(diǎn)X(k＋1)，即其步長(zhǎng)如下確定：由此可見：故證其步長(zhǎng)為：四、共軛方向的構(gòu)造對(duì)于n個(gè)線性無(wú)關(guān)向量e(0)，e(1)，，e(n-1)，對(duì)其進(jìn)行關(guān)于矩陣A的共軛化處理，得n個(gè)共軛方向d(0)，d(1)，，d(n-1)。然后順次沿這n個(gè)共軛方向進(jìn)行一維搜索，這就是共軛方向法的基本思想。由初始點(diǎn)X(0)出發(fā)，對(duì)于n維二次函數(shù)首先取令由d(0)，d(1)關(guān)于矩陣A的共軛，得：令由d(k+1)與d(0)，d(1)，…，d(k)關(guān)于矩陣A的共軛，得：開始置e(j)=[0,0,..,1,0..,0]，j=0,1,…,n-1Min

()=f(X(k),l+d(k))

X(k+1),l=

X(k),l+k

d(k)

k<n?置X(l+1)=X(n)l,l=l+1結(jié)束yesnoyesno五、共軛方向法算法框圖置X(0),l=X(l),A=H(X(l))置d(0)=e(0)

,k=0k=k+1輸出:X*=X(n),l和f

*=f(X(n),l)輸入:n,,X(0)?六、共軛梯度法共軛梯度法(ConjugateGraientMethod)是最著名的共軛方向方法，它首先由Hestenes和Stiefel在1952年提出來(lái)作為解線性方程組的方法。1964年Fletcher和Reeves應(yīng)用于求解無(wú)約束問題。在該方法中每個(gè)共軛方向的構(gòu)造都依賴于迭代點(diǎn)處的負(fù)梯度，而不必確定矩陣A。對(duì)于一個(gè)二維二次函數(shù)由初始點(diǎn)X(k)出發(fā)，沿共軛方向d(k)，進(jìn)行一維搜索，得點(diǎn)

X(k＋1)，即或在點(diǎn)X(k)、點(diǎn)X(k＋1)處的梯度記為：設(shè)方向d(j)與方向d(k)關(guān)于矩陣A共軛，則有此式表明，沿方向d(k)進(jìn)行一維搜索,其終點(diǎn)X(k＋1)和始點(diǎn)X(k)的梯度之差，與d(k)的共軛方向正交。共軛梯度法就是利用這個(gè)性質(zhì)做到不必計(jì)算矩陣A就能求得共軛方向的。共軛梯度法的計(jì)算過程1.由X(0)出發(fā)，沿方向d(0)＝－g0＝－f(X(0))進(jìn)行一維搜索，得點(diǎn)X(1)，即2.令g1＝f(X(1))，則g1與d(0)(＝g0)正交，在該正交系中求與方向d(0)共軛的方向d(1)，令由共軛方向d(1)與梯度關(guān)系：得：即：由X(1)出發(fā)，沿方向d(1)進(jìn)行一維搜索，得點(diǎn)X(2)，即令g2＝f(X(2))，則g2與d(1)正交，即由共軛方向d(0)與梯度關(guān)系：3.在g0、g1、

g2所構(gòu)成的正交系中，求與方向d(0)及d(1)均共軛的方向d(2)，設(shè)因?yàn)橐骴(2)與d(0)和d(1)均共軛，由共軛方向與梯度關(guān)系得：考慮到g0、g1、

g2相互正交，故有故得共軛梯度法共軛方向生成通式共軛梯度法的特點(diǎn)：1.共軛梯度法可看作是對(duì)最速下降法的修正，故收斂速度較最速下降法快；2.共軛梯度法具有二次收斂性；3.共軛梯度法程序簡(jiǎn)單，存儲(chǔ)量小，對(duì)初始點(diǎn)要求不嚴(yán)。4.共軛梯度法梯度模較小時(shí)容易上溢出。第五節(jié)變尺度法變尺度法(VariableMetricMethod)也稱為擬Newton法(Quasi-NewtonMethod)，是求解無(wú)約束最優(yōu)化問題最有效的算法之一，它不需要求二階Hesse矩陣，而只利用一階導(dǎo)數(shù)來(lái)構(gòu)造二階信息的近似矩陣，從而該算法有較好的收斂性質(zhì)。一、尺度矩陣的概念變量的尺度變換就是對(duì)其坐標(biāo)進(jìn)行放大或縮小處理，達(dá)到降低函數(shù)偏心率的目的。對(duì)于二次函數(shù)進(jìn)行尺度變換則函數(shù)的二次項(xiàng)變?yōu)槿艟仃嘓是正定的，則一定存在尺度矩陣Q，使由此可見，二次函數(shù)的Hesse矩陣H的逆陣H-1，可以通過尺度矩陣Q求得。Newton法迭代公式因此而變?yōu)椋禾荻确ǖ綖椋河浄Q為尺度矩陣則Newton法和梯度法的迭代公式可統(tǒng)一寫為：為了避免在牛頓法中直接計(jì)算目標(biāo)函數(shù)f(X)的Hesse矩陣的逆陣[H(X(k))]-1，故構(gòu)造一個(gè)尺度矩陣序列{Ak}來(lái)逼近[H(X(k))]-1,則稱Ak為變尺度矩陣。從而可得變尺度法的迭代公式為：二、變尺度矩陣的構(gòu)造原則：1.為了保證迭代公式具有下降性質(zhì)，要求{Ak}中的每個(gè)矩陣都是對(duì)稱正定的。2.為了計(jì)算簡(jiǎn)便，要求Ak具有如下的遞推關(guān)系：3.為了獲得牛頓法的收斂速度，要求Ak[H(X(k))]-1。Ak不可能在數(shù)值上近似于[H(X(k))]–1，因?yàn)槲覀兊哪繕?biāo)是不計(jì)算Hesse矩陣[H(X(k))]–1。那么，Ak只能在性質(zhì)上近似[H(X(k))]–1。因此，先研究一下Hesse矩陣的逆陣[H(X(k))]–1的性質(zhì)?？紤]f(X)在X(k)處的Taylor展開式令X=X(k+1)，得求梯度得記則得擬牛頓條件：令A(yù)k+1滿足擬牛頓條件，得：即滿足上述擬牛頓條件的Ak有無(wú)窮多個(gè)，因此變尺度法是一族方法。三、DFP變尺度矩陣DFP公式是由Daviden在1959年提出來(lái)的，后由Fletcher和Powell在1963年于以簡(jiǎn)化，故此而得名的。設(shè)代入擬牛頓條件得：比較系數(shù)得：DFP變尺度矩陣迭代公式為：四、BFGS變尺度矩陣由于DFP變尺度法的數(shù)值穩(wěn)定性差，1970年由Brogden、Fletcher、Goldfarb、Shanno提出數(shù)值穩(wěn)定性好的BFGS變尺度法，其尺度矩陣迭代公式如下：五、變尺度矩陣的統(tǒng)一表達(dá)式1970年Huang對(duì)變尺度矩陣迭代公式進(jìn)行了統(tǒng)一處理，得出如下公式：其中當(dāng)取為DFP公式當(dāng)取為BFGS公式當(dāng)取當(dāng)取為McCormick公式為Pearson公式(1)取初始點(diǎn)X(0)，置初始矩陣A0=I，置精度要求ε,置k=0.六、變尺度法的算法步驟(2)計(jì)算gk=f(X(k))，如果‖f(X(k))‖≤ε，則停止計(jì)算，將X(k)作為無(wú)約束問題的解輸出；否則計(jì)算搜索方向(3)沿d(k)方向進(jìn)行一維搜索,即求解一維問題(4)計(jì)算gk+1=f(X(k+1)),gk=gk+1-

gk，Xk=X(k+1)-

X(k)修正矩陣Ak和尺度矩陣Ak+1

=Ak+Ak得：(5)置k=k+1，若k<n,轉(zhuǎn)(2)；否則X(0)=X(k+1),A0=I，k=0，轉(zhuǎn)(2).七、變尺度法的特點(diǎn)1、算法具有下降性2、算法具有二次收斂性定理：設(shè)矩陣Ak正定對(duì)稱矩陣，且XkTgk>0，則由DFP公式(或BFGS公式)構(gòu)造的Ak+1是正定對(duì)稱的。若一維搜索是精確的，假設(shè)已進(jìn)行了m次迭代，則:定理：若用DFP算法(或BFGS算法)求解正定二次函數(shù)(1)搜索方向d(0),d(1),…,d(m-1)是m個(gè)非零的H共軛方向;(2)對(duì)于j=0，2，…，m-1，有AmXj=gj

且當(dāng)m=n-1時(shí)，有An=H-1證明：僅對(duì)DFP公式進(jìn)行證明即可.由于XkTgk>0，蘊(yùn)含著gk≠0，再由Ak的正定性，得到

gkTAk

gk>0，因此DFP公式有意義。對(duì)任意的x∈Rn，考察由廣義Cauchy-Schwarz不等式證得Ak＋1是正定的，其對(duì)稱性是顯然的.證明：由算法知，搜索方向d(0),d(1),…,d(m-1)是零的。現(xiàn)證明其共軛性。用數(shù)學(xué)歸納法證明：八、變尺度法的算例用DFP變尺度法求解下述無(wú)約束優(yōu)化問題第六節(jié)坐標(biāo)輪換法

(CyclicCoordinateMethod)

一、方法簡(jiǎn)介取搜索方向?yàn)樽鴺?biāo)軸方向，即沿該方向求最優(yōu)點(diǎn)，即每次迭代只改變?cè)O(shè)計(jì)變量X的一個(gè)分量的值，而其他分量的值保持不變，故該方法又稱為降維法。二、幾何說明現(xiàn)以二維函數(shù)極小化問題為例，說明坐標(biāo)輪換法的尋優(yōu)過程。由沿求即即由沿求完成第一輪搜索，若則停止搜索；負(fù)責(zé)進(jìn)行下一輪搜索。三、算法框圖開始X1(0)=X(0),l=1輸入X(0),,nk=1min()=f(Xl(k-1)+

ek)Xl(k)=Xl(k-1)+kl

ekk=n

?nok=k+1yes

?yes開始Xl+1(0)=Xl(n)l=l+1no輸出X(*)=Xl(n)四、方法特點(diǎn)1、簡(jiǎn)單、方便；2、對(duì)函數(shù)無(wú)連續(xù)性要求；3、收斂速度慢；4、可能產(chǎn)生偽最優(yōu)。第七節(jié)powell法一、共軛方向的直接生成對(duì)于一個(gè)二次函數(shù)設(shè)點(diǎn)X(k)和點(diǎn)X(k＋1)是從不同出發(fā)點(diǎn)，沿同一方向d(k)進(jìn)行一維搜索而得的兩個(gè)極小點(diǎn)，則方向d(k)與點(diǎn)X(k)和點(diǎn)X(k＋1)處的梯度有如下關(guān)系：上面兩式相減得：記則即d(k)與d(k＋1)關(guān)于矩陣A共軛二、基本算法以二維問題為例，介紹Powell基本算法1）任取初始點(diǎn)X1(0)，沿各個(gè)坐標(biāo)軸方向(基本方向)進(jìn)行一維搜索，即2）產(chǎn)生新生方向，并由X1(2)出發(fā)，沿新生方向進(jìn)行一維搜索，即3）用新生方向d1擠掉原基本方向組中的第一個(gè)方向e1,形成新的基本方向組e2,d1。4）令進(jìn)行下一輪搜索。對(duì)于二元二次目標(biāo)函數(shù)則可得其理論最優(yōu)解。三、基本算法框圖開始X1(0)=X(0),l=1輸入X(0),,ni=1min()=f(Xl(i-1)+

di)Xl(i)=Xl(i-1)+il

dii=n

?noi=i+1yes

?yes輸出X(*)=Xl(n)開始基本方向取為di,i=2,n＋1Xl+1(0)=Xl(n＋1),l=l+1no將n個(gè)坐標(biāo)方向作為初始基本方向di,i=1,ndn+1=Xl(n)-Xl(0)min()=f(Xl(i-1)+

dn+1)Xl(n+1)=Xl(n)+ln+1dn+1l=n

?yesnoX1(0)=Xl(n+1),l=1四、基本算法的缺陷

POWELL基本算法在迭代中逐次生成共軛方向，而共軛方向是較好的搜索方向，所以鮑威爾法又稱作方向加速法。上述基本算法僅具有理論意義，不要說對(duì)于一般函數(shù)，就是對(duì)于二次函數(shù)，這個(gè)算法也可能失效，因?yàn)樵诘械膎個(gè)搜索方向有時(shí)會(huì)變成線性相關(guān)而不能形成共軛方向。這時(shí)張不成n維空間，可能求不到極小點(diǎn)，所以上述基本算法有待改進(jìn)。在鮑威爾基本算法中，每一輪迭代都用連結(jié)始點(diǎn)和終點(diǎn)所產(chǎn)生出的搜索方向去替換原向量組中的第一個(gè)向量，而不管它的“好壞”，這是產(chǎn)生向量組線性相關(guān)的原因所在。因此在改進(jìn)的算法中首先判斷原向量組是否需要替換。如果需要替換，還要進(jìn)一步判斷原向量組中哪個(gè)向量最壞，然后再用新產(chǎn)生的向量替換這個(gè)最壞的向量，以保證逐次生成共軛方向。五、修正算法步驟1)給定初始點(diǎn)Xo(記作X0o)，選取初始方向組，它由n個(gè)線性無(wú)關(guān)的向量d10，d20，,dn0(如可取n個(gè)坐標(biāo)軸單位向量e1，e2

，,en)所組成，置k=0;2)從X0k出發(fā)，順次沿方向d1k，d2k，,dnk作一維搜索，得點(diǎn)X1