第4章 無約束優(yōu)化方法

第四章無約束優(yōu)化方法§4-1最速下降法（梯度法）§4-2牛頓類方法§4-3共軛方向法§4-4共軛梯度法§4-5變尺度法§4-6坐標(biāo)輪換法§4-7鮑威爾方法§4-8單形替換法第1章所列舉的機(jī)械優(yōu)化設(shè)計(jì)問題，都是在一定的限制條件下追求某一指標(biāo)為最小，它們都屬于約束優(yōu)化問題。工程問題大都如此。

為什么要研究無約束優(yōu)化問題?

（1）有些實(shí)際問題，其數(shù)學(xué)模型本身就是一個無約束優(yōu)化問題。

（2）通過熟悉它的解法可以為研究約束優(yōu)化問題打下良好的基礎(chǔ)。

（3）約束優(yōu)化問題的求解可以通過一系列無約束優(yōu)化方法來達(dá)到。所以無約束優(yōu)化問題的解法是優(yōu)化設(shè)計(jì)方法的基本組成部分，也是優(yōu)化方法的基礎(chǔ)。無約束優(yōu)化問題是：求n維設(shè)計(jì)變量使目標(biāo)函數(shù)

目前已研究出很多種無約束優(yōu)化方法，它們的主要不同點(diǎn)在于構(gòu)造搜索方向上的差別。（1）間接法——要使用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)構(gòu)造搜索方向，如梯度法、（阻尼）牛頓法、變尺度法、共軛梯度法等。（2）直接法——不使用導(dǎo)數(shù)信息，只利用目標(biāo)函數(shù)值構(gòu)造搜索方向，如坐標(biāo)輪換法、鮑威爾法、單純形法等。4-1梯度法

基本思想：函數(shù)的負(fù)梯度方向是函數(shù)值在該點(diǎn)下降最快的方向。將n維問題轉(zhuǎn)化為一系列沿負(fù)梯度方向用一維搜索方法尋優(yōu)的問題，利用負(fù)梯度作為搜索方向，故稱最速下降法或梯度法。

搜索方向s取該點(diǎn)的負(fù)梯度方向(最速下降方向)，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快。

為了使目標(biāo)函數(shù)值沿搜索方向能夠獲得最大的下降值，其步長因子應(yīng)取一維搜索的最佳步長。即有

根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得圖4-2最速下降法的搜索路徑

在最速下降法中，相鄰兩個迭代點(diǎn)上的函數(shù)梯度相互垂直。而搜索方向就是負(fù)梯度方向，因此相鄰兩個搜索方向互相垂直。這就是說在迭代點(diǎn)向函數(shù)極小點(diǎn)靠近的過程，走的是曲折的路線。形成“之”字形的鋸齒現(xiàn)象，而且越接近極小點(diǎn)鋸齒越細(xì)。梯度法計(jì)算步驟例4－1求目標(biāo)函數(shù)的極小點(diǎn)。解取初始點(diǎn)則初始點(diǎn)處函數(shù)值及梯度分別為沿負(fù)梯度方向進(jìn)行一維搜索，有為一維搜索最佳步長，應(yīng)滿足極值必要條件

算出一維搜索最佳步長

第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值

繼續(xù)作下去，經(jīng)10次迭代后，得到最優(yōu)解

這個問題的目標(biāo)函數(shù)的等值線為一簇橢圓,迭代點(diǎn)從走的是一段鋸齒形路線，見圖4-3。圖4-3等值線為橢圓的迭代過程將上例中目標(biāo)函數(shù)引入變換y1=x1,y2=5x2則函數(shù)f(X)變?yōu)椋浩涞戎稻€由橢圓變成一簇同心圓。

仍從

即

