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

CompanyLogo4.74.64.54.44.3修正Newton法共軛方向法共軛梯度法變尺度法坐標輪換法第四章常用無約束最優(yōu)化方法4.24.14.8最速下降法Newton法單純形法CompanyLogo4.74.64.54.44.3修正NCompanyLogo成立．點就是問題（4.1）的全局最優(yōu)點．但是，大多數(shù)最優(yōu)化方法只能求到局部最優(yōu)點，即在中找到一點，使得式（4.2)在的某個領(lǐng)域中成立．第四章常用無約束最優(yōu)化法本章開始討論多維無約束最優(yōu)化問題 （4.1）其中．這個問題的求解是指，在中找一點，使得對于任意的都有（4.2）CompanyLogo成立．點就是問題（4.1）的全CompanyLogo

這個矛盾對于實際問題來講一般容易解決，因為根據(jù)問題的實際意義多半可以直接判定用優(yōu)化方法求出的局部最優(yōu)解是否為全局最優(yōu)解．但在理論上這是個比較復雜的問題，本書不涉及．無約束優(yōu)化方法是優(yōu)化技術(shù)中極為重要和基本的內(nèi)容之一．它不僅可以直接用來求解無約束優(yōu)化問題，而且很多約束優(yōu)化問題也常將其轉(zhuǎn)化為無約束優(yōu)化問題，然后用無約束優(yōu)化方法來求解．另外，有些無約束優(yōu)化方法只需略加處理，即可用于求解約束優(yōu)化問題．CompanyLogo這個矛盾對于實際問題來講CompanyLogo

無約束優(yōu)化理論發(fā)展較早，比較成熟，方法也很多，新的方法還在陸續(xù)出現(xiàn)．把這些方法歸納起來可以分成兩大類：一類是僅用計算函數(shù)值所得到的信息來確定搜索方向，通常稱它為直接搜索法，簡稱為直接法，另一類需要計算函數(shù)的一階或二階導數(shù)值所得到的信息來確定搜索方向，這一類方法稱為間接法（或解析法）．直接法不涉及導數(shù)和Hesse矩陣，適應(yīng)性強，但收斂速度一般較慢；間接法收斂速度一般較快，但需計算梯度，甚至需要計算Hesse矩陣．一般的經(jīng)驗是，在可能求得目標函數(shù)導數(shù)的情況下還是盡可能使用間接方法；相反，在不可能求得目標函數(shù)的導數(shù)或根本不存在導數(shù)的情況下，當然就應(yīng)該使用直接法．CompanyLogo無約束優(yōu)化理論發(fā)展較早，CompanyLogo一、最速下降法基本原理在基本迭代公式中，每次迭代搜索方向取為目標函數(shù)的負梯度方向，即，而每次迭代的步長取為最優(yōu)步長，由此所確定的算法稱為最速下降法．

對于問題（4.1）為了求其最優(yōu)解，按最優(yōu)化算法的基本思想是從一個給定的初始點出發(fā)，通過基本迭代公式，按照特定的算法產(chǎn)生一串點列，如果點列收斂，則該點列的極限點為問題（4.1）的最優(yōu)解．§4.1最速下降法

CompanyLogo一、最速下降法基本原理CompanyLogo為了求解問題（4.1），如圖4.1所示，假定我們已經(jīng)迭代了次，獲得了第個迭代點．現(xiàn)在從出發(fā)，可選擇的下降方向很多，一個非常自然的想法是沿最速下降方向（即負梯度方向）進行搜索應(yīng)該是有利的，至少在鄰近的范圍內(nèi)是這樣．因此，取搜索方向為．．圖4.1CompanyLogo為了求解問題（4.1），如CompanyLogo為了使目標函數(shù)在搜索方向上獲得最多的下降，沿進行一維搜索，由此得到第個迭代點，即，其中步長因子按下式確定，也可記為．（4.3）顯然，令就可以得到一個點列，其中是初始點，由計算者任意選定．當滿足一定的條件時，由式（4.3）所產(chǎn)生的點列必收斂于的極小點．CompanyLogo為了使目標函數(shù)在搜索方向上獲得最CompanyLogo以后為書寫方便，記．因此，．在不發(fā)生混淆時，再記．CompanyLogo以后為書寫方便，記CompanyLogo已知目標函數(shù)及其梯度，終止限、和．（1）選定初始點，計算，；置．（2）作直線搜索：；計算，．（3）用終止準則檢測是否滿足：若滿足，則打印最優(yōu)解，，結(jié)束；否則，置，轉(zhuǎn)（2）．最速下降法算法流程如圖4.2所示．二、最速下降法迭代步驟

，CompanyLogo已知目標函數(shù)及其梯度CompanyLogo開始結(jié)束選定X0YX，fH準則滿足最速下降法算法流程如圖所示．圖4.2CompanyLogo開始結(jié)束選定X0YX，fH準則滿CompanyLogo設(shè)第次迭代點為，我們來求的表達式．對式(4.4)關(guān)于求梯度，有，(4.5)因此，．(4.6)現(xiàn)在從出發(fā)沿作直線搜索以確定，于是，(4.7)其中是最優(yōu)步長因子．

