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

1、第四章第四章 無約束優(yōu)化方法無約束優(yōu)化方法4.14.24.34.44.54.64.74.84.9，數(shù)值解法：數(shù)值解法：是利用是利用已有已有的信息，通過計(jì)算點(diǎn)一步一步地的信息，通過計(jì)算點(diǎn)一步一步地直接移動，直接移動，逐步逼近逐步逼近最后達(dá)到最優(yōu)點(diǎn)。最后達(dá)到最優(yōu)點(diǎn)。 1(0,1,)kkkkxxdk1 1）選擇迭代方向即探索方向；）選擇迭代方向即探索方向；2 2）在確定的方向上選擇適當(dāng)步長邁步進(jìn)行探索）在確定的方向上選擇適當(dāng)步長邁步進(jìn)行探索 ， 一類是利用目標(biāo)函數(shù)的一類是利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)一階或二階導(dǎo)數(shù)的無約束優(yōu)化的無約束優(yōu)化方方法（如最速下降法、共軛梯度法、牛頓法及變尺度法）；法（如最速

2、下降法、共軛梯度法、牛頓法及變尺度法）； 另一類另一類只利用目標(biāo)函數(shù)只利用目標(biāo)函數(shù)的無約束優(yōu)化方法（如坐標(biāo)輪的無約束優(yōu)化方法（如坐標(biāo)輪換換法、單形替換法及鮑威爾法等）。法、單形替換法及鮑威爾法等）。， 最速下降法就是采用使目標(biāo)函數(shù)值下降得最快的最速下降法就是采用使目標(biāo)函數(shù)值下降得最快的負(fù)負(fù)梯度方向梯度方向作為探索方向，來求目標(biāo)函數(shù)的極小值的方法，作為探索方向，來求目標(biāo)函數(shù)的極小值的方法，又稱為又稱為梯度法梯度法。1()(0,1,)kkkkxxf xk最速下最速下降法的降法的迭代公迭代公式式， 011*10();3minmin4|;1,kkkkkkkkkkkkkxkdf xfxa daxxa d

3、xxxxkk 1）給定初始點(diǎn) 和收斂精度 ，置；2）計(jì)算梯度，并構(gòu)造搜索方向）用一維搜索的方法求解得最佳步長 ，代入得到新的迭代點(diǎn)；）若，則停止迭代，得最優(yōu)解否則，轉(zhuǎn)到第二步。2212 ( )25 f xxx例：用最速下降法求目標(biāo)函數(shù)的極小點(diǎn)。，1()(0,1,)kkkkxxf xk， 1 1）對）對初始搜索點(diǎn)初始搜索點(diǎn)無嚴(yán)格要求；無嚴(yán)格要求； 2 2）收斂）收斂速度不快速度不快； 3 3）相鄰兩次相鄰兩次迭代搜索迭代搜索方向方向互相互相垂直垂直，在遠(yuǎn)離極值點(diǎn)處，在遠(yuǎn)離極值點(diǎn)處收斂快，在靠近極值點(diǎn)處收斂慢；收斂快，在靠近極值點(diǎn)處收斂慢； 4 4）收斂速度與）收斂速度與目標(biāo)函數(shù)值的性質(zhì)目標(biāo)函數(shù)值

4、的性質(zhì)有關(guān)，對等值線是有關(guān)，對等值線是同同心圓心圓的目標(biāo)函數(shù)來說，經(jīng)過的目標(biāo)函數(shù)來說，經(jīng)過一次迭代一次迭代就可以達(dá)到極值點(diǎn)。就可以達(dá)到極值點(diǎn)。， 利用利用二次曲線二次曲線來逐點(diǎn)來逐點(diǎn)近似原目標(biāo)函數(shù)近似原目標(biāo)函數(shù)，以，以二次曲線的二次曲線的極極小點(diǎn)小點(diǎn)來來近似原目標(biāo)函數(shù)的極小點(diǎn)近似原目標(biāo)函數(shù)的極小點(diǎn)并逐漸逼近該點(diǎn)。并逐漸逼近該點(diǎn)。 基本牛頓法的迭代公式：基本牛頓法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x ，基本牛頓法的迭代公式：基本牛頓法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x 022121211,1 ,0.1 min( )224Txf