出發(fā)進(jìn)行最速下降法尋優(yōu)。此時：沿負(fù)梯度方向進(jìn)行一維搜索：β為一維搜索最佳步長，可由極值條件：由從而算得一步計(jì)算后設(shè)計(jì)點(diǎn)的位置及其目標(biāo)函數(shù)：經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是因?yàn)榻?jīng)過尺度變換：等值線由橢圓變成圓。等值線為圓的迭代過程比較以上兩種函數(shù)形式二次型函數(shù)的對角形矩陣刻畫了橢圓的長短軸，它們是表示度量的矩陣或者是表示尺度的矩陣。最速下降法的收斂速度和變量的尺度關(guān)系很大，在適當(dāng)條件下，最速下降法的收斂速度估計(jì)式為M——f（x）海塞矩陣最大特征值上界m——f（x）海塞矩陣最小特征值下界梯度法的特點(diǎn)（1）理論明確，程序簡單，對初始點(diǎn)要求不嚴(yán)格。每迭代一次除需進(jìn)行一維搜索外，只需計(jì)算函數(shù)的一階導(dǎo)數(shù)，計(jì)算量小。（2）梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，在遠(yuǎn)離極小點(diǎn)時逼近速度較快，而在接近極小點(diǎn)時逼近速度較慢。（3）按負(fù)梯度方向搜索并不等同于以最短時間到達(dá)最優(yōu)點(diǎn)，對一般函數(shù)而言，梯度法的收斂速度并不快，因?yàn)樽钏傧陆捣较騼H僅是指迭代點(diǎn)的一個局部性質(zhì)，從局部上看，在一點(diǎn)附近函數(shù)下降是最快的，但從整體看則走了許多彎路，下降的并不算快。（4）梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)和初始點(diǎn)的位置選擇密切有關(guān)。對于等值線(面)為同心圓（球）的目標(biāo)函數(shù)，一次搜索即可達(dá)到極小點(diǎn)。最速下降法采用了函數(shù)的負(fù)梯度方向作為下一步的搜索方向，整個搜索過程收斂速度較慢，這是它的主要缺點(diǎn)。但是，應(yīng)用最速下降法可以使目標(biāo)函數(shù)在開頭幾步下降很快，所以它可與其它無約束優(yōu)化方法配合使用，特別是一些更有效的方法都是在對它進(jìn)行改進(jìn)后，或在它的啟發(fā)下獲得的，因此最速下降法仍是有約速和無約束優(yōu)化方法的基礎(chǔ)。4-2牛頓類方法基本思想：在xk鄰域內(nèi)用一個二次函數(shù)來近似代替原目標(biāo)函數(shù)，并將的極小點(diǎn)作為對目標(biāo)函數(shù)求優(yōu)的下一個迭代點(diǎn)。經(jīng)多次迭代，使之逼近目標(biāo)函數(shù)的極小點(diǎn)。設(shè)為的極小點(diǎn)

一維情況的牛頓迭代公式k+1=kf

(k)/f(k)k=0,1,2,對于多元函數(shù)f(x),設(shè)xk為f(x)極小點(diǎn)x*的一個近似點(diǎn)，在xk處將f(x)進(jìn)行泰勒展開，保留到二次項(xiàng)，得到海塞矩陣這就是多元函數(shù)求極值的牛頓法迭代公式。

對于二次函數(shù)，海賽矩陣H是一個常矩陣，其中各元素均為常數(shù)。因此，無論從任何點(diǎn)出發(fā)，只需一步就可找到極小點(diǎn)。

例4－2求目標(biāo)函數(shù)的極小點(diǎn)。解取初始點(diǎn)則初始點(diǎn)處的函數(shù)梯度、海賽矩陣及其逆陣分別為牛頓方向經(jīng)過一次迭代即求得極小點(diǎn)函數(shù)極小值

從牛頓法迭代公式的推演中可以看到，迭代點(diǎn)的位置是按照極值條件確定的，其中并未含有沿下降方向搜尋的概念。因此對于非二次函數(shù)，如果采用上述牛頓迭代公式，有時會使函數(shù)值上升。阻尼牛頓法

阻尼因子，沿牛頓方向進(jìn)行一維搜索的最佳步長，由下式求得：

阻尼牛頓法每次迭代都在牛頓方向上進(jìn)行一維搜索，避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法的二次收斂性，而對初始點(diǎn)的選擇沒有要求。阻尼牛頓法的迭代步驟：例用牛頓法求解下列方法：給定初始點(diǎn)解目標(biāo)函數(shù)f(x)的梯度和海塞矩陣是在x(1)處，目標(biāo)函數(shù)f(x)的梯度和海塞矩陣是牛頓方向從x(1)出發(fā)，沿d(1)作一維搜索，令步長變量為λ，最優(yōu)步長為λ1，則有令故上述想x（2）即極小點(diǎn)。牛頓法方法特點(diǎn)

（1）初始點(diǎn)應(yīng)選在極小值X*附近，有一定難度；（2）盡管每次迭代都不會使函數(shù)值上升，但不能保證每次下降；（3）若迭代點(diǎn)的海賽矩陣為奇異，則無法求逆矩陣，不能構(gòu)造牛頓法方向；

（4）

不僅要計(jì)算梯度，還要求海賽矩陣及其逆矩陣，計(jì)算量和存儲量大。此外，對于二階不可微的F(X)也不適用。雖然阻尼牛頓法有上述缺點(diǎn)，但在特定條件下它具有收斂最快的優(yōu)點(diǎn)，并為其他的算法提供了思路和理論依據(jù)。梯度法與牛頓法：一般迭代式：梯度法：牛頓法：阻尼牛頓法：4-3

