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

4-1

最速下降法4-2牛頓類方法4-3坐標(biāo)輪換法4-4

共軛方向法4-5

鮑威爾方法

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

（1）通過熟悉它的解法可以為研究約束優(yōu)化問題打下良好的基礎(chǔ)。（2）約束優(yōu)化問題的求解可以通過一系列無約束優(yōu)化方法來達(dá)到。第四章無約束優(yōu)化方法

無約束優(yōu)化問題標(biāo)準(zhǔn)形式：求n維設(shè)計(jì)變量使目標(biāo)函數(shù)無約束優(yōu)化問題極值存在的必要條件：目標(biāo)函數(shù)（1）間接法（2）直接法搜索方向的構(gòu)成問題乃是無約束優(yōu)化方法的關(guān)鍵。無約束優(yōu)化問題標(biāo)準(zhǔn)形式：§4-1

最速下降法

基本思想：函數(shù)的負(fù)梯度方向是函數(shù)值在該點(diǎn)下降最快的方向。利用負(fù)梯度作為搜索方向，故稱最速下降法或梯度法。（梯度法）搜索方向s取該點(diǎn)的負(fù)梯度方向(最速下降方向)，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快?！?-1

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

最速下降法步長(zhǎng)因子求解方法：解析法：根據(jù)極值點(diǎn)必要條件。黃金分割法牛頓法拋物線法§4-1

最速下降法最速下降法的搜索路徑相鄰兩個(gè)搜索方向互相垂直§4-1

最速下降法

根據(jù)一元函數(shù)極值的必要條件及復(fù)合函數(shù)求導(dǎo)公式得在最速下降法中，相鄰兩個(gè)迭代點(diǎn)上的函數(shù)梯度相互垂直。搜索方向就是負(fù)梯度方向，因此相鄰兩個(gè)搜索方向互相垂直。形成“之”字形的鋸齒現(xiàn)象，而且越接近極小點(diǎn)鋸齒越細(xì)。

圖最速下降法的搜索路徑§4-1

最速下降法圖最速下降法的收斂過程§4-1

最速下降法方法特點(diǎn)（1）初始點(diǎn)可任選，每次迭代計(jì)算量小，存儲(chǔ)量少，程序簡(jiǎn)短。即使從一個(gè)不好的初始點(diǎn)出發(fā)，開始的幾步迭代，目標(biāo)函數(shù)值下降很快，然后慢慢逼近局部極小點(diǎn)。（2）任意相鄰兩點(diǎn)的搜索方向正交，它的迭代路徑為繞道逼近極小點(diǎn)。當(dāng)?shù)c(diǎn)接近極小點(diǎn)時(shí)，步長(zhǎng)變得很小，越走越慢?！?-1

最速下降法αα沿負(fù)梯度方向進(jìn)行一維搜索，有例4－1求目標(biāo)函數(shù)的極小點(diǎn)。取初始點(diǎn)解：初始點(diǎn)處梯度：沿負(fù)梯度方向進(jìn)行一維搜索，有為一維搜索最佳步長(zhǎng)，應(yīng)滿足極值必要條件

例4－1求目標(biāo)函數(shù)的極小點(diǎn)。取初始點(diǎn)第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值

因此，迭代終止：

沿負(fù)梯度方向進(jìn)行一維搜索，有為一維搜索最佳步長(zhǎng)，應(yīng)滿足極值必要條件

例4－2求目標(biāo)函數(shù)的極小點(diǎn)。解取初始點(diǎn)則初始點(diǎn)處梯度：如何求？坐標(biāo)輪換算出一維搜索最佳步長(zhǎng)

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

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

坐標(biāo)輪換這個(gè)問題的目標(biāo)函數(shù)的等值線為一簇橢圓,迭代點(diǎn)從走的是一段鋸齒形路線，見圖?！?-1