5、 xxxx xx例：用基本牛頓法求解下列無約束優(yōu)化問題，已知。，基本牛頓法的迭代公式：基本牛頓法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x 阻尼牛頓法的迭代公式：阻尼牛頓法的迭代公式：11 (0,1,2,)() kkkkkkkxxdkdG xf x ，01111*1,0;()()()()34|;1,kkkkkkkkkkkkkkkxkf xG xG xdG xf xxxddxxxxkk 1）給定初始點(diǎn)收斂精度 ，置2）計(jì)算、和，得到；）求，其中，是沿著進(jìn)行一維搜索的最佳步長；）檢查收斂精度。若，則停止迭代，得最優(yōu)解否則，轉(zhuǎn)到第二步繼續(xù)進(jìn)行搜索。，022121211,1

6、 ,0.1 min( )224Txf xxxx xx例：用阻尼牛頓法求解下列無約束優(yōu)化問題，已知。阻尼牛頓法的迭代公式：阻尼牛頓法的迭代公式：11 (0,1,2,)() kkkkkkkxxdkdG xf x ，10()0Tf xd 在下一次迭代時(shí)，選擇搜索方在下一次迭代時(shí)，選擇搜索方d d1 1指向極小點(diǎn)指向極小點(diǎn)x x* *， *111xxa d以以二元函數(shù)二元函數(shù)為例：為例： 我們?nèi)我膺x擇一個我們?nèi)我膺x擇一個初始點(diǎn)初始點(diǎn)x x0 0點(diǎn)，點(diǎn)，沿著沿著某個下降方向某個下降方向d d0 0作一維搜索作一維搜索 1000 xxa d 12TTfxx Gxb xc010TdGd ，01m 101m

7、1Gnmddd()0 ( ,0,1,1) ()dddGGi TjdGdi jmij設(shè) 是n n對稱正定矩陣，若 維空間中有 個非零向量 、 、 、滿足 則稱 、 、 、對 共軛，或稱它們是 的共軛方向。01m 1G I()0 ()dddiTjddij當(dāng) = （單位矩陣）時(shí)，有，即向量、 、 、互相正交。， 01m 1001n 1*dddG() m2nn3xnGdddn1x2TTfxx Gxb xc性質(zhì)1：若非零向量系、 、 、是對實(shí)對稱正定矩陣共軛的，則這 個向量是線性無關(guān)的。性質(zhì) ：在 維空間中互相共軛的非零向量個數(shù)不超過 。性質(zhì) ：從任意初始點(diǎn)點(diǎn)出發(fā)，順次沿 個 的共軛方向、 、 、進(jìn)行一

8、維搜索，最多經(jīng)過 次迭代就可以 找到二次函數(shù)的極小點(diǎn) 。，00k111111xdkd340j01 2k5kk+1kkkkkkTkjkxxa df xxddGd）選定初始點(diǎn) ，下降方向和收斂精度 ， 置0；2）沿方向進(jìn)行一維搜索，得；）判斷是否滿足，滿足則打印， 否則，轉(zhuǎn)到第四步；）提供新的共軛方向，使， ， ，；）置，轉(zhuǎn)第二步。，111,0iiriirrdvdn n個線性無關(guān)的向量系個線性無關(guān)的向量系vi vi（i=0,1i=0,1，n-1 n-1 ）一組獨(dú)立向量一組獨(dú)立向量d dr r（r=0,1r=0,1，n-1n-1） 11,()()j Tiijj TjdGvdGd 1110()()jT