共軛方向及共軛方向法為了克服最速下降法的鋸齒現(xiàn)象以提高其收斂速度，發(fā)展了一類共軛方向法。一、共軛方向的基本概念首先以二元二次函數(shù)為例予以說明共軛方向概念，設(shè)函數(shù)2*2階對稱正定矩陣式中二元二次函數(shù)的等值線為一組橢圓，任選初始點(diǎn)x0沿某個下降方向d0作一維搜索，得x1=x0+0d0。0是沿d0方向搜索的最佳步長，即在x1點(diǎn)處函數(shù)f(x)沿d0方向的方向?qū)?shù)為零。故有d0與某一等值線相切于x1點(diǎn)。為了避免按最速下降法出現(xiàn)的鋸齒現(xiàn)象，可取下一次的迭代搜索方向d1直指極小點(diǎn)x*，如圖所示。既有x*=x1+1d11為d1方向上的最佳步長。二次函數(shù)f(x)在x1點(diǎn)的梯度為f(x1)=Gx1+b當(dāng)x1x*時10，由于x*是函數(shù)f(x)的極小點(diǎn)，應(yīng)有f(x*)=Gx*+b=0f(x*)=G(x1+1d1)+b=f(x1)+1Gd1=0等式兩邊同時左乘(d0)T,整理，得(d0)TGd1=0這就是為使d1直指極小點(diǎn)x*,d1所必須滿足的條件。滿足上式得兩個向量d0,d1稱為G的共軛向量，或者說d0,d1對G是共軛的。d1方向應(yīng)該滿足什么條件？二、共軛方向的性質(zhì)定義設(shè)G是nn階對稱正定矩陣，若維空間中有m個非零向量d0，d1，dm-1滿足(di)TGdj=0(i,j=0,1,2,,m-1)(ij)則稱d0，d1，dm-1對G共軛，或稱它們是G的共軛方向。

當(dāng)G=I(單位矩陣）時，上式變成(di)Tdj

=0(ij)即向量d0，d1，dm-1互相正交。由此知，共軛概念是正交概念的推廣，正交是共軛的特例。性質(zhì)1

若非零向量d0，d1，dm-1對G共軛，則這m個向量線性無關(guān)。性質(zhì)2

在n維空間中相互共軛的非零向量的個數(shù)不超過n。性質(zhì)3

從任意初始點(diǎn)x0出發(fā)，順此沿n個G的共軛方向d0，d1，dm-1進(jìn)行一維搜索，最多經(jīng)過n次迭代就可以找到二次函數(shù)的極小點(diǎn)。此性質(zhì)表明本迭代方法具有二次收斂性。一個算法能經(jīng)有限步的搜尋后求出二次目標(biāo)函數(shù)的極小點(diǎn)三、共軛方向法建立在性質(zhì)3的基礎(chǔ)上，提供了求二次函數(shù)極小點(diǎn)的原則方法。步驟是：1）選定初始點(diǎn)x0,下降方向d0和收斂精度，置k0。共軛方向法的程序框圖2）沿dk

方向進(jìn)行一維搜索，得xk+1=xk

+kd

k.3)判斷||f(xk+1)||<是否滿足，滿足則打印xk+1，停機(jī)，否則轉(zhuǎn)4。4）提供新的共軛方向dk+1,使(dj)TGdk+1=0,j=0,1,2,,k.5)置kk+1,轉(zhuǎn)2。格拉姆-斯密特向量系共軛化方法設(shè)已選定線性無關(guān)向量系（例如，它們是n個坐標(biāo)軸上的單位向量），首先取令其中是待定系數(shù)，它根據(jù)與共軛條件來確定，即與共軛的設(shè)已求得共軛向量，現(xiàn)求。令為使與共軛，應(yīng)有由此解得于是

例4-3求的一組共軛向量d0,d1,d2。解：選三個坐標(biāo)軸上的單位向量e0、e1、e2作為一組線性無關(guān)向量系取設(shè)得設(shè)得計(jì)算表明說明d0,d1,d2對G共軛。

上述算法是針對二次函數(shù)的，對于非二次函數(shù)，在極小點(diǎn)可以用二次函數(shù)來近似上式中的海賽矩陣相當(dāng)于二次函數(shù)中的矩陣G，但x*未知。當(dāng)?shù)c(diǎn)x0充分靠近x*時，可用G(x0)構(gòu)造共軛向量系。更有效的共軛方法是構(gòu)造共軛向量系時避開海塞矩陣，下一節(jié)將討論構(gòu)造共軛向量系時如何避開海賽矩陣。

共軛方向法是建立在共軛方向性質(zhì)3的基礎(chǔ)上的。它提供了求二次函數(shù)極小點(diǎn)的原則方法。在無約束方法中許多算法都是以共軛方向作為搜索方向，根據(jù)構(gòu)造共軛方向的原理不同，可以形成不同的共軛方向法，如共軛梯度法，鮑威爾法等。4-4

共軛梯度法

