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

第四章無約束優(yōu)化方法1第一頁，共五十九頁，2022年，8月28日若存在則稱X*點(diǎn)為無約束最優(yōu)點(diǎn)，F(xiàn)(X)為無約束最優(yōu)值。

直接搜索法：坐標(biāo)輪換法、鮑威爾法方法

間接法：梯度法、牛頓法、變尺度法

直接搜索法：只需進(jìn)行函數(shù)值的計(jì)算與比較來確定迭代方向和步長間接法：利用函數(shù)的一階或二階偏導(dǎo)數(shù)矩陣來確定迭代方向和步長對(duì)于無約束優(yōu)化問題:2第二頁，共五十九頁，2022年，8月28日4.1坐標(biāo)輪換法基本思想：把一個(gè)n維無約束最優(yōu)化問題轉(zhuǎn)化為依次沿n個(gè)坐標(biāo)軸方向的一維最優(yōu)化問題。即迭代方向依次為:第一輪:任取一初始點(diǎn)X(0)

一維搜索求得一維搜索求得第二輪:3第三頁，共五十九頁，2022年，8月28日終止準(zhǔn)則:上式點(diǎn)距準(zhǔn)則中的兩點(diǎn)應(yīng)是一輪迭代的始點(diǎn)與終點(diǎn)利用一維優(yōu)化方法確定沿該方向上具有最小目標(biāo)函數(shù)值的步長，即:min{F(X(k)+αS(k))}=F(X(k)+α(k)S(k))迭代步長α的確定:4第四頁，共五十九頁，2022年，8月28日坐

標(biāo)

輪

換

法

的

流

程

圖

5第五頁，共五十九頁，2022年，8月28日坐標(biāo)輪換法的特點(diǎn):具有程序結(jié)構(gòu)簡單，易于掌握等優(yōu)點(diǎn)。但收斂慢，適用于n<10的低維優(yōu)化問題。另收斂速度與等值線的形狀有關(guān)6第六頁，共五十九頁，2022年，8月28日例題4.1用坐標(biāo)輪換法求目標(biāo)函數(shù)的無約束最優(yōu)解。給定初始點(diǎn)精度要求ε=0.1

解：作第一輪迭代計(jì)算。沿e1方向進(jìn)行一維搜索

按最優(yōu)步長原則確定步長α1，即極小化此問題可用某種一維優(yōu)化方法求出α1。在這里，我們暫且借用微分學(xué)求導(dǎo)解出，令其一階導(dǎo)數(shù)為零，α1=5

以為新起點(diǎn)，沿e2方向一維搜索以最優(yōu)步長原則確定α2，即極小化得α2=4.5，對(duì)于第一輪按終止條件檢驗(yàn)7第七頁，共五十九頁，2022年，8月28日例題4.1對(duì)于第一輪按終止條件檢驗(yàn):繼續(xù)第二輪迭代計(jì)算。以下各輪的計(jì)算結(jié)果列于表4.1。8第八頁，共五十九頁，2022年，8月28日例題4.1計(jì)算五輪后有故近似優(yōu)化解為F*＝F(x*)=7.950259第九頁，共五十九頁，2022年，8月28日例題4.1用解析法驗(yàn)證

解:令正定10第十頁，共五十九頁，2022年，8月28日4.2鮑威爾(Powell)法鮑威爾法是直接搜索法中一個(gè)十分有效的算法。該算法是沿著逐步產(chǎn)生的共軛方向進(jìn)行搜索的，因此本質(zhì)上是一種共軛方向法，鮑威爾法的收斂速率較快。以共軛方向作為搜索方向，不只限于鮑威爾法，也用于其他一些較為有效的方法，可以統(tǒng)稱為共軛方向法。因此，共軛方向的概念在優(yōu)化方法研究中占有重要的地位。共軛方向在最優(yōu)化問題中的應(yīng)用是基于其具有一個(gè)重要性質(zhì)，即：設(shè)S1、S2、…、Sn是關(guān)于A的n個(gè)互相共軛的向量，則對(duì)于求正定二次函數(shù)的極小點(diǎn)，從任意初始點(diǎn)出發(fā)，依次沿Si