9、iijiijTjjdGvdvddGd012210G=121012ddd例：求的一組共軛向量系、 、。，1110()()jTiijiijTjjdGvdvddGd111,0iiriirrdvd11,()()j Tiijj TjdGvdGd ， 先沿先沿最速下降方向最速下降方向( (負(fù)梯度方向負(fù)梯度方向) )探索第一步，然后沿與探索第一步，然后沿與該負(fù)梯度方向相該負(fù)梯度方向相共軛的方向共軛的方向進(jìn)行探索。進(jìn)行探索。，1()0Tjkkdgg 它表示沿著方向它表示沿著方向d dk k做一維搜索，做一維搜索，它的終點(diǎn)它的終點(diǎn)x xk+1k+1與始點(diǎn)與始點(diǎn)x xk k的梯度之差的梯度之差與與d dk k的共

10、軛方向的共軛方向d dj j正交。正交。 ，21112| |(0,1,2,1)kkkkkgdgdgkn ，001(1)*1*10121;(),0;3);4)(),()(),5|kkkkkkkkkkkkkdf xkdxxdf xxxf xf xknxxg 1)給定初始點(diǎn)x 和計(jì)算精度2）取x 的負(fù)梯度方向作為搜索方向：置沿方向作一維搜索得判斷收斂：若滿足則令，結(jié)束迭代；否則，轉(zhuǎn)到第五步；）若，則令，轉(zhuǎn)到第二步開始新的一輪的迭代；否則，轉(zhuǎn)到第六步；6）構(gòu)造新的共軛方向112,|1,kkkkkdgdgkk ，令轉(zhuǎn)到第三步。，221212112( ,)242f x xxxxx x例：用共軛梯度法求二次

11、函數(shù)的極小點(diǎn)及極小值。，21112| |(0,1,2,1)kkkkkgdgdgkn 設(shè)法構(gòu)造出一個設(shè)法構(gòu)造出一個對稱正定矩陣對稱正定矩陣 來代替來代替 ，并，并在迭代過程中使在迭代過程中使 逐漸逼近逐漸逼近 , ,那么就簡化了牛頓那么就簡化了牛頓法的計(jì)算，并且保持了牛頓法收斂快的優(yōu)點(diǎn)。法的計(jì)算，并且保持了牛頓法收斂快的優(yōu)點(diǎn)。kH1()kG x1()kG xkH，1()kkkdG xfx 1 (0,1,2)kkkkkxxHf xk尺度矩陣尺度矩陣， 12TTfxx Gxb xcxQx12TTx Q GQxG G 正定正定TQ GQI牛頓迭代公式：牛頓迭代公式：1kkTkkxxQQf x1TQQG

12、THQQ1kkkkkxxHfx目標(biāo)函數(shù)的偏心率減小到零。，1kkkkkxxHfx變尺度法的迭代公式：變尺度法的迭代公式：搜索方向：搜索方向： =kkkkkdHfxH g 尺度矩陣應(yīng)具備的條件：尺度矩陣應(yīng)具備的條件：1 1）為正定對稱矩陣；）為正定對稱矩陣；2 2）具有簡單的迭代形式）具有簡單的迭代形式: :3 3）滿足擬牛頓條件：）滿足擬牛頓條件：令令 則則111()kkkkkHggxx1kkkHHE1kkkygg1kkksxx1kkkHys，0000011111*11)2)()03)=4)(),5)66)kkkkkkkkkkkkkkkkkkxgf xHHIkdH gdxxdgf xsxxyg

13、gxxnH 選定初始點(diǎn)和收斂精度 ；計(jì)算，選定初始對稱正定矩陣 （如），置；計(jì)算搜索方向；沿方向進(jìn)行一維搜索，計(jì)算， ；判斷是否滿足迭代終止條件，若滿足則，停機(jī)，否則轉(zhuǎn)到 ；若迭代 次后還沒有找到極小點(diǎn)，重置為單位矩陣011277)13kkkkIxxHHEkk，并以當(dāng)前設(shè)計(jì)點(diǎn) 為初始點(diǎn)，返回 進(jìn)行下一輪迭代，否則轉(zhuǎn)到 ；計(jì)算矩陣，置，返回 。，DFPDFP算法的校正公式算法的校正公式1 (0,1,2,)TTkkkkkkkkkkTTkkkkks sH y y HHHEHks yy H y，221212112DFP,242 f x xxxxx x例：用算法求的極值解。1 (0,1,2,)TTkkk