共軛梯度法是介于最速下降法與牛頓法之間的一個方法。它僅需利用一階導(dǎo)數(shù)信息，克服了最速下降法收斂慢的缺點(diǎn)，又避免了存儲和計(jì)算牛頓法所需要的二階導(dǎo)數(shù)信息。本節(jié)介紹的共軛梯度法是一種著名的共軛方向法，它的基本思想是把共軛性與最速下降法相結(jié)合，利用已知點(diǎn)的梯度構(gòu)造一組共軛方向，并沿此組方向進(jìn)行搜索，求出目標(biāo)函數(shù)的極小點(diǎn)。該方法中每一個共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來，根據(jù)共軛方向的基本性質(zhì)，這種方法具有二次收斂性。考慮二次函數(shù)從點(diǎn)出發(fā)，沿G的某一共軛方向做一維搜索，到達(dá)點(diǎn)，即或海塞矩陣而在點(diǎn)處的梯度分別為若與對G是共軛的，則據(jù)共軛條件有所以有（4-1）對式4-1兩端左乘，即得式中不再包含海塞矩陣此式表明沿方向進(jìn)行一維搜索，其終點(diǎn)與始點(diǎn)的梯度之差與的共軛方向正交。共軛梯度法的計(jì)算過程1、設(shè)初始點(diǎn)為，第一個搜索方向取，得并算出點(diǎn)處的梯度。和組成平面正交系2、在和組成的平面正交系中求的共軛方向。令——待定常數(shù)，根據(jù)共軛方向與梯度關(guān)系求得。由X0點(diǎn)負(fù)梯度方向線性無關(guān)有求得構(gòu)成一個正交系。沿方向進(jìn)行一維搜索與共軛為最佳步長即X1點(diǎn)梯度方向3、在所構(gòu)成的正交系中，求與及均共軛的方向。因?yàn)榕c均共軛，有考慮到g0,g1,g2相互正交，有設(shè)1=1，得因此從而得出沿著這些共軛方向一直搜索下去，直到最后迭代點(diǎn)處梯度的模小于給定允許值為止。若目標(biāo)函數(shù)為非二次函數(shù)，經(jīng)n次搜索還未達(dá)到最優(yōu)點(diǎn)時，則以最后得到的點(diǎn)為初始點(diǎn)，重新計(jì)算共軛方向，一直到滿足收斂精度要求為止。再沿點(diǎn)d2方向繼續(xù)進(jìn)行一維搜索，可得遞推公式為共軛梯度法的迭代步驟共軛梯度法的程序框圖例題4-3求下列問題的極值，已知初始點(diǎn)[1,1]T解：1）第一次沿負(fù)梯度方向搜尋計(jì)算初始點(diǎn)處的梯度為一維搜索最佳步長，應(yīng)滿足得:2）第二次迭代：代入目標(biāo)函數(shù)由得從而有：即x2點(diǎn)滿足極值必要條件，再根據(jù)x2點(diǎn)的海賽矩陣正定，可知x2滿足極值充分必要條件。故x2是極小點(diǎn)，即函數(shù)的極小值為f(x*)=8

共軛梯度法的計(jì)算過程可以看出，第一個搜索方向是負(fù)梯度方向，這就是最速下降法。其余各步的搜索方向是將負(fù)梯度偏轉(zhuǎn)一個角度，也就是對負(fù)梯度進(jìn)行修正，稱為旋轉(zhuǎn)梯度法。共軛梯度法屬于解析法，其算法需求一階導(dǎo)數(shù)，所用公式及算法簡單，所需存儲量少。該方法以正定二次函數(shù)的共軛方向理論為基礎(chǔ)，對二次型函數(shù)可以經(jīng)過有限步達(dá)到極小點(diǎn)，所以具有二次收斂性。但是對于非二次型函數(shù)，以及在實(shí)際計(jì)算中由于計(jì)算機(jī)舍入誤差的影響，雖然經(jīng)過n次迭代，仍不能達(dá)到極小點(diǎn)，則通常以重置負(fù)梯度方向開始，搜索直至達(dá)到預(yù)定精度，其收斂速度也是較快的。4-5變尺度法變尺度法也稱擬牛頓法，它是基于牛頓法的思想而又作了重大改進(jìn)的一類方法。我們所介紹的變尺度法是由Davidon于1959年提出又經(jīng)Fletcher和Powell加以發(fā)展和完善的一種變尺度法，故稱為DFP變尺度法。一、變尺度法的基本思想

變尺度法的基本思想與牛頓法和梯度法有密切聯(lián)系。觀察梯度法和牛頓法的迭代公式

x(k+1)

=x(k)

-(k)

g(k)

和 x(k+1)

=x(k)

-(k)

Gk-1

g(k)

分析比較這兩種方法可知：梯度法的搜索方向?yàn)?g(k)，只需計(jì)算函數(shù)的一階偏導(dǎo)數(shù)，計(jì)算量小，當(dāng)?shù)c(diǎn)遠(yuǎn)離最優(yōu)點(diǎn)時，函數(shù)值下降很快，但當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時收斂速度極慢。

牛頓法的搜索方向?yàn)?Gk-1g(k)

，不僅需要計(jì)算一階偏導(dǎo)數(shù)，而且要計(jì)算二階偏導(dǎo)數(shù)及其逆陣，計(jì)算量很大，但牛頓法具有二次收斂性，當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時，收斂速度很快。若迭代過程先用梯度法，后用牛頓法并避開牛頓法的海賽矩陣的逆矩陣的煩瑣計(jì)算，則可以得到一種較好的優(yōu)化方法，這就是“變尺度法”產(chǎn)生的基本構(gòu)想。