（i=1，2，…，n)方向進(jìn)行一維最優(yōu)化搜索，至多n步便可以收斂到極小點(diǎn)．11第十一頁，共五十九頁，2022年，8月28日2.5關(guān)于優(yōu)化方法中搜尋方向的理論基礎(chǔ)

2.5.2共軛方向(見第二章)一、共軛方向的基本概念若有兩個(gè)n維矢量S1、S2，對(duì)n×n階對(duì)稱正定矩陣A能滿足:稱n維空間矢量S1與S2對(duì)A共軛共軛矢量所代表的方向稱為共軛方向。正交:可以看作是共軛的特例例:(1)共軛并正交12第十二頁，共五十九頁，2022年，8月28日例:(2)共軛但不正交設(shè)A為n×n階實(shí)對(duì)稱正定矩陣，有一組非零的n維矢量S1、S2、…、Sq，若滿足

i≠j則稱矢量系Si(i＝1，2，…，q≤n)對(duì)于矩陣A共軛

13第十三頁，共五十九頁，2022年，8月28日以二維函數(shù)為例:

二維正定二次函數(shù)具有兩個(gè)重要特性：1）二維正定二次函數(shù)的等值線是同心的橢圓族，且橢圓中心就是正定二元二次函數(shù)的極小點(diǎn)。2)過同心橢圓族中心x*作任意直線，此直線與諸橢圓交點(diǎn)處的切線相互平行?；蛘哒f：兩條平行的任意方向的切線,其切點(diǎn)的連線必通過橢圓簇的中心?？梢宰C明上訴S1和S2方向是關(guān)于矩陣A的共軛方向。14第十四頁，共五十九頁，2022年，8月28日S1與S2是對(duì)A共軛的一對(duì)矢量證明：設(shè)直線方程為代入F(X),并關(guān)于α求極值即結(jié)論:兩個(gè)平行方向的極小點(diǎn)構(gòu)成的新方向與原方向相互共軛即S1與S2對(duì)A共軛也即對(duì)于二維正定二次函數(shù)只要分別沿兩個(gè)共軛方向?qū)?yōu)即可找到最優(yōu)點(diǎn).15第十五頁，共五十九頁，2022年，8月28日與此類似，可以推出對(duì)于n維正定二次函數(shù)，共軛方向的一個(gè)十分重要的極為有用的性質(zhì)：從任意初始點(diǎn)出發(fā)，依次沿n個(gè)線性無關(guān)的與A共軛的方向S1，S2，…Sn各進(jìn)行一維搜索，那么總能在第n步或n步之前就能達(dá)到n維正定二次函數(shù)的極小點(diǎn)；并且這個(gè)性質(zhì)與所有的n個(gè)方向的次序無關(guān)。簡言之，用共軛方向法對(duì)于二次函數(shù)從理論上來講，n步就可達(dá)到極小點(diǎn)。因而說共軛方向法具有有限步收斂的特性。通常稱具有這種性質(zhì)的算法為二次收斂算法。共軛矢量之所以引起優(yōu)化研究者的重視，就是因?yàn)樗倪@些性質(zhì)對(duì)提高優(yōu)化方法的收斂速率極為有用。

16第十六頁，共五十九頁，2022年，8月28日例設(shè)二維目標(biāo)函數(shù)，給定方向S1＝e2，初始點(diǎn)，求與S1相共軛的S2，并求函數(shù)的極小點(diǎn)。解：(1)第一個(gè)搜索方向(2)函數(shù)的海賽矩陣對(duì)稱正定(3)從點(diǎn)沿S1方向求極小點(diǎn)x(1)，即

17第十七頁，共五十九頁，2022年，8月28日例解：(4)任取另初始點(diǎn)沿S1方向一維搜索求得該方向極小點(diǎn)x(2)

X(2)=

(5)求與S1相共軛的方向S2S2=X(2)-X(1)=

核驗(yàn)計(jì)算

矢量S1與S2確為對(duì)A矩陣共軛。

(6)從x(1)點(diǎn)出發(fā)，沿S2方向作一維搜索，得極小點(diǎn)X*=[00]T