14、kkkkkkkTTkkkkks sH y y HHHEHks yy H y， 每次僅對多元函數(shù)的每次僅對多元函數(shù)的一個變量一個變量沿其沿其坐標(biāo)軸坐標(biāo)軸進(jìn)行進(jìn)行一維探索一維探索，其余各變量均固定不動，并，其余各變量均固定不動，并依次輪換依次輪換進(jìn)行進(jìn)行一一維探索的坐標(biāo)軸維探索的坐標(biāo)軸，完成第一輪探索后再重新進(jìn)行第二輪，完成第一輪探索后再重新進(jìn)行第二輪探索，直到找到目標(biāo)函數(shù)在全域上的最小點(diǎn)為止。探索，直到找到目標(biāo)函數(shù)在全域上的最小點(diǎn)為止。將一個將一個多維多維的無約束最優(yōu)化問題，轉(zhuǎn)化為的無約束最優(yōu)化問題，轉(zhuǎn)化為一系一系列的一維問題列的一維問題來求解。來求解。，二維問題二維問題，1 (0,1,2, 1

15、,2, )kkkkiiiixxdkin00100kTiide11()()kkkkiiiif xdf x包括正負(fù)包括正負(fù)，隨機(jī)選擇方法隨機(jī)選擇方法加速步長法加速步長法最優(yōu)步長法（一維搜索方法，如：黃金分割法、最優(yōu)步長法（一維搜索方法，如：黃金分割法、二次插值法，來確定最優(yōu)步長）二次插值法，來確定最優(yōu)步長）11()()kkkkiiiif xdf x11min()()kkkkkiiiiif xdf xd，1111)2)()()3)()J 1()J4)kkiikkkkkiiiiiikiikiihff xf xdff xff x先以試驗(yàn)步長確定步長的正負(fù)，當(dāng)沿坐標(biāo)軸正方向探索能使目標(biāo)函數(shù)值減小時(shí)，則取正

16、值，否則應(yīng)取負(fù)值；按所取步長計(jì)算目標(biāo)函數(shù)值若，則取加速步長，使其沿同一方向延伸；若延伸至第次時(shí)，則延伸至第 次為止。當(dāng)步長不宜延伸而宜縮小時(shí)，亦可縮小，也是一直到函數(shù)值達(dá)到最小值為止；改kid變方向，在新的方向上重復(fù)前述過程，直到函數(shù)值達(dá)到最小值為止，終止計(jì)算。， 計(jì)算簡單、概念清楚、易于掌握；但搜索路線較長計(jì)算簡單、概念清楚、易于掌握；但搜索路線較長（需要經(jīng)過多次曲折迂回的路徑才能達(dá)到極值點(diǎn)），計(jì)（需要經(jīng)過多次曲折迂回的路徑才能達(dá)到極值點(diǎn)），計(jì)算率較低，特別是當(dāng)維數(shù)很高時(shí)很費(fèi)時(shí)，所以坐標(biāo)輪換算率較低，特別是當(dāng)維數(shù)很高時(shí)很費(fèi)時(shí)，所以坐標(biāo)輪換法只能用于低維（法只能用于低維（n10n10）的優(yōu)化問