為此，綜合梯度法和牛頓法的優(yōu)點(diǎn)，提出變尺度法的基本思想。變尺度法的基本迭代公式寫為下面的形式：

xk+1=xk-kH(k)

g(k)式中的H(k)為構(gòu)造的nn階對稱矩陣，它是隨迭代點(diǎn)的位置的變化而變化的。變尺度法的搜索方向-H(k)

g(k)

，稱為擬牛頓方向。若H(k)=I，上式為梯度法的迭代公式，若H(k)=[G(xk)]-1

，上式為阻尼牛頓法的迭代公式。當(dāng)矩陣Ak不斷地迭代而能很好地逼近H(k)=[G(xk)]-1

時，就可以不再需要計(jì)算二階導(dǎo)數(shù)。變尺度法的關(guān)鍵在于尺度矩陣Hk的產(chǎn)生。二、尺度矩陣的概念變量的尺度變換是放大或縮小各個坐標(biāo)。通過尺度變換可以把函數(shù)的偏心程度降到最低限度。尺度變換能顯著地改進(jìn)幾乎所有極小化方法的收斂性質(zhì)。例如在用最速下降法求的極小值時需要進(jìn)行10次迭代才能達(dá)到極小點(diǎn)如作變換

y1=x1,y2=5x2把的尺度放大5倍，則目標(biāo)函數(shù)等值線由一簇橢圓變成一簇同心圓。x2消除了函數(shù)的偏心，用最速下降法只需一次迭代即可求得極小點(diǎn)。對于一般二次函數(shù)為減低函數(shù)二次項(xiàng)的偏心程度，進(jìn)行尺度變換

xQx則在新的坐標(biāo)系中，函數(shù)的二次項(xiàng)變?yōu)槿艟仃囀钦ǖ模瑒t總存在矩陣Q使QTGQ=I將函數(shù)的偏心變?yōu)榱?。用Q-1右乘等式兩邊，得QTG=Q-1再用Q左乘等式兩邊，得QQTG=I所以QQT=G-1這說明二次函數(shù)矩陣G的逆陣，可以通過尺度變換矩陣Q求得。

QQT實(shí)際上是在空間內(nèi)測量距離大小的一種度量，稱為尺度矩陣，記作H，即

H=

QQT根據(jù)變尺度法的基本原理，需要構(gòu)造一個變尺度矩陣序列{Hk}來逼近海賽逆矩陣序列{Gk-1}，每迭代一次，尺度改變一次。從初始矩陣A0=I(單位矩陣)開始，通過對公式中修正矩陣ΔHk的不斷修正，在迭代中逐步逼近于Gk-1.因此，一旦達(dá)到最優(yōu)點(diǎn)附近，就可望達(dá)到牛頓法的收斂速度。變尺度法的迭代公式：牛頓法法的迭代公式：搜索方向三、變尺度矩陣的建立根據(jù)變尺度法的基本思想，需要構(gòu)造一個矩陣Hk，使其得到的搜索方向必須具有下降性、收斂性和計(jì)算簡便性。1、下降性即只要構(gòu)造的矩陣H（k）為對稱正定矩陣，就是下降方向。對于求目標(biāo)函數(shù)的極小化問題，當(dāng)沿某個可行方向向量s作出微小移動時，其目標(biāo)函數(shù)的變化為對于充分小的，若成立，則s為目標(biāo)函數(shù)下降可行方向。即2、為了使構(gòu)造的矩陣H(k)逐漸逼近，所以還要滿足擬牛頓條件。取其梯度，令設(shè)，若為極值點(diǎn)附近的第k+1次的迭代，則即即若用一矩陣Hk+1來逼近，就必須滿足令則為擬牛頓條件3、為適應(yīng)迭代需要，希望變尺度矩陣有如下遞推形式，即——稱為第k次的校正矩陣（1）選定初始點(diǎn)和收斂精度（4）沿方向進(jìn)行一維搜索，計(jì)算（5）收斂判斷，停機(jī)，否則6若滿足則（6）若令轉(zhuǎn)2，若轉(zhuǎn)7.四、變尺度法的一般步驟及程序框圖（7）計(jì)算矩陣，置，返回到3。（2）計(jì)算，選取初始對稱正定矩陣置（3）計(jì)算搜索方向變尺度法程序框圖五、DFP算法

在變尺度法中，校正矩陣Ek取不同的形式，就形成不同的變尺度法。用遞推方法構(gòu)造擬牛頓條件(1)再令(2)可保證AK的對稱性待定常數(shù)代入(1):兩邊對比得:回代到(2)得:(3)例4-3：

用DFP算法求下列問題的極值：解：1）取初始點(diǎn)，為了按DFP法構(gòu)造第一次搜尋方向d0，需計(jì)算初始點(diǎn)處的梯度取初始變尺度矩陣為單位矩陣H0=I，則第一次搜尋方向?yàn)?/p>

