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

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

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

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

4、的性質有關，對等值線是有關，對等值線是同同心圓心圓的目標函數來說，經過的目標函數來說，經過一次迭代一次迭代就可以達到極值點。就可以達到極值點。， 利用利用二次曲線二次曲線來逐點來逐點近似原目標函數近似原目標函數，以，以二次曲線的二次曲線的極極小點小點來來近似原目標函數的極小點近似原目標函數的極小點并逐漸逼近該點。并逐漸逼近該點。 基本牛頓法的迭代公式：基本牛頓法的迭代公式：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）給定初始點收斂精度 ，置2）計算、和，得到；）求，其中，是沿著進行一維搜索的最佳步長；）檢查收斂精度。若，則停止迭代，得最優(yōu)解否則，轉到第二步繼續(xù)進行搜索。，022121211,1

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

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

8、維搜索，最多經過 次迭代就可以 找到二次函數的極小點 。，00k111111xdkd340j01 2k5kk+1kkkkkkTkjkxxa df xxddGd）選定初始點 ，下降方向和收斂精度 ， 置0；2）沿方向進行一維搜索，得；）判斷是否滿足，滿足則打印， 否則，轉到第四步；）提供新的共軛方向，使， ， ，；）置，轉第二步。，111,0iiriirrdvdn n個線性無關的向量系個線性無關的向量系vi vi（i=0,1i=0,1，n-1 n-1 ）一組獨立向量一組獨立向量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 ， 先沿先沿最速下降方向最速下降方向( (負梯度方向負梯度方向) )探索第一步，然后沿與探索第一步，然后沿與該負梯度方向相該負梯度方向相共軛的方向共軛的方向進行探索。進行探索。，1()0Tjkkdgg 它表示沿著方向它表示沿著方向d dk k做一維搜索，做一維搜索，它的終點它的終點x xk+1k+1與始點與始點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)給定初始點x 和計算精度2）取x 的負梯度方向作為搜索方向：置沿方向作一維搜索得判斷收斂：若滿足則令，結束迭代；否則，轉到第五步；）若，則令，轉到第二步開始新的一輪的迭代；否則，轉到第六步；6）構造新的共軛方向112,|1,kkkkkdgdgkk ，令轉到第三步。，221212112( ,)242f x xxxxx x例：用共軛梯度法求二次

11、函數的極小點及極小值。，21112| |(0,1,2,1)kkkkkgdgdgkn 設法構造出一個設法構造出一個對稱正定矩陣對稱正定矩陣 來代替來代替 ，并，并在迭代過程中使在迭代過程中使 逐漸逼近逐漸逼近 , ,那么就簡化了牛頓那么就簡化了牛頓法的計算，并且保持了牛頓法收斂快的優(yōu)點。法的計算，并且保持了牛頓法收斂快的優(yōu)點。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目標函數的偏心率減小到零。，1kkkkkxxHfx變尺度法的迭代公式：變尺度法的迭代公式：搜索方向：搜索方向： =kkkkkdHfxH g 尺度矩陣應具備的條件：尺度矩陣應具備的條件：1 1）為正定對稱矩陣；）為正定對稱矩陣；2 2）具有簡單的迭代形式）具有簡單的迭代形式: :3 3）滿足擬牛頓條件：）滿足擬牛頓條件：令令 則則111()kkkkkHggxx1kkkHHE1kkkygg1kkksxx1kkkHys，0000011111*11)2)()03)=4)(),5)66)kkkkkkkkkkkkkkkkkkxgf xHHIkdH gdxxdgf xsxxyg

13、gxxnH 選定初始點和收斂精度 ；計算，選定初始對稱正定矩陣 （如），置；計算搜索方向；沿方向進行一維搜索，計算， ；判斷是否滿足迭代終止條件，若滿足則，停機，否則轉到 ；若迭代 次后還沒有找到極小點，重置為單位矩陣011277)13kkkkIxxHHEkk，并以當前設計點 為初始點，返回 進行下一輪迭代，否則轉到 ；計算矩陣，置，返回 。，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， 每次僅對多元函數的每次僅對多元函數的一個變量一個變量沿其沿其坐標軸坐標軸進行進行一維探索一維探索，其余各變量均固定不動，并，其余各變量均固定不動，并依次輪換依次輪換進行進行一一維探索的坐標軸維探索的坐標軸，完成第一輪探索后再重新進行第二輪，完成第一輪探索后再重新進行第二輪探索，直到找到目標函數在全域上的最小點為止。探索，直到找到目標函數在全域上的最小點為止。將一個將一個多維多維的無約束最優(yōu)化問題，轉化為的無約束最優(yōu)化問題，轉化為一系一系列的一維問題列的一維問題來求解。來求解。，二維問題二維問題，1 (0,1,2, 1

15、,2, )kkkkiiiixxdkin00100kTiide11()()kkkkiiiif xdf x包括正負包括正負，隨機選擇方法隨機選擇方法加速步長法加速步長法最優(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先以試驗步長確定步長的正負，當沿坐標軸正方向探索能使目標函數值減小時，則取正

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

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

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

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

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