最速下降法例4－3用梯度法求下面無約束優(yōu)化問題：例4－3用梯度法求下面無約束優(yōu)化問題：例4－3用梯度法求無約束優(yōu)化問題：例4－3用梯度法求下面無約束優(yōu)化問題：例4－3用梯度法求下面無約束優(yōu)化問題：例4－3用梯度法求下面無約束優(yōu)化問題：梯度法的特點(diǎn)（1）理論明確，程序簡(jiǎn)單，對(duì)初始點(diǎn)要求不嚴(yán)格。（2）對(duì)一般函數(shù)而言，梯度法的收斂速度并不快，因?yàn)樽钏傧陆捣较騼H僅是指某點(diǎn)的一個(gè)局部性質(zhì)。（3）梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，遠(yuǎn)快近慢。（4）梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)密切相關(guān)。對(duì)于等值線(面)為同心圓（球）的目標(biāo)函數(shù)，一次搜索即可達(dá)到極小點(diǎn)。(b)(c)(a)優(yōu)化前后圖形對(duì)比梯度法應(yīng)用的一個(gè)實(shí)例：4-2

牛頓類方法

基本思想：在xk鄰域內(nèi)用一個(gè)二次函數(shù)來近似代替原目標(biāo)函數(shù)，并將的極小點(diǎn)作為對(duì)目標(biāo)函數(shù)求優(yōu)的下一個(gè)迭代點(diǎn)。經(jīng)多次迭代，使之逼近目標(biāo)函數(shù)的極小點(diǎn)。牛頓法是求函數(shù)極值的最古老算法之一。4-2

牛頓類方法設(shè)為的極小點(diǎn)

這就是多元函數(shù)求極值的牛頓法迭代公式。

例4－4求目標(biāo)函數(shù)的極小點(diǎn)。解取初始點(diǎn)4-2

牛頓類方法例4－4求目標(biāo)函數(shù)的極小點(diǎn)。解取初始點(diǎn)經(jīng)過一次迭代即求得極小點(diǎn)函數(shù)極小值4-2

牛頓類方法例5、用牛頓法求解函數(shù)的極小值初始起始點(diǎn)[1，1]T。4-2

牛頓類方法對(duì)于正定二次函數(shù)，該方法可以直達(dá)極小點(diǎn)。因此對(duì)于非二次函數(shù)，如果采用上述牛頓迭代公式，有時(shí)會(huì)使函數(shù)值上升。4-2

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

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

（4）

不僅要計(jì)算梯度，還要求海賽矩陣及其逆矩陣，計(jì)算量和存儲(chǔ)量大。此外，對(duì)于二階不可微的F(X)也不適用。特定條件下它具有收斂最快的優(yōu)點(diǎn)阻尼牛頓法方法特點(diǎn)一般迭代式：梯度法：牛頓法：阻尼牛頓法：梯度法與牛頓法牛頓法和變尺度法§3.5牛頓法和變尺度法1.變尺度的基本思想：

發(fā)揚(yáng)梯度法和牛頓法各自的優(yōu)點(diǎn)，避免兩者各自的缺點(diǎn)，將兩者結(jié)合起來，形成變尺度法?！?.5牛頓法和變尺度法§3.5牛頓法和變尺度法構(gòu)造變尺度矩陣的遞推公式：修正矩陣:

變尺度法

DFP變尺度法現(xiàn)代公認(rèn)的較好的算法之一。

DFP法、BFGS算法是基于牛頓法的思想又作了重要改進(jìn)。這種算法僅用到梯度，不必計(jì)算海賽陣及其逆矩陣，但又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂速度。間接法：梯度法；牛頓法；變尺度法§4-3

坐標(biāo)輪換法共同點(diǎn)：求導(dǎo)數(shù)直接法：直接用函數(shù)值搜索方向如何定？由于直接搜索是通過大量試驗(yàn)結(jié)果相比較而得最優(yōu)解，因此計(jì)算時(shí)間比較長(zhǎng)，且隨著設(shè)計(jì)變量的增多，計(jì)算時(shí)間增加得很快?！?-3

坐標(biāo)輪換法實(shí)踐證明，在變量不超過10個(gè)的情況下，直接搜索法由于方法本身直觀明確，易于被人所理解與掌握，雖然計(jì)算時(shí)間格長(zhǎng)，但從使用者的角度來看，卻比解析法更為個(gè)人滿意。將一個(gè)多維的無約束最優(yōu)化問題轉(zhuǎn)化為一系列沿坐標(biāo)軸方向的一維易優(yōu)化間題央求解，因此也稱降維法?！?-3