將最速下降法應(yīng)用于正定二次函數(shù) （4.4）可以推出顯式迭代公式．CompanyLogo設(shè)第次迭代點為，我們CompanyLogo又因式（4.2），有，再利用式（4.5），式（4.6）和式（4.7）可得或．由此解出，代入式（4.7）中得到.（4.8）這就是最速下降法用于二次函數(shù)的顯式迭代公式．CompanyLogo又因式（4.2），有CompanyLogo例4.1試用最速下降法求函數(shù)的極小點．迭代兩次，計算各迭代點的函數(shù)值，梯度及其模，并驗證相鄰兩個搜索方向是正交的．設(shè)初始點為．CompanyLogo例4.1試用最速下降法求函數(shù)CompanyLogo解與式（4.4）比較，得，梯度表達式是，由，計算出，，．因為目標函數(shù)是二次的，可以使用式（4.8），所以有，CompanyLogo解與式（4.4）比較，得CompanyLogo計算

因為由此說明相鄰兩個搜索方向與、,與是正交的．CompanyLogo計算CompanyLogo三、最速下降法有關(guān)說明

最速下降法的優(yōu)點是算法簡單，每次迭代計算量小，占用內(nèi)存量小，即使從一個不好的初始點出發(fā)，往往也能收斂到局部極小點，但它有一個嚴重缺點就是收斂速度慢．圖4.3沿負梯度方向函數(shù)值下降很快的說法，容易使人們產(chǎn)生一種錯覺，認為這一定是最理想的搜索方向，沿該方向搜索時收斂速度應(yīng)該很快，然而事實證明，梯度法的收斂速度并不快．特別是對于等值線（面）具有狹長深谷形狀的函數(shù)，收斂速度更慢．CompanyLogo三、最速下降法有關(guān)說明

最CompanyLogo其原因是由于每次迭代后下一次搜索方向總是與前一次搜索方向相互垂直，如此繼續(xù)下去就產(chǎn)生所謂的鋸齒現(xiàn)象（如圖4.3所示）．即從直觀上看，在遠離極小點的地方每次迭代可能使目標函數(shù)有較大的下降，但是在接近極小點的地方，由于鋸齒現(xiàn)象，從而導致每次迭代行進距離縮短，因而收斂速度不快．圖4.3CompanyLogo其原因是由于每次迭代后下一次搜索方向CompanyLogo§4.2Newton法

如果目標函數(shù)在上具有連續(xù)的二階偏導數(shù)，其Hesse矩陣正定并且可以表達成為顯式（今后為了簡便起見，記，那么可以使用下述的Newton法．這種方法一旦好用，收斂速度是很快的．它是一維搜索Newton切線法的推廣．圖4.4CompanyLogo§4.2Newton法

CompanyLogo下面具體討論Newton法．設(shè)最優(yōu)化問題為，其中二階可導，Hesse矩陣正定．不妨設(shè)經(jīng)過次迭代已獲點，現(xiàn)將在處展成二階泰勒公式，于是有一、Newton法基本原理為尋求收斂速度快的算法，我們考慮在應(yīng)用基本迭代公式中，每輪迭代在迭代的起始點處用一個適當?shù)亩魏瘮?shù)來近似該點處的目標函數(shù)，由此用點指向近似二次函數(shù)極小點的方向來構(gòu)造搜索方向（如圖4.4所示）．CompanyLogo下面具體討論Newton法．一CompanyLogo顯然是二次函數(shù)，特別由假設(shè)知還是正定二次函數(shù)，所以是凸函數(shù)且存在唯一全局極小點．為求此極小點，令即可解得，亦即

.，(4.9)CompanyLogo顯然是二次CompanyLogo對照基本迭代公式易知，式（4.9）中的搜索方向，步長因子．換句話說從點出發(fā)沿搜索方向并取步長即可得的極小點．因此，是直指點處近似二次函數(shù)的極小點的方向．CompanyLogo對照基本迭代公式CompanyLogo此時稱為從點出發(fā)的Newton方向．從初始點開始，每一輪從當前迭代點出發(fā)，沿Newton方向并取步長的算法稱為Newton法．CompanyLogo此時稱CompanyLogo二、Newton法迭代步驟

已知目標函數(shù)及其梯度，Hesse矩陣，終止限．（1）選定初始點；計算；置．（2）計算．（3）由方程解出．（4）計算．（5）判別終止準則是否滿足：若滿足，則打印最優(yōu)解，結(jié)束；否則，置，轉(zhuǎn)（2）．Newton法的流程如圖4.5所示．CompanyLogo二、Newton法迭代步驟

已知目標CompanyLogo開始結(jié)束選定X0N求解方程H準則滿足X,fNewton法的流程如圖所示圖4.5CompanyLogo開始結(jié)束選定X0N求解方程H準則滿足CompanyLogo解梯度為，Hesse矩陣為，其逆矩陣為．由迭代公式（4.13）得第1迭代點為由于此時，停止迭代得，因此，它就是極小點．例4.2試用Newton法求的極小點，初始點取為．CompanyLogo解梯度為CompanyLogo從上述例4.2我們看到，用Newton法求解，只經(jīng)一輪迭代就得到最優(yōu)解．這一結(jié)果并不是偶然的，因為從Newton方向的構(gòu)造我們知道，對于正定二次函數(shù)，Newon方向就是指向其極小點的方向．因此，用Newton法解目標函數(shù)為正定二次函數(shù)的無約束最優(yōu)化問題，只需一次迭代就可得最優(yōu)解．