沿d0方向進(jìn)行一維搜索，得為一維搜索最佳步長，應(yīng)滿足得:,2）再按DFP法構(gòu)造點(diǎn)x1處的搜尋方向d1，需計(jì)算代入校正公式==第二次搜尋方向?yàn)樵傺豥1進(jìn)行一維搜索，得為一維搜索最佳步長，應(yīng)滿足,得3）判斷x2是否為極值點(diǎn)梯度:

海賽矩陣:梯度為零向量,海賽矩陣正定?？梢婞c(diǎn)滿足極值充要條件，因此為極小點(diǎn)。

算法評價：

DEF變尺度法以逐次逼近的方法實(shí)現(xiàn)G-1

的計(jì)算，當(dāng)目標(biāo)函數(shù)的一階導(dǎo)數(shù)易求時，以一階代替二階導(dǎo)數(shù)的計(jì)算是有效的方法。算法的第一步是梯度法，最速下降；接近x*

時，又采用二次收斂的共軛方向，總的收斂速度較快。

H(k)

近似代表x(k)點(diǎn)的二階導(dǎo)數(shù)，當(dāng)其為零時，可判斷x(k)為鞍點(diǎn)。

H(k)

的計(jì)算較復(fù)雜，存儲量較大。算法穩(wěn)定性較差，由于計(jì)算機(jī)有舍入誤差，容易使H(k)

的正定性破壞，趨于奇異。

六、BFGS算法式中4-6坐標(biāo)輪換法坐標(biāo)輪換法屬于直接法，既可以用于無約束優(yōu)化問題的求解，又可以經(jīng)過適當(dāng)處理用于約束優(yōu)化問題求解。坐標(biāo)輪換法是每次搜索只允許一個變量變化，其余變量保持不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量（其余變量視為常量）的優(yōu)化問題，因此又稱這種方法為變量輪換法。此種方法只需目標(biāo)函數(shù)的數(shù)值信息而不需要目標(biāo)函數(shù)的導(dǎo)數(shù)?；舅枷耄菏菍⒁粋€n維優(yōu)化問題轉(zhuǎn)化為依次沿n個坐標(biāo)方向反復(fù)進(jìn)行一維搜索問題。這種方法的實(shí)質(zhì)是把n維問題的求優(yōu)過程轉(zhuǎn)化為對每個變量逐次進(jìn)行一維求優(yōu)的循環(huán)過程。每次一維搜索時，只允許n個變量的一次改動，其余(n-1)個變量固定不變。故坐標(biāo)輪換法也常稱單變量法或變量交錯法。坐標(biāo)輪換法的迭代過程以二元函數(shù)為例，如右圖所示。從初始點(diǎn)x00出發(fā)，沿第一個坐標(biāo)方向搜索，即d10=e1得x10=x00+10d10按照一維搜索方法確定最佳步長因子10滿足：；然后從x10出發(fā)沿d20=e2方向搜索得x20=x10+20d20，

其中步長因子20滿足：x20為一輪(k=0)的終點(diǎn)。檢驗(yàn)始、終點(diǎn)間距離是否滿足精度要求，即判斷||x20

x00||<的條件是否滿足。若滿足則x*x20，否則令x01x20,重新依次沿坐標(biāo)方向進(jìn)行下一輪(k=1)的搜索。根據(jù)上述原理，對于第k輪計(jì)算，其迭代公式為其中搜索方向是輪流取n維空間個坐標(biāo)軸的單位向量此法的收斂效果與目標(biāo)函數(shù)等值線的形狀有很大關(guān)系二次就收斂到極值點(diǎn)多次迭代后逼近極值點(diǎn)目標(biāo)函數(shù)等值線出現(xiàn)山脊（或稱陡谷），若搜索到A點(diǎn)，再沿兩個坐標(biāo)軸，以±t0步長測試，目標(biāo)函數(shù)值均上升，計(jì)算機(jī)判斷A點(diǎn)為最優(yōu)點(diǎn)。事實(shí)上發(fā)生錯誤。方法特點(diǎn)

（1）計(jì)算量少，程序簡單，不需要求函數(shù)導(dǎo)數(shù)的直接探索目標(biāo)函數(shù)最優(yōu)解的方法；（2）探索路線較長，問題的維數(shù)愈多求解的效率愈低。當(dāng)維數(shù)n＞10時，則不應(yīng)采用此法。僅適用于n較少（n<10）的目標(biāo)函數(shù)求優(yōu)；（3）受目標(biāo)函數(shù)性態(tài)影響很大。改變初始點(diǎn)重新迭代，可避免出現(xiàn)病態(tài)。4-7鮑威爾方法鮑威爾法是以共軛方向?yàn)榛A(chǔ)的收斂較快的直接法之一，是一種十分有效的算法。1964年，鮑維爾提出這種算法，其基本思想是直接利用迭代點(diǎn)的目標(biāo)函數(shù)值來構(gòu)造共軛方向，然后從任一初始點(diǎn)開始，逐次沿共軛方向作一維搜索求極小點(diǎn)。因此本質(zhì)上是一種共軛方向法。這種方法不用對目標(biāo)函數(shù)求導(dǎo)計(jì)算。當(dāng)目標(biāo)函數(shù)不易求導(dǎo)或?qū)?shù)不連續(xù)時，可以采用這種方法。共軛方向的定義共軛方向的性質(zhì)：鮑威爾方法是在研究具有正定矩陣G的二次函數(shù)的極小化問題時形成的。對函數(shù)：基本思想：在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造G的共軛方向。