17、題求解。此外，坐標(biāo)）的優(yōu)化問題求解。此外，坐標(biāo)輪換法的效率在很大程度上取決于目標(biāo)函數(shù)的性態(tài)，也輪換法的效率在很大程度上取決于目標(biāo)函數(shù)的性態(tài)，也就是等值線的形態(tài)與坐標(biāo)軸的關(guān)系。就是等值線的形態(tài)與坐標(biāo)軸的關(guān)系。 ，直接利用迭代點(diǎn)的直接利用迭代點(diǎn)的目標(biāo)函數(shù)值目標(biāo)函數(shù)值來來構(gòu)造共軛構(gòu)造共軛方向方向，然后再從任一初始點(diǎn)出發(fā)，然后再從任一初始點(diǎn)出發(fā)，逐次的共軛方向逐次的共軛方向作一維搜索求極值點(diǎn)。作一維搜索求極值點(diǎn)。，共軛方向的生成：共軛方向的生成：結(jié)論：結(jié)論：從從不同的不同的兩點(diǎn)兩點(diǎn)出發(fā)，沿出發(fā)，沿同同一方向一方向進(jìn)行兩次進(jìn)行兩次一維搜索，所得一維搜索，所得兩個極小點(diǎn)的連兩個極小點(diǎn)的連線方向線方向便是便

18、是原方原方向共軛向共軛的另一方的另一方向。向。，共軛方向的生成：共軛方向的生成：二維情況：二維情況：任意點(diǎn)出發(fā)沿著任意點(diǎn)出發(fā)沿著x1x1軸軸方方向和向和ABAB方向搜索，即可方向搜索，即可得到極小點(diǎn)。得到極小點(diǎn)。，基本基本POWELLPOWELL法（二維）：法（二維）：012012001001220112012111021121)1 00 12)3)TTxeexeexxdxxxdxedxedxx任選一初始點(diǎn) ，再選兩個線性無關(guān)的向量，如坐標(biāo)單位向量和作為初始搜索方向。從 出發(fā)，順次沿著 、 作一維搜索得到點(diǎn)、 ，兩點(diǎn)連線得到一個新的方向。再從 出發(fā)沿著作一維搜索得到點(diǎn) ，作為下一輪迭代的初始點(diǎn)

19、。下一輪迭代的搜索方向 、 。從 出發(fā)，順次沿著 、作一維搜索，得到點(diǎn) 、211212012222*dxxddGxdxxx，兩點(diǎn)連線得一個新的方向。同一起對 共軛。再從 出發(fā)，沿著作一維搜索得到點(diǎn) 。 點(diǎn)就是該二維問題的極小點(diǎn) 。基本基本POWELLPOWELL法（法（n n維）：維）：1 1）從初）從初始點(diǎn)始點(diǎn)出發(fā)，首先沿著出發(fā)，首先沿著n n個坐標(biāo)軸方向個坐標(biāo)軸方向進(jìn)行一維搜索，得進(jìn)行一維搜索，得到一個終點(diǎn)；到一個終點(diǎn)；2 2）由初）由初始點(diǎn)和終點(diǎn)連線始點(diǎn)和終點(diǎn)連線形成一個形成一個新方向新方向，該方向排在原方向，該方向排在原方向組的最后，去掉原方向組的的第一個方向，形成新的方向組；組的最后

20、，去掉原方向組的的第一個方向，形成新的方向組；3 3）從上一輪的搜索）從上一輪的搜索終點(diǎn)終點(diǎn)出發(fā)沿出發(fā)沿新的搜索方向新的搜索方向作一維搜索而得作一維搜索而得到的極小點(diǎn)，作為到的極小點(diǎn)，作為下一輪下一輪迭代的迭代的始點(diǎn)始點(diǎn)。4 4）從）從新的始點(diǎn)新的始點(diǎn)出發(fā)，沿著出發(fā)，沿著新的方向組新的方向組做一維搜索。做一維搜索。 如此反復(fù)進(jìn)行如此反復(fù)進(jìn)行n n輪輪搜索后，可找到搜索后，可找到n n個共軛方向個共軛方向，若目標(biāo)函數(shù)，若目標(biāo)函數(shù)是是正定二次正定二次型函數(shù)，則經(jīng)過型函數(shù)，則經(jīng)過n n輪后就可以找到極小點(diǎn)。輪后就可以找到極小點(diǎn)。改進(jìn)改進(jìn)POWELLPOWELL法：法： 獲得新方向構(gòu)成新方向組時(shí)獲得新方向構(gòu)成新方向組時(shí), ,不是輪換地