CompanyLogo從上述例4.2我們看到，用NewtoCompanyLogo

對于目標函數(shù)是非二次函數(shù)的非約束最優(yōu)化問題，一般地說，用Newton法通過有限輪迭代并不能保證可求得最優(yōu)解．但由于目標函數(shù)在最優(yōu)解附近能近似于二次函數(shù)，因此當先取接近于最優(yōu)解的初始點使用Newton法求解時，其收斂速度一般是快的．事實上，可以證明在初始點離最優(yōu)解不遠的條件下，Newton法是二次收斂的．但是當初始點選得離最優(yōu)解太遠時，Newton法并不一定是收斂的方法，甚至連其下降性也很難保證．CompanyLogoCompanyLogo三、Newton法有關(guān)說明

Newton法收斂速度非?？炀哂卸问諗康膬?yōu)點，但它存在下面四個嚴重的缺點：（1）盡管每次迭代不會使目標函數(shù)上升，但仍不能保證下降．當Hesse矩陣非正定時，Newton法的搜索將會失敗．（2）對初始點要求嚴格．一般要求比較接近或有利于接近極值點，而這在實際計算中是比較難辦的．

CompanyLogo三、Newton法有關(guān)說明CompanyLogo（3）在進行某次迭代時可能求不出搜索方向．由于搜索方向為若目標函數(shù)在點Hesse矩陣為奇異，則求不出，因而不有構(gòu)成牛頓方向，從而使迭代無法進行．（4）牛頓方向構(gòu)造困難，計算相當復雜，除了求梯度以外還需計算Hesse矩陣及其逆矩陣，占用機器內(nèi)存相當大．CompanyLogo（3）在進行某次迭代時可能求不出搜索CompanyLogo§4.3修正Newton法一、修正Newton法基本原理為了克服Newton法的缺點，人們保留選Newton方向作為搜索方向，摒棄其步長恒取1，而用一維搜索確定最優(yōu)步長，由此產(chǎn)生的算法稱為修正Newton法（或阻力Newton法）．CompanyLogo§4.3修正Newton法一、修正CompanyLogo

二、修正Newton法迭代步驟已知目標函數(shù)及其梯度Hesse矩陣終止限（1）選取初始點令（2）求梯度向量．計算，若，停止迭代輸出．否則，轉(zhuǎn)（3）．（3）構(gòu)造Newton方向．計算，

取（4）進行一維搜索．求，使得令，轉(zhuǎn)（2）．修正Newton法的流程如圖4.6所示．．令，轉(zhuǎn)（2）．修正Newton法的流程如圖5.6所示．CompanyLogo二、修正Newton法迭代步驟．，CompanyLogok=0計算求使計算開始結(jié)束選定YN修正Newton法的流程如圖所示．圖4.6CompanyLogok=0計算CompanyLogo三、修正Newton法有關(guān)說明修正Newton法克服了Newton法的缺點．特別是，當

迭代點接近于最優(yōu)解時，此法具有收斂速度快的優(yōu)點，

對初始點的選擇要求不嚴．但是，修正Newton法仍需要計算目標函數(shù)的Hesse矩

陣和逆矩陣，所以求解的計算量和存貯量均很大.另外，

當目標函數(shù)的Hesse矩陣在某點處出現(xiàn)奇異時，迭代將無法進行，因此修正Newton法仍有相當?shù)木窒扌裕瓹ompanyLogo三、修正Newton法有關(guān)說明CompanyLogo§3.4共軛方向法構(gòu)成各種不同最優(yōu)化方法，往往取決于如何從基本迭代公式中確定搜索方向在最速下降法中，由于取從而導致搜索路線出現(xiàn)鋸齒狀，收斂速度降低；而在Newton法中，由于選取收斂速度雖很快，但計算量很大，特別是還要求Hesse矩陣正定，從而導致該算法對初始點選擇要求過嚴．下面我們將給大家介紹一種新的最優(yōu)化方法，它的計算量小，收斂速度沒有Newton法快，但比最速下降法快得多的新算法，稱為共軛方向法．CompanyLogo§3.4共軛方向法構(gòu)成各種不同最優(yōu)CompanyLogo一、共軛方向法基本原理首先介紹共軛方向概念及其些性質(zhì)．

定義4.1

設(shè)是對稱矩陣,對于非零向量若有(4.10),則稱與相互共軛或正交的．對于非零向量組,若有(4.11)則稱是共軛方向組或正交方向組，也稱

它們是一組的共軛方向． CompanyLogo一、共軛方向法基本原理CompanyLogo在上述定義中若(階單位矩陣)，則式（4.10）和式（4.11）成為和由此可知，共軛概念是正交概念的推廣，共軛方向是正交方向的推廣．定理4.1