1.共軛方向的生成設(shè)xk,xk+1為從不同點(diǎn)出發(fā)，沿同一方向dj進(jìn)行一維搜索而到的兩個極小點(diǎn)。

根據(jù)梯度和等值面相垂直的性質(zhì),

dj和

xk,xk+1兩點(diǎn)處的梯度gk,gk+1之間存在關(guān)系:另一方面，對于上述二次函數(shù)，其xk,xk+1兩點(diǎn)處的梯度可表示為:取兩式相減，得因而有則dk和dj對G共軛。這說明只要沿dj方向分別對函數(shù)作兩次一維搜索，得到兩個極小點(diǎn)xk和xk+1，那么這兩點(diǎn)的連線所給出的方向dk就是與dj一起對G共軛的方向。對于二維問題，的等值線為一族橢圓，A,B為沿軸方向上的兩個極小點(diǎn)，分別處于等值線的切點(diǎn)上。則AB就是與軸一起對G共軛的方向。沿此共軛方向進(jìn)行一維搜索就可找到函數(shù)的極小點(diǎn)x*。2.鮑威爾的基本算法針對二維情況描述鮑威爾的基本算法:

x1x2x0oe1e2d1d2x*11）任選一初始點(diǎn)x0，再選兩個線性無關(guān)的向量，如坐標(biāo)軸單位向量e1=[1,0]T和e2=[0,1]T作為初始搜索方向。2）從x0出發(fā)，順次沿e1，e2作一維搜索，得點(diǎn)，兩點(diǎn)連線得一新方向d1用d1代替e1形成兩個線性無關(guān)向量e2,d1，作為下一輪迭代的搜索方向。再從出發(fā)，沿d1作一維搜索得點(diǎn)，作為下一輪迭代的初始點(diǎn)。3）從出發(fā)，順次沿e2,d1

作一維搜索，得到點(diǎn)，兩點(diǎn)連線得一新方向:從x21出發(fā)，沿d2作一維搜索得點(diǎn)x2即是二維問題的極小點(diǎn)x*。方法的基本迭代格式包括共軛方向產(chǎn)生和方向替換兩主要步驟。

把二維情況的基本算法擴(kuò)展到n維，則鮑威爾基本算法的要點(diǎn)是：在每一輪迭代中總有一個始點(diǎn)（第一輪的始點(diǎn)是任選的初始點(diǎn)）和n個線性獨(dú)立的搜索方向。從始點(diǎn)出發(fā)順次沿n個方向作一維搜索得一終點(diǎn)，由始點(diǎn)和終點(diǎn)決定了一個新的搜索方向。用這個方向替換原來n個方向中的一個，于是形成新的搜索方向組。替換的原則是去掉原方向組的第一個方向而將新方向排在原方向的最后。此外規(guī)定，從這一輪的搜索終點(diǎn)出發(fā)沿新的搜索方向作一維搜索而得到的極小點(diǎn)，作為下一輪迭代的始點(diǎn)。這樣就形成算法的循環(huán)。

鮑威爾基本算法的缺陷

可能在某一環(huán)迭代中出現(xiàn)基本方向組為線性相關(guān)的矢量系的情況。如第k環(huán)中，產(chǎn)生新的方向：

Sk=xnk-x0k=1kS1k+2kS2k+???+nkSnk

式中，S1k、S2k、

???、Snk為第k環(huán)基本方向組矢量，1k

、2k、???、nk為對應(yīng)方向的最優(yōu)步長。

若在第k環(huán)的優(yōu)化搜索過程中出現(xiàn)1k=0，則方向Sk表示為S2k、

S3k、???、Snk的線性組合，以后的各次搜索將在降維的空間進(jìn)行，無法得到n維空間的函數(shù)極小值，計(jì)算將失敗。

如圖所示為一個三維優(yōu)化問題的示例，設(shè)第一環(huán)中1=0，則新生方向與e2、e3共面，隨后的各環(huán)方向組中，各矢量必在該平面內(nèi)，使搜索局限于二維空間，不能得到最優(yōu)解。鮑威爾基本算法的退化x1x2x31=01e23e3S1

因?yàn)樵诘械膎個搜索方向有時會變成線性相關(guān)而不能形成共軛方向。這時組不成n維空間，可能求不到極小點(diǎn)，所以上述基本算法有待改進(jìn)。

3.改進(jìn)的算法

在鮑威爾基本算法中，每一輪迭代都用連結(jié)始點(diǎn)和終點(diǎn)所產(chǎn)生出的搜索方向去替換原向量組中的第一個向量，而不管它的“好壞”，這是產(chǎn)生向量組線性相關(guān)的原因所在。