坐標(biāo)輪換法基本原理

坐標(biāo)輪換法的基本思想：是將一個(gè)n維優(yōu)化問題轉(zhuǎn)化為依次沿n個(gè)坐標(biāo)方向反復(fù)進(jìn)行一維搜索問題。

每次一維搜索時(shí)，只允許n個(gè)變量的一個(gè)改動(dòng)，其余(n-1)個(gè)變量固定不變。

故坐標(biāo)輪換法也常稱單變量法或變量交錯(cuò)法。

§4-3

坐標(biāo)輪換法§4-3

坐標(biāo)輪換法例4－1求目標(biāo)函數(shù)的極小點(diǎn)。取初始點(diǎn)分別用1）最速下降法

2）牛頓類方法

3）坐標(biāo)輪換法求上題的最優(yōu)點(diǎn)1）對(duì)于n個(gè)變量的函數(shù)，若在第k輪沿著第i個(gè)坐標(biāo)方向進(jìn)行搜索，其迭代公式為：2）求最優(yōu)搜索步長(zhǎng)計(jì)算步驟：3）本輪所有方向搜索完畢，判斷迭代終止條件：4）滿足上式：否則，進(jìn)行下一輪迭代。例4－2求目標(biāo)函數(shù)的極小點(diǎn)。取初始點(diǎn)梯度法解：第一輪迭代：求最優(yōu)搜索步長(zhǎng)求最優(yōu)搜索步長(zhǎng)沿著第二個(gè)坐標(biāo)方向搜索：判斷終止條件，不滿足，進(jìn)行第二輪迭代：求最優(yōu)搜索步長(zhǎng)求最優(yōu)搜索步長(zhǎng)沿著第二個(gè)坐標(biāo)方向搜索：梯度法例3:用坐標(biāo)輪換法求下面問題的最優(yōu)解，給定初始點(diǎn)X0=[00]T,精度要求ε=0.1解:第一輪迭代求最優(yōu)步長(zhǎng)，即極小化：以X1(1)為新起點(diǎn)，沿e2方向進(jìn)行一維搜索：仍以最優(yōu)步長(zhǎng)原則確定α2：繼續(xù)進(jìn)行第二輪迭代計(jì)算，等等。從坐標(biāo)輪換法的迭代過程可以看出其搜索路線較長(zhǎng)，計(jì)算效率低。因此，一般認(rèn)為此法僅適宜n＜10的小型優(yōu)化問題的求解。另外，此法的效能在很大程度上取決于目標(biāo)函數(shù)的性質(zhì)。按終止條件檢驗(yàn)：坐標(biāo)輪換法此法的效能在很大程度上取決于目標(biāo)函數(shù)的性質(zhì)。（1）計(jì)算量少，程序簡(jiǎn)單，不需要求函數(shù)導(dǎo)數(shù)的直接探索目標(biāo)函數(shù)最優(yōu)解的方法；（2）探索路線較長(zhǎng)，問題的維數(shù)愈多求解的效率愈低。當(dāng)維數(shù)n＞10時(shí)，則不應(yīng)采用此法。僅適用于n較少（n<10）的目標(biāo)函數(shù)求優(yōu)；

（3）改變初始點(diǎn)重新迭代，可避免出現(xiàn)病態(tài)。方法特點(diǎn)

4-4共軛方向法1.共軛方向：設(shè)G為n×n階實(shí)對(duì)稱正定矩陣，如果有兩個(gè)n維向量d0和d1滿足，則稱向量d0與d1