設(shè)是正定矩陣，是非零向量．若是一組共軛方向，則它們是線性無關(guān)的．CompanyLogo在上述定義中若(CompanyLogo證明設(shè)有一組實數(shù),使得

.依次以左乘上式得到

,(4.12)因為是一組的共軛方向，故有

又由于A是正定矩陣，所以對于有

把以上兩式用于式（4.12），便可推知由此證明是線性無關(guān)．CompanyLogo證明設(shè)有一組實數(shù)CompanyLogo考慮以二次函數(shù)為目標函數(shù)的無約束極小化問題,(4.13)其中是對稱正定矩陣有如下定理：

定理4.2

設(shè)是對稱正定矩陣，是一組

的共軛方向.對于問題（4.13）,若從任意點出發(fā)依次沿進行一維搜索，則至多經(jīng)過輪迭代，可得問題（4.13）的最優(yōu)解．CompanyLogo考慮以二次函數(shù)為目標函數(shù)的無約CompanyLogo證明設(shè)從點出發(fā)依次按方向進行一維搜索產(chǎn)生的迭代點是

,其中最優(yōu)步長是通過下式來確定．又由和式（4.14）可推知即利用式（4.16）有

(4.14)(4.15)(4.16)CompanyLogo證明設(shè)從點出發(fā)依次按方CompanyLogo對上式右乘可得因為是

共軛方向，故得

或.另外，由式（4.15）可知

(4.17)(4.18)CompanyLogo對上式右乘可得(4.17)(4CompanyLogo因為所以由式（4.18）有由式（4.17）和上式，對于我們得到特別地，當時有

.由于是一組

的共軛方向,由定理4.1知它們是線性無關(guān)的,因而向量可表示為這些向量的線性組合,其中是實數(shù).．(4.19)CompanyLogo因為．(4.19)CompanyLogo所以由式（4.19）有

,即有于是得,即是

的駐點．又因為

是對稱正定，故

是凸函數(shù)，因而

是問題（4.13）的最優(yōu)解．這說明，至多經(jīng)過

次迭代必可求得(4.13)的最優(yōu)解.CompanyLogo所以由式（4.19）有CompanyLogo通常，我們把從任意點出發(fā),依次沿某組共軛方向進行一維搜索的求解最優(yōu)化問題的方法,叫做共軛方向法．為了直觀起見,首先考慮二維情況．現(xiàn)在我們把下降法用于形式為(4.13)的二元二次函數(shù)．任選初始點從出發(fā)沿某個下降方向作一維搜索得到(如圖所示)．CompanyLogo通常，我們把從任意點CompanyLogo由式（4.2）知

而且向量所在的直線必與某條等值線（橢圓）相切于點．下一次迭代，如果按最速下降法選擇負梯度方向為搜索方向，那末將要發(fā)生鋸齒現(xiàn)象.為了克服這種現(xiàn)象，我們設(shè)想，下一次迭代的搜索方向?qū)⒅敝笜O小點．如果能夠選定這樣的搜索方向，那么對于二元二次函數(shù)只須順次進行兩次直線搜索就可以求到極小點了．下面來討論這樣的方向應(yīng)該滿足什么條件，怎樣確定．(4.20)CompanyLogo由式（4.2）知(4.20CompanyLogo因為直接指極小點,所以可寫成 其中是最優(yōu)步長因子，顯然，當時，.對（4.13）求導數(shù)，有因為是極小點，所以有.將式（4.21）代入此式中，由（4.22）可得.等式兩邊同時左乘并注意到式(4.20)和,于是有

,(4.21),(4.22).(4.23)CompanyLogo因為直接指極小點CompanyLogo這就是為使直指極小點所必須滿足的條件．顯然（4.23）中和是

的共軛向量．由式（4.20），不難給出的表達式．設(shè)

兩邊同時左乘，有

.由此解出

,代回到式（4.24），得.．，(4.24)CompanyLogo這就是為使直指極小CompanyLogo一般地，在維空間中可以找出個互相共軛的方向，對于元正定二次函數(shù)，從任意初始點出發(fā)，順次沿這個共軛方向最多作次直線搜索就可以求得目標函數(shù)的極小點．這就是共軛方向法的算法形成的基本思想．

CompanyLogo一般地，在維空間中CompanyLogo對于元正定二次目標函數(shù)，從任意初始點出發(fā)，如果經(jīng)過有限次迭代就能夠求得極小點，那么這種算法稱為具有二次終止性．例如Newton法對于二次函數(shù)只須經(jīng)過一次迭代就可以求得極小點，因此是二次終止的；而最速下降法不具有二次終止性；共軛方向法（包括共軛梯度法，變尺度法等）是二次終止的．一般來說，具有二次終止性的算法，在用于一般函數(shù)時，收斂速度較快．CompanyLogo對于元正定二次目CompanyLogo二、共軛方向法迭代步驟已知具有正定矩陣

的二次目標函數(shù)和終止限．（1）選定初始點和具有下降的方向,置

．（2）作直線搜索.（3）判別是否滿足：若滿足，則打印,

結(jié)束；否則轉(zhuǎn)（4）．（4）提供共軛方向使得

.（5），轉(zhuǎn)（2）.共軛方向法的流程如圖4.7所示．CompanyLogo二、共軛方向法迭代步驟CompanyLogo

e<?+)(1kXf

k=0

提供共軛方向1+kP使得

kjQPPkj,,1,0,01L==+T

),(1kkskPXlX=+

開始

停

1+kX

Y

N

k=k+1

選定e,,00PX

共軛方向法的流程如圖所示．圖4.7CompanyLogoe<?+)(1kXfk=0提供CompanyLogo三、共軛方向法有關(guān)說明上述算法針對二次目標函數(shù)，但也可用于一般的非二次函數(shù)．在求優(yōu)過程中因舍入誤差不能滿足時，可取為新的初始點，再重復前面的過程．CompanyLogo三、共軛方向法有關(guān)說明CompanyLogo§5.5共軛梯度法

如果在共軛方向法中初始的共軛向量恰好取為初始點

處的負梯度，而以下各共軛方向由第迭代點處的負梯度與已經(jīng)得到的共軛向量的線性組合來確定，那么就構(gòu)成了一種具體的共軛方向法.因為一個共軛向量都是依賴于迭代點處的負梯度而構(gòu)造出來的，所以稱為共軛梯度法．

CompanyLogo§5.5共軛梯度法

如CompanyLogo一、共軛梯度法基本原理設(shè)從任意點出發(fā)，第一個搜索方向取為處的負梯度方向

.當搜索得到點后，設(shè)以下按來產(chǎn)生搜索方向．為了使選擇使所產(chǎn)生的和是

的共軛，以右乘上式的兩邊，于是有

.．CompanyLogo一、共軛梯度法基本原理．CompanyLogo因為要使和是

的共軛,應(yīng)有故由上式得綜上所述，我們可以生成個方向(4.25)CompanyLogo因為要使和CompanyLogo式（4.25）中含有問題（4.13）的目標函數(shù)系數(shù)陣，這對于目標函數(shù)是非二次函數(shù)的問題是不方便的．通過簡化，一般地我們可以利用目標函數(shù)的梯度信息，來產(chǎn)生個共軛方向

由此得共軛梯度法算法．CompanyLogo式（4.25）中含有問題（4.13）CompanyLogo二、共軛梯度法迭代步驟已知目標函數(shù)，終止限．（1）選取初始點，給定終止限．（2）求初始梯度．計算，若，停止迭代輸出，否則轉(zhuǎn)（3）．（3）構(gòu)造初始搜索方向.取,令,轉(zhuǎn)（4）．（4）進行一維搜索．求使得

,

令，轉(zhuǎn)（5）．CompanyLogo二、共軛梯度法迭代步驟CompanyLogo（5）求梯度向量．計算，若，停止迭代輸出．否則轉(zhuǎn)（6）.（6）檢驗迭代次數(shù)．若，令，轉(zhuǎn)（3），

否則，轉(zhuǎn)（7）．（7）構(gòu)造共軛方向．取,

令，轉(zhuǎn)（4）.共軛梯度法的流程如圖4.8所示．CompanyLogo（5）求梯度向量．計算CompanyLogo結(jié)束求tk使計算開始X0選定YN構(gòu)造初始搜索方向取計算Xk+1YNYN共軛梯度法的流程如圖所示圖4.8CompanyLogo結(jié)束求tk使計算開始X0選定YN構(gòu)造CompanyLogo

例4.3用共軛梯度法求，其中，選初始點.解:顯然CompanyLogo例4.3用共軛梯度法求CompanyLogo所以新的搜索方向由此，有,并且可推知

,.因而得下一迭代點由于停止迭代輸出所求得

.．∴

CompanyLogo所以新的搜索方向．∴CompanyLogo例4.3的迭代的路徑如圖所示．CompanyLogo例4.3的迭代的路徑如圖所示．CompanyLogo三、共軛梯度法有關(guān)說明實際上,可以把共軛梯度法看作是最速下降法的一種改進.當令時,就變?yōu)樽钏傧陆捣?共軛梯度法由于不涉及矩陣,僅僅存儲向量,因而存儲量小,適合于維數(shù)較高的優(yōu)化問題．另外,共軛梯度法不要求精確的直線搜索.但是,不精確的直線搜索可能導致迭代出來的向量不再共軛,從而降低方法的效能.克服的辦法是:重設(shè)初始點,即把經(jīng)過次迭代得到的作為初始點重新迭代．CompanyLogo三、共軛梯度法有關(guān)說明CompanyLogo§3.6變尺度法

我們知道Newton法最突出的優(yōu)點是收斂速度快,在這一點上其它算法無法比擬的.因此,建議凡是Hesse矩陣比較容易求出的問題盡可能使用Newton法求解.然而Newton法還有一個嚴重缺陷,就是每次迭代都要計算目標函數(shù)的Hesse矩陣和它的逆矩陣,當問題的維數(shù)n較大時,計算量迅速增加,從而就抵消了Newton法的優(yōu)點．CompanyLogo§3.6變尺度法

我們知道NeCompanyLogo為此，人們開始尋找一種算法既可以保持Newton法收斂速度快的優(yōu)點，又可以擺脫關(guān)于Hesse矩陣的計算，這就是本節(jié)要給大家介紹的變尺度算法．變尺度法是一種非常好的方法．其中DFP算法和BFGS算法，可以說直到目前為止在不用Hesse矩陣的方法中是最好的算法．CompanyLogo為此，人們開始尋找一種算法既可以CompanyLogo一、變尺度法基本原理在Newton法中，由基本迭代格式,其中,.令,于是有其中是初始點，和分別是目標函數(shù)在

點的梯度和Hesse矩陣．

,(4.26)CompanyLogo一、變尺度法基本原理,(4.26)CompanyLogo為了消除這個迭代公式中的Hesse逆矩陣可用某種近似矩陣來替換它，即構(gòu)造一個矩陣序列去逼近Hesse逆矩陣序列．此時式（4.26）變?yōu)?事實上,式中無非是確定了第次迭代的搜索方向.為了取得更大的靈活性,我們考慮更一般的迭代公式其中步長因子通過從出發(fā)沿作直線搜索來確定.,(4.27)CompanyLogo為了消除這個迭代公式中的HesCompanyLogo式（4.27）是代表很廣的一類迭代公式.例如,當（單位矩陣）時，它變?yōu)樽钏傧陆捣ǖ牡剑疄槭勾_實與近似并且有容易計算的特點，必須對