在改進(jìn)的算法中首先判斷原向量組是否需要替換。如果需要替換，還要進(jìn)一步判斷原向量組中哪個向量最壞，然后再用新產(chǎn)生的向量替換這個最壞的向量，以保證逐次生成共軛方向。為此，要解決兩個關(guān)鍵問題：（1）dk＋1是否較好？是否應(yīng)該進(jìn)入新的方向組？即方向組是否進(jìn)行更新？（2）如果應(yīng)該更新方向組，dk＋1不一定替換方向，而是有選擇地替換某一方向。改進(jìn)算法步驟：（1）給點(diǎn)初始點(diǎn)x0（記做），選取初始方向組它由n個線性無關(guān)的向量所組成，置k0。令在k次循環(huán)中分別稱為一輪迭代的始點(diǎn)、終點(diǎn)和反射點(diǎn)。（2）從出發(fā)，順次沿做一維搜索得。接著以為起點(diǎn)，沿方向移動一個的距離，得同時計(jì)算各中間點(diǎn)處的函數(shù)值記：因此則在第k次循環(huán)中函數(shù)下降最多的第m次迭代是相應(yīng)的方向?yàn)?。為了?gòu)成共軛性好的方向組，須遵循下列準(zhǔn)則：在k次循環(huán)中，若不滿足條件：和則下輪迭代仍用原方向組，并以中函數(shù)值小者作為下一輪迭代的始點(diǎn)。

這樣重復(fù)迭代的結(jié)果，后面加進(jìn)去的向量都彼此對G共軛，經(jīng)n輪迭代即可得到一個由n個共軛方向所組成的方向組。對于二次函數(shù)，最多n次就可找到極小點(diǎn)，而對一般函數(shù)，往往要超過n次才能找到極小點(diǎn)（這里“n”表示設(shè)計(jì)空間的維數(shù)）。

若滿足條件，則去掉方向，將補(bǔ)充到原方向組中的最后位置。即新方向組為作為下輪迭代的搜索方向。下輪迭代的始點(diǎn)取為沿方向進(jìn)行一維搜索的極小點(diǎn)。例4-5用改進(jìn)的鮑威爾法求目標(biāo)函數(shù)。的最優(yōu)解。已知初始點(diǎn)[1,1]T，迭代精度解：（1）第1輪迭代計(jì)算沿e1方向進(jìn)行一維搜索得以為起點(diǎn)，沿第二坐標(biāo)軸方向e2進(jìn)行一維搜索得確定此輪中的最大下降量及其相應(yīng)方向反射點(diǎn)及其函數(shù)值檢驗(yàn)Powell條件由于滿足Powell條件，則淘汰函數(shù)值下降量最大的方向e1，下一輪的基本方向組為e2，。構(gòu)成新的方向

沿方向一維搜索得極小點(diǎn)和極小值此點(diǎn)為下輪迭代初始點(diǎn)。

按點(diǎn)距準(zhǔn)則檢驗(yàn)終止條件

需進(jìn)行第二輪迭代機(jī)算。（2）第2輪迭代計(jì)算此輪基本方向組為e2，，分別相當(dāng)于，，起始點(diǎn)為＝。沿e2方向進(jìn)行一維搜索得

以為起點(diǎn)沿方向一維搜索得確定此輪中函數(shù)值最大下降量及其相應(yīng)方向反射點(diǎn)及其函數(shù)值檢驗(yàn)Powell條件，淘汰函數(shù)值下降量最大的方向e2，下一輪的基本方向組應(yīng)為，。

構(gòu)成新的方向沿方向進(jìn)行一維搜索得檢驗(yàn)終止條件

（3）第3輪迭代計(jì)算此輪基本方向組為，，起始點(diǎn)為＝，先后沿，方向，進(jìn)行一維搜索，得，檢驗(yàn)終止條件故最優(yōu)解實(shí)際上，前兩輪迭代的，為共軛方向，由于本例目標(biāo)函數(shù)是二次函數(shù)，按共軛方向的二次收斂性，故前兩輪的結(jié)果就是問題的最優(yōu)解，但每一輪迭代都需要進(jìn)行n+1次迭代。如果做第三次迭代，則一定各一維搜索的步長為零。4-8單形替換法一、基本思想

單純形替換法也是一種不使用導(dǎo)數(shù)的求解無約束極小化問題的直接搜索方法，與前面幾種方法不同的是，單純形替換法不是利用搜索方向從一個點(diǎn)迭代到另一個更優(yōu)的點(diǎn)，而是從一個單純形迭代到另一個更優(yōu)的單純形。單純形法迭代的基本要點(diǎn)是保證單純形不斷向最優(yōu)點(diǎn)移動并使單純形縮小直至趨于一點(diǎn)。定義：單純形n維空間中的恰好有n+1個頂點(diǎn)的有界的凸多面體稱之為一個單純形。根據(jù)定義，可知，一維空間中的單純形是線段，二維空間中的單純形是三角形，而三維空間中的單純形則是四面體。在單純形替換算法中，從一個單純形到另一個單純形的迭代主