關(guān)于矩陣G共軛。當(dāng)G為單位矩陣時(shí)，假設(shè)目標(biāo)函數(shù)f(x)在極值點(diǎn)附近的二次近似函數(shù)為對(duì)二維情況任選取初始點(diǎn)x0沿某個(gè)下降方向d0作一維搜索，得x14-4共軛方向法因?yàn)槭茄豥0方向搜索的最佳步長(zhǎng)，即在點(diǎn)x1處函數(shù)f（x）沿方向d0的方向?qū)?shù)為零?？紤]到點(diǎn)x1處方向?qū)?shù)與梯度之間的關(guān)系，故有α0d0x0x1x*11α1d1d14-4共軛方向法如果按最速下降法，選擇負(fù)梯度方向?yàn)樗阉鞣较?，則將發(fā)生鋸齒現(xiàn)象。取下一次的迭代搜索方向d1直指極小點(diǎn)x*。α0d0x0x1x*11α1d1d14-4共軛方向法如果能夠選定這樣的搜索方向，那么對(duì)于二元二次函數(shù)只需順次進(jìn)行d0、d1兩次直線搜索就可以求到極小點(diǎn)x*

，即有那么這樣的d1方向應(yīng)該滿足什么條件呢?對(duì)于前述的二次函數(shù):有4-4共軛方向法當(dāng)時(shí)，x*是f(x)極小點(diǎn)，應(yīng)滿足極值必要條件，故有將等式兩邊同時(shí)左乘得：4-4共軛方向法就是使d1直指極小點(diǎn)x*

，d1所必須滿足的條件。兩個(gè)向量d0和d1稱為G的共軛向量，或稱d0和d1對(duì)G是共軛方向。4-4共軛方向法2.共軛方向的性質(zhì)性質(zhì)1

若非零向量系d0,d1,d2,…,dm-1是對(duì)G共軛，則這m個(gè)向量是線性無關(guān)的。性質(zhì)2

在n維空間中互相共軛的非零向量的個(gè)數(shù)不超過n。

性質(zhì)3

從任意初始點(diǎn)出發(fā)，順次沿n個(gè)G的共軛方向d0,d1,d2,…,進(jìn)行一維搜索，最多經(jīng)過n次迭代就可以找到的二次函數(shù)f(x)極小點(diǎn)。

關(guān)鍵：新的共軛方向確定在無約束方法中許多算法都是以共軛方向作為搜索方向，它們具有許多特點(diǎn)。根據(jù)構(gòu)造共軛方向的原理不同，可以形成不同的共軛方向法。

4-4共軛方向法3.共軛梯度法共軛梯度法是共軛方向法中的一種，該方法中每一個(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來。從xk出發(fā)，沿負(fù)梯度方向作一維搜索:設(shè)與dk共軛的下一個(gè)方向dk+1由dk和點(diǎn)xk+1的負(fù)梯度的線形組合構(gòu)成，即：共軛條件：3.共軛梯度法則：解得：3.共軛梯度法令為函數(shù)的泰勒二次展開式則上兩式相減，并代入3.共軛梯度法將式與式兩邊相乘，并應(yīng)用共軛條件得：3.共軛梯度法因此3.共軛梯度法，已知初始點(diǎn)[1,1]T例題4-4求下列問題的極值解：1）第一次沿負(fù)梯度方向搜尋計(jì)算初始點(diǎn)處的梯度迭代精度。為一維搜索最佳步長(zhǎng)，應(yīng)滿足得:2）第二次迭代：代入目標(biāo)函數(shù)得因收斂。由從而有：課堂練習(xí)：求目標(biāo)函數(shù)的極小點(diǎn)。

取初始點(diǎn)用共軛梯度法解上題。（只計(jì)算搜索兩次）4-5鮑威爾方法鮑威爾法是以共軛方向?yàn)榛A(chǔ)的收斂較快的直接法之一，是一種十分有效的算法。

基本思想是直接利用迭代點(diǎn)的目標(biāo)函數(shù)值來構(gòu)造共軛方向，然后從任一初始點(diǎn)開始，逐次沿共軛方向作一維搜索求極小點(diǎn)。對(duì)函數(shù)：基本思想：在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造G的共軛方向。

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

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

dj和

xk,

xk+1兩點(diǎn)處的梯度gk,gk+1之間存在關(guān)系:4-5鮑威爾方法另一方面，對(duì)于上述二次函數(shù)，其xk,

xk+1兩點(diǎn)處的梯度可表示為:4-5鮑威爾方法因而有取這說明只要沿dj方向分別對(duì)函作兩次一維搜索，得到兩個(gè)極小點(diǎn)xk和xk+1