附加某些條件：第一，為保證迭代公式具有下降性質(zhì)，要求中的每一個矩陣都是對稱正定的．理由是，為使搜索方向是下降方向，只要

成立即可，即成立．當對稱正定時,此式必然成立,從而保證式（4.27)具有下降性質(zhì)．CompanyLogo式（4.27）是代表很廣的一類CompanyLogo第二，要求之間的迭代具有簡單形式．顯然，是最簡單的形式了．其中稱為校正矩陣，式（4.28）稱為校正公式．第三，必須滿足擬Newton條件．,(4.28)CompanyLogo第二，要求之間的迭代具有簡CompanyLogo所謂擬Newton條件由下面的推導給出．設(shè)迭代過程已進行到步，和均已求出，現(xiàn)在推導所必須滿足的條件．設(shè)目標函數(shù)具有連續(xù)的二階偏導數(shù)．現(xiàn)在將在處展成二階泰勒公式:.令，于是有即.．CompanyLogo所謂擬Newton條件由下面的CompanyLogo當正定時，

.當用近似時，由此看出也必須滿足

換句話說，式（4.29）就是稱為近似Newton

條件．為了今后書寫方便，記于是擬Newton條件可寫為， ． .(4.29),,.(4.30)CompanyLogo當正定時，，CompanyLogo二、變尺度法迭代步驟（擬Newton法）已知目標函數(shù)及其梯度,終止限.（1）選定初始點；計算；選定初始矩陣,要求對稱正定（例如）;置．（2）計算搜索方向