18第十八頁，共五十九頁，2022年，8月28日4.2.1鮑威爾基本算法（共軛方向的原始構(gòu)成）19第十九頁，共五十九頁，2022年，8月28日4.2.1鮑威爾基本算法任取一初始點(diǎn)X(0)→

X0(1)第一環(huán):

e1,e2,e3→

S1第二環(huán):

e2,e3,S1→

S2第三環(huán):

e3,S1,

S2→S3第一輪

S1,

S2

,S3

兩兩共軛由前結(jié)論:兩個(gè)平行方向的極小點(diǎn)構(gòu)成的新方向與原方向相互共軛20第二十頁，共五十九頁，2022年，8月28日4.2.1鮑威爾基本算法第一環(huán):

e1,e2,e3→

S1第二環(huán):

e2,e3,S1→

S2第三環(huán):

e3,S1,

S2→S3第一輪S1是e1,e2,e3的線性組合S2是e2,e3,S1的線性組合S3是e3,S1,

S2的線性組合新一環(huán)方向組:e2,e3,S1線性相關(guān)!降維21第二十一頁，共五十九頁，2022年，8月28日鮑威爾法的基本思想:

對(duì)原始共軛方向法進(jìn)行修正,即在某環(huán)已取得的n+1個(gè)方向中,選取n個(gè)線性無關(guān),共軛程度盡可能高的方向作為下一環(huán)的基本方向組,從而避免出現(xiàn)“退化”現(xiàn)象.鮑威爾法與原始共軛方向法的主要區(qū)別是：在構(gòu)成K+1環(huán)基本方向組時(shí)，不再總是淘汰前一環(huán)(K環(huán))中的第一個(gè)方向，而是根據(jù)條件式是否得到滿足分兩種情況來處理。4.2.1鮑威爾修正算法22第二十二頁，共五十九頁，2022年，8月28日映射點(diǎn)一、Powell

修正算法的搜索方向

Powell

判別式23第二十三頁，共五十九頁，2022年，8月28日情況一：

Powell

判別式中若至少有一個(gè)不等式成立，則第K+1環(huán)的方向組仍用老方向組

初始點(diǎn):當(dāng)F2<F3時(shí),當(dāng)F2≥F3時(shí),情況二：

Powell

判別式中若兩個(gè)不等式均不成立，則第K+1環(huán)的方向組去掉函數(shù)值下降最大的方向,補(bǔ)上新增的方向初始點(diǎn):24第二十四頁，共五十九頁，2022年，8月28日

以二維為例:兩條件式至少有一成立且F2<F3兩條件式至少有一成立且F2>F3

25第二十五頁，共五十九頁，2022年，8月28日兩條件式均不成立且m=1

兩條件式均不成立且m=226第二十六頁，共五十九頁，2022年，8月28日終止準(zhǔn)則:采用了上述產(chǎn)生基本方向組的新方式后，除了第一環(huán)以單位坐標(biāo)矢量系為基本方向組外，以后每輪開始就不必重置單位坐標(biāo)矢量系，只要一環(huán)接一環(huán)繼續(xù)進(jìn)行即可。隨著逐環(huán)迭代的繼續(xù)，各環(huán)的基本方向組將漸趨共軛。因此，這個(gè)修正了的鮑威爾算法，雖然已不再像基本算法那樣具有二次收斂的性質(zhì)，但修正算法確實(shí)克服了退化的不利情形，同時(shí)仍能夠有效地、越來越快地收斂于無約束最優(yōu)點(diǎn)x*。二、修正算法的迭代步驟及流程圖映射點(diǎn)27第二十七頁，共五十九頁，2022年，8月28日28第二十八頁，共五十九頁，2022年，8月28日試用鮑爾修正算法求目標(biāo)函數(shù)

的最優(yōu)解。迭代精度ε=0.001。

已知初始點(diǎn)解：第一環(huán)迭代計(jì)算

沿第一坐標(biāo)方向e1進(jìn)行一維搜索沿第二坐標(biāo)軸方向e2進(jìn)行一維搜索

29第二十九頁，共五十九頁，2022年，8月28日例題沿s1方向一維搜索得極小點(diǎn)與極小值