，那么這兩點(diǎn)的連線所給出的方向dk就是與dj一起對(duì)G共軛的方向。2.基本算法二維情況描述鮑威爾的基本算法:

1）任選一初始點(diǎn)x0，再選兩個(gè)線性無關(guān)的向量，如坐標(biāo)軸單位向量e1=[1,0]T和e2=[0,1]T作為初始搜索方向。x1x2x0oe1e2d1d2x*12.基本算法2）從x0出發(fā)，順次沿e1，e1作一維搜索，得點(diǎn)，兩點(diǎn)連線得一新方向d1x1x2x0oe1e2d1d2x*1x1x2x0oe1e2d1d2x*1用

d1代替e1形成兩個(gè)線性無關(guān)向量d1,e2

，作為下一輪迭代的搜索方向。再?gòu)某霭l(fā)，沿d1作一維搜索得點(diǎn)，作為下一輪迭代的初始點(diǎn)。

3）從出發(fā)，→

e2,→

d1

作一維搜索，得到點(diǎn)，兩點(diǎn)連線得一新方向:2.基本算法x1x2x0oe1e2d1d2x*1沿d2作一維搜索得點(diǎn)x2

。即是二維問題的極小點(diǎn)x*

。方法的基本迭代格式包括共軛方向產(chǎn)生和方向替換兩主要步驟。2.基本算法要點(diǎn)：在每一輪迭代中總有一個(gè)始點(diǎn)和n個(gè)線性獨(dú)立的搜索方向。從始點(diǎn)出發(fā)順次沿n個(gè)方向作一維搜索得一終點(diǎn)，由始點(diǎn)和終點(diǎn)決定了一個(gè)新的搜索方向。用這個(gè)方向替換原來n個(gè)方向中的一個(gè)，于是形成新的搜索方向組。鮑威爾基本算法替換的原則:去掉原方向組的第一個(gè)方向而將新方向排在原方向的最后。規(guī)定:

從這一輪的搜索終點(diǎn)出發(fā)沿新的搜索方向作一維搜索而得到的極小點(diǎn)，作為下一輪迭代的始點(diǎn)。這樣就形成算法的循環(huán)。

鮑威爾基本算法例1、用鮑威爾分析函數(shù)的極小值，起始點(diǎn)[0，0]T。（板書）鮑威爾基本算法

上述基本算法僅具有理論意義

:如果需要替換，還要進(jìn)一步判斷原向量組中哪個(gè)向量最壞，然后再用新產(chǎn)生的向量替換這個(gè)最壞的向量，以保證逐次生成共軛方向。3.改進(jìn)的鮑威爾方法在改進(jìn)的算法中首先判斷原向量組是否需要替換。為此，要解決兩個(gè)關(guān)鍵問題：（1）dk＋1是否較好？是否應(yīng)該進(jìn)入新的方向組？即方向組是否進(jìn)行更新？（2）如果應(yīng)該更新方向組，dk＋1不一定替換方向，而是有選擇地替換某一方向。3.改進(jìn)的鮑威爾方法令在k次循環(huán)中（）分別稱為一輪迭代的始點(diǎn)、終點(diǎn)和反射點(diǎn)。3.改進(jìn)的鮑威爾方法則在循環(huán)中函數(shù)下降最多的第m次迭代是記：相應(yīng)的方向?yàn)?。因?.改進(jìn)的鮑威爾方法為了構(gòu)成共軛性好的方向組，須遵循下列準(zhǔn)則,在k次循環(huán)中，若滿足條件：和則選用新方向dk，并在第k+1迭代中用dk替換對(duì)應(yīng)于的方向。否則，仍然用原方向組進(jìn)行第k+1迭代。3.改進(jìn)的鮑威爾方法例4-5用改進(jìn)的鮑威爾法求目標(biāo)函數(shù)解：（1）第1輪迭代計(jì)算，沿e1方向進(jìn)行一維搜索。的最優(yōu)解。已知初始點(diǎn)[1,1]T，迭代精度例4-5用改進(jìn)的鮑威爾法求目標(biāo)函數(shù)，沿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)沿方向一維搜索得構(gòu)成新的方