．（3）作直線搜索，計算

CompanyLogo二、變尺度法迭代步驟（擬NewtonCompanyLogo（4）判別終止準則是否滿足：若滿足，則就是所求的極小點，打印，結(jié)束；否則轉(zhuǎn)（5）．（5）計算（6）,轉(zhuǎn)（2）．其中校正矩陣可由確定的公式來計算．不同的公式對應(yīng)不同的擬Newton算法．擬Newton算法的流程如圖4.9所示．

CompanyLogo（4）判別終止準則是否滿足：若滿足，CompanyLogok=k+1H準則滿足Xk+1開始結(jié)束選定X0，對稱正定陣H0，置k=0YN擬Newton算法的流程如圖所示．圖4.9CompanyLogok=k+1H準則滿足Xk+1開始結(jié)束CompanyLogo以下幾段將要討論各種公式的構(gòu)成以及相應(yīng)算法．但是不論哪個公式都必須滿足擬Newton條件，由式（4.30）和式（4.28）知，必須滿足或 由此可見，與，和有關(guān)．滿足式（4.31）的有無窮多個，因此上述擬Newton算法構(gòu)成一族算法．下面分別介紹兩個常用的公式．選定,(4.31)CompanyLogo以下幾段將要討論各種公式的構(gòu)CompanyLogo（一）DFP算法DFP算法首先是由Davidon（1959年）提出來的，后來，F(xiàn)letcher和Powell（1963年）對Davidon的方法作了改進，最后才形成DFP算法．D，F(xiàn)，P是這三位學者名字的字頭．這種算法是無約束最優(yōu)化方法最有效的方法之一．CompanyLogo（一）DFP算法CompanyLogo

1．DFP算法基本原理考慮如下形式的校正公式

其中，是待定維向量，，是待定常數(shù)．這時,校正矩陣是現(xiàn)在來確定.根據(jù)擬Newton條件，必須滿足（4.31），于是有

或．．.(4.32)..CompanyLogo1．DFP算法基本原理CompanyLogo滿足以上方程的待定向量和有無窮多種取法，下面是其中的一種：注意到和都是數(shù)量，不妨取同時定出將這兩式代回（4.32）得這就是DFP校正公式．.(4.33),,CompanyLogo滿足以上方程的待定向量CompanyLogo2．DFP算法迭代步驟在擬Newton算法中,只要把第（5）步改為計算式（4.33）

而其它不變，該算法就為DFP算法了．但是由于計算中舍去誤差的影響，特別是直線搜索不精確的影響，可能要破壞迭代矩陣的正定性，從而導致算法失效．為保證的正定性，采取以下重置措施：

迭代次后，重置初始點和迭代矩陣，即以后重新迭代．CompanyLogo2．DFP算法迭代步驟CompanyLogo已知目標函數(shù)及其梯度,問題的維數(shù),終止限(1)選定初始點．計算(2)置(3)作直線搜索

計算(4)判別終止準則是否滿足:若滿足,則打印結(jié)束；否則轉(zhuǎn)(5)．(5)若，則置，轉(zhuǎn)(2);否則,轉(zhuǎn)(6).(6)計算置，轉(zhuǎn)(3).