需進(jìn)行第二環(huán)迭代計(jì)算。第二環(huán)迭代計(jì)算：首先確定上環(huán)中的最大函數(shù)下降量及其相應(yīng)方向

映射點(diǎn)及其函數(shù)值30第三十頁，共五十九頁，2022年，8月28日檢驗(yàn)鮑爾條件鮑威爾條件兩式均不成立。第二環(huán)基本方向組和起始點(diǎn)為沿e2方向作一維搜索得沿S1方向一維搜索得

構(gòu)成新生方向沿S2方向一維搜索得去掉函數(shù)值下降最大的方向,補(bǔ)上新增的方向初始點(diǎn)取新增方向的極小點(diǎn)31第三十一頁，共五十九頁，2022年，8月28日例題4.2檢查迭代終止條件需再作第三環(huán)迭代計(jì)算。根據(jù)具體情況來分析，S1、S2實(shí)際上為共軛方向的（見圖4.9）。本題又是二次函數(shù)，按共軛方向的二次收斂性質(zhì)，上面的結(jié)果就是問題的最優(yōu)解?？梢灶A(yù)料，如果作第三環(huán)迭代，則一定各一維搜索的步長為零，必有故得最優(yōu)解32第三十二頁，共五十九頁，2022年，8月28日解:令正定

用解析法驗(yàn)證

得:33第三十三頁，共五十九頁，2022年，8月28日鮑威爾法的特點(diǎn):

是到目前為止求解無約束優(yōu)化問題的最有效的方法。不需求導(dǎo)數(shù),只需計(jì)算目標(biāo)函數(shù)值。適用中、小型問題。34第三十四頁，共五十九頁，2022年，8月28日梯度法的基本思想:利用函數(shù)在其負(fù)梯度方向函數(shù)值下降最快這一局部性質(zhì)，將n維無約束優(yōu)化問題轉(zhuǎn)化為一系例的沿目標(biāo)函數(shù)負(fù)梯度方向的一維尋優(yōu)問題。4.3梯度法終止準(zhǔn)則:?。核裕?5第三十五頁，共五十九頁，2022年，8月28日例題4.3用梯度法求目標(biāo)函數(shù)F(x)=+25的最優(yōu)解。已知初始點(diǎn)x(0)＝[22]T，迭代精度取ε=0.005。解：函數(shù)的梯度第一次迭代：以x(0)為起點(diǎn)沿-g(0)方向作一維搜索初始點(diǎn)函數(shù)梯度值:第一點(diǎn)函數(shù)梯度值:36第三十六頁，共五十九頁，2022年，8月28日37第三十七頁，共五十九頁，2022年，8月28日解:令正定得:

用解析法驗(yàn)證

38第三十八頁，共五十九頁，2022年，8月28日梯度法的特點(diǎn):

幾何概念直觀,方法和程序簡單,遠(yuǎn)離極小點(diǎn)時(shí)收斂速度快。但越接近極小點(diǎn)收斂速度越慢。39第三十九頁，共五十九頁，2022年，8月28日原始牛頓法基本思想：

在點(diǎn)x(k)

領(lǐng)域內(nèi)用一個(gè)二次函數(shù)Φ（x)去近似代替原目標(biāo)函數(shù)F(x)，然后求出這個(gè)二次函數(shù)的極小點(diǎn)，以該點(diǎn)作為對(duì)原目標(biāo)函數(shù)求優(yōu)的下一個(gè)選代點(diǎn)x(k+1），這樣通過重復(fù)若干次迭代，使迭代點(diǎn)逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)X*

。

4.5牛頓法

40第四十頁，共五十九頁，2022年，8月28日注意：與一維優(yōu)化方法的二次插值法的不同每次迭代所用的二次函數(shù)就是在迭代點(diǎn)展開的泰勒二次多項(xiàng)式