，，，，.CompanyLogo已知目標函數(shù)及其梯度CompanyLogo例4.4用DFP算法求,取.解:

當我們?nèi)r，DFP法與最速下降法具有相同的第1迭代點，在§4.1中已作了計算CompanyLogo例4.4用DFP算法求CompanyLogo以下用DFP法作第二次迭代按DFP算法中的第（6）步計算因為所以,.CompanyLogo以下用DFP法作第二次迭代,.CompanyLogo搜索方向為從

出發(fā)沿

進行直線搜索，即由知，所以，由于,所以是極小點．CompanyLogo搜索方向為CompanyLogo（二）BFGS算法我們再介紹另一個有效和著名的變尺度算法．由于它是Broyden，F(xiàn)letcher（1970年），Goldfarb（1969年）和Shanno（1970年）共同研究的結(jié)果，因而叫做BFGS算法．CompanyLogo（二）BFGS算法CompanyLogo1．BFGS算法基本原理考慮如下形式的校正公式

式中,

這時校正矩陣為

．(4.34)CompanyLogo1．BFGS算法基本原理．(4CompanyLogo式（4.34）中有一個參數(shù)，它可以取任何實數(shù)，每取一個實數(shù)就對應(yīng)一種擬Newton算法．容易驗證，當取時就是DFP校正公式．令就轉(zhuǎn)變?yōu)橹腄FGS校正公式

.CompanyLogo式（4.34）中有一個參數(shù)CompanyLogo2．DFGS算法迭代步驟已知目標函數(shù)及其梯度,問題的維數(shù),終止限（1）選取初始點,初始矩陣,給定終止限（2）求初始梯度向量，計算,若，停止迭代輸出，否則，轉(zhuǎn)（3）．（3）構(gòu)造初始BFGS方向，取

令,轉(zhuǎn)（4）．（4）進行一維搜索，求，使得，

令，轉(zhuǎn)（5）．CompanyLogo2．DFGS算法迭代步驟CompanyLogo（5）求梯度向量，計算，若，停止迭代輸出；否則，轉(zhuǎn)（6）．（6）檢驗迭代次數(shù)，若,令轉(zhuǎn)（3）；否

則，轉(zhuǎn)（7）．（7）構(gòu)造BFGS方向，用BFGS公式計算，取，令，轉(zhuǎn)（4）．

BFGS算法的流程如圖4.10所示．CompanyLogo（5）求梯度向量，計算CompanyLogo結(jié)束求tk使X0開始計算給定YN構(gòu)造初始BFGS方向,取計算Xk+1用BFGS公式計算Hk+1，取令YNYNDFGS算法的流程如圖所示．

圖4.10CompanyLogo結(jié)束求tk使X0開始計算給定YN構(gòu)造CompanyLogo三、變尺度法有關(guān)說明變尺度法中的二個重要算法DFP算法和BFGS算法，它們的迭代過程相同，區(qū)別僅在于校正矩陣選取不同.對于DFP法，由于一維搜索的不精確和計算誤差的積累可能導致某一輪的奇異，而BFGS法對一維搜索的精度要求不高.并且由它產(chǎn)生的不易變?yōu)槠娈惥仃?FGS法比DFP法更具有好的數(shù)值穩(wěn)定性，它比DFP法更具有實用性．CompanyLogo三、變尺度法有關(guān)說明CompanyLogo§3.7坐標輪換法坐標輪換法屬于直接法．它既可用于無約束最優(yōu)化問題的求解，又可經(jīng)過適當?shù)奶幚碛糜诩s束最優(yōu)化問題的求解．一、坐標輪換法基本原理坐標輪換法的基本思想是把含有n個變量的優(yōu)化問題輪換地轉(zhuǎn)化為單變量（其它變量視為常量）的優(yōu)化問題．所謂單變量優(yōu)化問題就是沿某個坐標軸方向進行一維搜索的問題．CompanyLogo§3.7坐標輪換法坐標輪換法屬CompanyLogo坐標輪換法的尋優(yōu)思路是：先選定一個初始點

作為第一輪搜索的始點，依次沿

個坐標軸方向進行一維搜索，每次只在一個坐標軸方向上改變相應(yīng)變量的值，其它

個變量均保持不變．在沿第一個坐標軸方向進行一維搜索得到目標函數(shù)值的最小點（或近似最小點）后，再以此點作為始點轉(zhuǎn)到沿第二個坐標軸方向進行一維搜索得到,直到沿第

個坐標軸方向搜索結(jié)束得到為一個循環(huán)．如果不滿足收斂準則,則以作為初始點轉(zhuǎn)入下一輪循環(huán),直到經(jīng)過次循環(huán),獲得滿足收斂準則的點,即作為最優(yōu)點.．CompanyLogo坐標輪換法的尋優(yōu)思路是：先選定一CompanyLogo對于二維最優(yōu)化問題，其搜索過程如圖所示．CompanyLogo對于二維最優(yōu)化問題，其搜索過程如圖所CompanyLogo在坐標輪換法中，沿各個坐標軸方向進行一維搜索時，常選用最優(yōu)步長因子或加速步長法．加速步長法則是從初始點出發(fā)，沿搜索（坐標軸）方向先取一個較小的步長，作前進（或后退）試探．如試探成功（目標函數(shù)值有所減小），則按步長序列加大步長（注意每次加大步長都是由初始點算起），直至試探失敗（目標函數(shù)值比前一次的有所增加）時，則取其前一次的步長作為沿這個坐標軸方向搜索的最優(yōu)步長，并計算出該方向上的終止點，而后以這個終止點為始點再進行下一坐標軸方向的搜索，并重復上述步驟．如此迭代下去，直到找到最優(yōu)點．本節(jié)只用一維搜索法來確定最優(yōu)步長．CompanyLogo在坐標輪換法中，沿各個坐標軸方CompanyLogo二、坐標輪換法迭代步驟取初始點置坐標軸搜索方向：首先沿方向進行一維搜索，求出該方向上目標函數(shù)的極值點；再以為初始點沿方向進行一維搜索，得到極值點仿此依次沿進行一維搜索，最終得到極值點．這就完成了第一輪循環(huán)的搜索．，，……．CompanyLogo二、坐標輪換法迭代步驟，，．CompanyLogo如果能夠滿足收斂準則，即可停止搜索，以作為輸出．否則，繼續(xù)以為初始點，進行第二輪循環(huán)，依次沿

進行一維搜索，得到第二循環(huán)的極值點如此進行下去，直至最終找到滿足收斂準則（終止準則）的點，即求得了最優(yōu)解，再求出目標函數(shù)值.具體迭代過程如下：CompanyLogo如果能夠滿足收斂準則，即CompanyLogo已知目標函數(shù),終止限.（1）任選取始點,作為第一輪循環(huán)的初始點,.（2）置搜索方向依次為

,（3）按下式求最優(yōu)步長并進行迭代計算

,

,

，，CompanyLogo已知目標函數(shù),終止限CompanyLogo

上式中，為循環(huán)次數(shù)，;為該循環(huán)中

一維搜索的序號，;為利用一維搜索求出的最優(yōu)步長．（4）如果，即轉(zhuǎn)（5）;如果，則轉(zhuǎn)（3）.（5）收斂性準則：，若滿足判別式,即停止迭代，輸出最優(yōu)解及若不滿足，則令轉(zhuǎn)（3）．

CompanyLogo上式中，為循環(huán)次數(shù)，CompanyLogok=k+1k=1X=X0i=n?開始給定YN沿求使i=1i=i+1N結(jié)束YX*坐標輪換法的計算流程如圖所示．圖4.11CompanyLogok=k+1k=1X=X0i=n?開始CompanyLogo例4.5用坐標輪換法求，初始點.解:

從初始點出發(fā)，依次沿方向搜索，以第一步為例，從

出發(fā)，沿

方向搜索，求得點

CompanyLogo例4.5用坐標輪換法求CompanyLogo得，即，于是得

再從出發(fā)，沿方向搜索，求得點

求

可得，即取，于是有

.CompanyLogo得，即CompanyLogo終止判別,因終止條件不滿足,需繼續(xù)迭代,取,進行第二輪循環(huán)迭代,各輪迭代計算數(shù)據(jù)見下表,最優(yōu)解為.循環(huán)迭代序號是否滿足收斂準則10.00，3.003.133.13，1.561.443.13，1.561.633.45否23.13，1.56－0.502.63，1.56－0.252.63，1.310.160.56否32.63，1.31－0.192.44，1.31－0.092.44，1.220.040.21否42.44，1.22－0.092.35，1.22－0.052.35，1.170.0150.10否52.35，1.17－0.062.29，1.17－0.032.29，1.140.0070.06否62.29，1.14－0.042.25，1.14－0.022.25，1.120.0040.045否72.25，1.12－0.032.22，1.12－0.012.22，1.110.0020.03是CompanyLogo終止判別CompanyLogo三、坐標輪換法有關(guān)說明坐標輪換法的優(yōu)點是算法簡單，計算量小，其缺點是計算效率低，對高維問題尤為突出．因此，坐標輪換法通常用于維數(shù)較低的優(yōu)化問題（一般）．CompanyLogo三、坐標輪換法有關(guān)說明CompanyLogo§4.8單純形法

單純形法是利用對簡單幾何圖形各頂點的目標函數(shù)值作相互比較，在連續(xù)改變幾何圖形的過程中，逐步以目標函數(shù)值較小的頂點取代目標函數(shù)值最大的頂點，從而進行求優(yōu)的一種方法,屬于直接法之一．CompanyLogo§4.8單純形法

單純CompanyLogo一、單純形法基本原理現(xiàn)以求二元函數(shù)的極小點為例,說明單純形法形成原理.設(shè)二元函數(shù)在平面上取不在同一條直線上的三個點,,和，并以它們?yōu)轫旤c構(gòu)成一單純形——三角形．算出各頂點的函數(shù)值，，，比較其大小，現(xiàn)假定比較后有這說明點最差，點最好，點次差．為了尋找極小點，一般來說應(yīng)向最差點的反對稱方向進行搜索．

．這說明CompanyLogo一、單純形法基本原理．CompanyLogo以記為的中點（如圖所示），在的延長線上取點，使

.

稱為關(guān)于的反射點．算出的函數(shù)值，可能出現(xiàn)以下幾種情形：．CompanyLogo以記為CompanyLogo

(1)

這說明搜索方向正確，可進一步擴大效果，繼續(xù)沿

向前搜索，也就是向前擴張．這時取