41第四十一頁，共五十九頁，2022年，8月28日4.5.1原始牛頓法一元函數(shù)f(x)在x(k)點(diǎn)的泰勒展開式：n元函數(shù)F(X)在X(k)點(diǎn)的泰勒展開式：42第四十二頁，共五十九頁，2022年，8月28日即:牛頓方向:(定步長)等號(hào)兩邊左乘為求極小點(diǎn),令一階導(dǎo)數(shù)等于零由前：即迭代方向：:43第四十三頁，共五十九頁，2022年，8月28日牛頓法具有二次收斂性。對(duì)于二次正定函數(shù)，迭代一次即可到達(dá)最優(yōu)點(diǎn)；對(duì)于非二次函數(shù)，若函數(shù)的二次性態(tài)較強(qiáng)或迭代點(diǎn)已進(jìn)入最優(yōu)點(diǎn)的較小鄰域，則其收斂速度也是很快的。但原始牛頓法還存在一個(gè)問題：由于在全部迭代過程中，取步長α(k)≡1，這種定步長有時(shí)造成函數(shù)值反而有所增大。44第四十四頁，共五十九頁，2022年，8月28日

阻尼牛頓法基本思想:阻尼牛頓法的迭代方向仍是上述牛頓方向，但每次迭代需沿此方向作一維搜索，求其最優(yōu)步長因子,即迭代公式為：

4.5.2阻尼牛頓法45第四十五頁，共五十九頁，2022年，8月28日46第四十六頁，共五十九頁，2022年，8月28日例題4.5用牛頓法求函數(shù)F(x)＝4(x1＋1)2＋2(x2－1)2＋x1＋x2＋10的最優(yōu)解。初始點(diǎn)x(0)＝[00]T，ε＝10－5。解：函數(shù)的梯度海賽矩陣及其逆在x(0)點(diǎn)處47第四十七頁，共五十九頁，2022年，8月28日沿S(0)方向一維搜索求最優(yōu)步長得代入函數(shù)解得：α(0)=1故新迭代點(diǎn)為該點(diǎn)的梯度滿足終止條件，迭代即可結(jié)束48第四十八頁，共五十九頁，2022年，8月28日補(bǔ)充:求逆矩陣稱作矩陣A的伴隨方陣,中元素

是中元素的代數(shù)余子式

劃去所在行列后余下的n-1階子式例:49第四十九頁，共五十九頁，2022年，8月28日解:令正定

用解析法驗(yàn)證

F(x)＝4(x1＋1)2＋2(x2－1)2＋x1＋x2＋10

得:50第五十頁，共五十九頁，2022年，8月28日牛頓法的特點(diǎn)：牛頓法具有二次收斂性，對(duì)正定二次函數(shù)一次迭代即可達(dá)到極小點(diǎn)。對(duì)目標(biāo)函數(shù)性態(tài)較好或當(dāng)初始點(diǎn)取在極小點(diǎn)附近時(shí)收斂速度快。但對(duì)目標(biāo)函數(shù)有較高的要求，必須存在一階、二階偏導(dǎo)數(shù)，H（x(k)）需正定且非奇異。計(jì)算復(fù)雜，計(jì)算量大。51第五十一頁，共五十九頁，2022年，8月28日梯度法和牛頓法對(duì)比方法梯度法牛頓法迭代公式迭代方向穩(wěn)定下降性肯定能保證穩(wěn)定下降須H(X)處處正定才能穩(wěn)定下降收斂速度離X*遠(yuǎn)時(shí)下降速度較快,離近時(shí)下降很慢離X*近時(shí)收斂很快二次收斂性不具有二次收斂性具有二次收斂性52第五十二頁，共五十九頁，2022年，8月28日觀察梯度法和牛頓法的迭代式：

變尺度法的基本思想：設(shè)法構(gòu)造一個(gè)對(duì)稱正定陣Ak代替,并在選代計(jì)算中，使其逐漸逼近。因此，一旦達(dá)到極值點(diǎn)附近，就可望達(dá)到牛頓法的收斂速度，同時(shí)又避免了矩陣的求逆計(jì)算。其選代公式：Ak是是根據(jù)需要構(gòu)造的n×n階對(duì)稱矩陣，它是隨著迭代點(diǎn)位置的變化而變化的。

梯度法:牛頓法:4.6DFP變尺度法53第五十三頁，共五十九頁，2022年，8月28日

4.6.2變尺度法構(gòu)造矩陣的產(chǎn)生遞推方法產(chǎn)生:校正矩陣

變尺度法采用構(gòu)造矩陣來代替牛頓法中海賽矩陣的逆陣