1、 第四章 無約束優化方法4.1 最速下降法4.2 牛頓型方法4.3 共軛梯度法4.6 鮑威爾方法4.4 變尺度法4.5 坐標輪換法4.7 單形替換法無約束優化問題表達形式：無約束優化問題表達形式：12TnXx xx求設計變量求設計變量()minf X 使目標函數使目標函數 數值迭代算法公式數值迭代算法公式:1kkkkXXa d從選定的某從選定的某初始點初始點X0出發，沿著以一定規律產生出發，沿著以一定規律產生的的搜索方向搜索方向d k,取適當的取適當的迭代步長迭代步長ak ,逐次搜尋函逐次搜尋函數值下降的新迭代點數值下降的新迭代點Xk+1,使之逐步逼近最優點使之逐步逼近最優點X*。概概 述述無

2、約束優化無約束優化方法分類方法分類間接法間接法:利用目標函數的利用目標函數的一階或二階導數一階或二階導數直接法直接法:利用利用目標函數值目標函數值最速下降法、牛頓法、共軛梯度法、變尺度法最速下降法、牛頓法、共軛梯度法、變尺度法坐標輪換法、鮑威爾方法、單形替換法等坐標輪換法、鮑威爾方法、單形替換法等 把把初始點初始點X0 、搜索方向搜索方向d k、迭代步長迭代步長ak 稱為優化方稱為優化方法算法的三要素。其中搜索方向法算法的三要素。其中搜索方向d k從根本上決定若從根本上決定若一個算法的成敗、收斂速率的快慢等。一個算法的成敗、收斂速率的快慢等。 無約束優化方法主要不同點在于無約束優化方法主要不同

3、點在于構造搜索方向構造搜索方向上的上的差別。差別。 概概 述述滿足收滿足收斂條件？斂條件？開開 始始給定給定X0、d0*XXa d形成新的形成新的 d計算最佳步長計算最佳步長 ，使，使 極小極小 *()f Xd結結 束束搜索方向搜索方向 d 取該點負梯度方向取該點負梯度方向-f(X) (最速下最速下降方向降方向)，使函數值在，使函數值在該點附近該點附近的范圍內下降最的范圍內下降最快。快。4.1 4.1 最速下降法最速下降法1(0,1,2,)kkkkXXdk1() (0,1,2,)kkkkXXaf Xkx1x20為了使目標函數值沿搜索方向為了使目標函數值沿搜索方向-f(Xk) 能夠獲得最大能夠獲

4、得最大的下降值，其步長因子的下降值，其步長因子 ak 應取一維搜索的最佳步長應取一維搜索的最佳步長:1()kf X4.1 4.1 最速下降法最速下降法( )()kkf Xa f X 可以得最佳步長可以得最佳步長設：設：( )0 根據一元函數極值的必要條件根據一元函數極值的必要條件()kkkf Xaf Xmin ()kkaf Xa f X 復合函數求導公式得復合函數求導公式得 ( ) 1()()0kTkf Xf X1()0kTkdd4.1 4.1 最速下降法最速下降法由此可知，在最速下降法中，相鄰兩個迭代點由此可知，在最速下降法中，相鄰兩個迭代點上的函數梯度相互垂直上的函數梯度相互垂直(正交正交

5、)。而搜索方向就。而搜索方向就是負梯度方向，因此是負梯度方向，因此相鄰兩個搜索方向相鄰兩個搜索方向互相垂互相垂直直。( )()kkkf Xaf X ()Tkkkf Xf X()kf X01()kkkkXXaf X相鄰兩個搜索方向的關系相鄰兩個搜索方向的關系迭代點向函數極小點靠迭代點向函數極小點靠近的過程，走的是曲折近的過程，走的是曲折的路線。形成的路線。形成“之之”字字形的鋸齒現象。在遠離形的鋸齒現象。在遠離極小點的位置，每次迭極小點的位置，每次迭代可使函數值有較多的代可使函數值有較多的下降。在接近極小點的下降。在接近極小點的位置，由于鋸齒現象使位置，由于鋸齒現象使每次迭代行進的距離縮每次迭代

6、行進的距離縮短，收斂速度減慢。短，收斂速度減慢。 最速下降法的搜索路徑最速下降法的搜索路徑4.1 4.1 最速下降法最速下降法x1x201kkXX開開 始始計算計算 ，1*kXX給定初始點給定初始點 ，誤差，誤差 ,令令k=00a()kkdf X計算計算 ，1kkkkXXd1kk計算計算 ，:min ()kkkkf Xd結結 束束4.1 4.1 最速下降法最速下降法例例41 用最速下降法求下列目標函數的極小點。用最速下降法求下列目標函數的極小點。初始點為初始點為 X (0)=2, 2T解解 初始點梯度為：初始點梯度為：01(0)22()50 xxf Xx沿負梯度方向進行一維搜索沿負梯度方向進行

7、一維搜索:(1)(0)(0)0()XXf X2212()25f Xxx1()kkkkXXaf X24-2100 000242 10041000為一維搜索最佳步長，應滿足極值必要條件為一維搜索最佳步長，應滿足極值必要條件 (1)2200()(24)25(2 100)f X4.1 4.1 最速下降法最速下降法008(24)5000(2 100)0算出一維搜索最佳步長算出一維搜索最佳步長 06260.020 030 7231 2524.1 4.1 最速下降法最速下降法第一次迭代設計點位置和函數值第一次迭代設計點位置和函數值 0(1)20241.919 8772 1000.307178 5 10X(1

8、)()3.686164f X繼續作下去，經繼續作下去，經10次迭代后，得到最優解次迭代后，得到最優解 00TX()0f X最速下降法評價：最速下降法評價：1)迭代過程簡單，對初始點選擇迭代過程簡單，對初始點選擇要求不高。要求不高。2)梯度方向目標函數值下降迅速梯度方向目標函數值下降迅速只是個只是個局部性質局部性質，從整體來看，從整體來看，不一定是收斂最快的方向。不一定是收斂最快的方向。3)梯度法相鄰兩次搜索方向的正梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜交性，決定了迭代全過程的搜索路線呈鋸齒狀，在遠離極小索路線呈鋸齒狀，在遠離極小點時逼近速度較快，而在接近點時逼近速度較快，而在接近

9、極小點時逼近速度較慢。極小點時逼近速度較慢。4.1 4.1 最速下降法最速下降法X(k)S(k)S(k+1)X(k+1)X(k+2)X(k+3)X*f(X)=Ckf(X)=Ck+1f(X)=Ck+31 1、牛頓法、牛頓法 在在Xk鄰域內用一個二次函數鄰域內用一個二次函數(X) 來近似代替原來近似代替原目標函數，并將目標函數，并將(X)的極小點作為對目標函數的極小點作為對目標函數f(X) 求優的下一個迭代點。經多次迭代，使之逼近目求優的下一個迭代點。經多次迭代，使之逼近目標函數標函數f(X) 的極小點。的極小點。 ()()()() ()1()()2kkTkkTkf XXf Xf XXXXXXX

10、G1()0kX1()()0kkkf XXXG4.2 4.2 牛頓型方法牛頓型方法()X設設 為為 的極小值點：的極小值點：1kX11()kkkXXGf X牛頓法迭代公式牛頓法迭代公式: 4.2 4.2 牛頓型方法牛頓型方法1()()kkkG XXf X 11()()kkkXXGf X 1()()0kkkf XXXG例例42 用牛頓法求下列目標函數的極小點。初始用牛頓法求下列目標函數的極小點。初始點為點為X0=2,2T解解 初始點梯度：初始點梯度：1(0)22()50 xf Xx海賽矩陣海賽矩陣:222112(0)222212()ffxx xG Xffx xx 2212()25f Xxx11()

11、kkkXXGf X410020050帶入到牛頓迭代公式帶入到牛頓迭代公式 ：海賽矩陣逆陣：海賽矩陣逆陣：11()kkkXXGf X11021050G1010()XXGf X102402121000050 4.2 4.2 牛頓型方法牛頓型方法牛頓法缺陷：牛頓法缺陷： 從牛頓法迭代公式的推演中可以看到，迭從牛頓法迭代公式的推演中可以看到，迭代點的位置是按照極值條件確定的，其中并代點的位置是按照極值條件確定的，其中并未含有沿下降方向未含有沿下降方向搜尋的概念。因此對于搜尋的概念。因此對于非非二次函數二次函數，如果采用上述牛頓迭代公式，有，如果采用上述牛頓迭代公式，有時會使函數值上升。時會使函數值上升

12、。4.2 4.2 牛頓型方法牛頓型方法11()kkkXXGf X2、阻尼牛頓法、阻尼牛頓法 11()kkkkkkkXXdXGf Xk:阻尼因子阻尼因子 ，沿牛頓方向進行，沿牛頓方向進行一維搜索的一維搜索的 最佳步長最佳步長，由下式求得：，由下式求得： 1()()min()kkkkkkkf Xf Xdf Xd4.2 4.2 牛頓型方法牛頓型方法1kkXX開開 始始給定初始點給定初始點 ，誤差，誤差 ,令令k=00a 計算計算 ，1()kkdGf X計算計算 ，1kkkkXXd1kk計算計算 ，:min ()kkkkf Xd阻尼牛頓法阻尼牛頓法4.2 4.2 牛頓型方法牛頓型方法1*kXX結結 束

13、束牛頓型方法評價：牛頓型方法評價： （1） 若迭代點的海賽矩陣為奇異，則很難甚至無若迭代點的海賽矩陣為奇異，則很難甚至無 法求逆矩陣，進而不能構造牛頓法方向；法求逆矩陣，進而不能構造牛頓法方向； （2） 不僅要計算梯度，還要求海賽矩陣及其逆矩不僅要計算梯度，還要求海賽矩陣及其逆矩 陣，計算量和存儲量大。陣，計算量和存儲量大。 4.2 4.2 牛頓型方法牛頓型方法為了克服最速下降法的鋸齒現象，提高收斂速度為了克服最速下降法的鋸齒現象，提高收斂速度;同時克服牛頓型方法需要計算二階導數及其逆陣，同時克服牛頓型方法需要計算二階導數及其逆陣，計算量大的現象，發展了一類共軛方向法。該方計算量大的現象，發展

14、了一類共軛方向法。該方法的搜索方向是法的搜索方向是共軛方向共軛方向。一、共軛方向的概念一、共軛方向的概念12TTfXX GXb Xc4.34.3 共軛梯度法共軛梯度法 式中：式中：c為常數，為常數，X, b為為2維列向量，維列向量，G為為n階對稱階對稱正定矩陣。正定矩陣。二元二次函數二元二次函數為避免鋸齒的發生，取下一次的迭代搜索方向為避免鋸齒的發生，取下一次的迭代搜索方向直接指向極小點，如果選定這樣的搜索方向，直接指向極小點，如果選定這樣的搜索方向，對于二元二次函數只需進行兩次直線搜索就可對于二元二次函數只需進行兩次直線搜索就可以求到極小點。以求到極小點。1000XXa d*111XXa d

15、100TfXd4.34.3 共軛梯度法共軛梯度法 和和 應具有什么樣的關系？應具有什么樣的關系？1d0dX0a0d0X1- -f(X1)a1d1對于二次函數對于二次函數 在在X* 處取得極小點的必要條件處取得極小點的必要條件:12TTfXX GXb Xc*0fX*111fXG Xa db1110fXaGd 等式兩邊同乘等式兩邊同乘 得得:0Td010TdGd 滿足上式的兩個向量滿足上式的兩個向量 , 是是G的的共軛方向。共軛方向。0d1d111GXbaGdX0a0d0X1- -f(X1)a1d1*GXb二二. .共軛方向的性質共軛方向的性質1）非零向量系）非零向量系d0, d1, d2, ,

16、dn-1是對是對G共軛，共軛， 則這則這n個向量線性無關。個向量線性無關。2）在在n維空間中互相共軛的非零向量個數不維空間中互相共軛的非零向量個數不 超過超過n。 3）從任意初始點出發，順次沿）從任意初始點出發，順次沿n個個G的共軛的共軛 方向方向d0,d1, d2,進行一維搜索，進行一維搜索，最多經過最多經過 n次迭代就可以找到次迭代就可以找到二次函數二次函數f(X)極小點極小點。 4.34.3 共軛梯度法共軛梯度法 二二. .共軛方向的性質共軛方向的性質4.34.3 共軛梯度法共軛梯度法 X0a0d0X1a1d1共軛梯度法是共軛方向法的一種，共軛向量由共軛梯度法是共軛方向法的一種，共軛向量

17、由迭代點的負梯度構造出來，所以稱共軛梯度法。迭代點的負梯度構造出來，所以稱共軛梯度法。12TTfXX GXb Xc1kkkkXXa d1kkkkXXa d()kkf XGXb從點從點Xk 出發，沿出發，沿G某一方向某一方向dk 作一維搜索作一維搜索,到達到達Xk+111()kkf XGXb而在點而在點Xk 、Xk+1 處的梯度分別為：處的梯度分別為：4.3 4.3 共軛梯度方法共軛梯度方法三三. .共軛梯度法共軛梯度法11()()kkkkf Xf XG XX+10TkkdGd 11()()0Tkkkdf Xf X得出共軛方向與梯度之間的關系。此式表明沿得出共軛方向與梯度之間的關系。此式表明沿方

18、向方向d k進行一維搜索，其終點進行一維搜索，其終點Xk+1與始點與始點Xk 的的梯度值差梯度值差f(Xk+1)- f(Xk)與與d k的共軛方向的共軛方向d k+1 正交。正交。 4.3 4.3 共軛梯度方法共軛梯度方法如果方向如果方向d k+1與方向與方向d k對對G共軛共軛:kka Gd共軛梯度法的幾何說明共軛梯度法的幾何說明4.3 4.3 共軛梯度方法共軛梯度方法 1()()0Tjkkdf Xf XXkdkf(Xk)d k+1X*Xk+1f(Xk+1)f(Xk+1) -f(Xk)共軛梯度法遞推公式共軛梯度法遞推公式( (推導過程自學推導過程自學) )：其中其中: :11()kkkkf

19、X dd212()()kkkf Xf X4.3 4.3 共軛梯度方法共軛梯度方法開開 始始初始點初始點 ,誤差誤差 ,0 x計算計算 ，1kkkkXXd計算計算 ，:min ()kkkkf Xd共軛梯度法共軛梯度法1*kXX結結 束束1kk10kXX000,kdf11212()()()kkkkkkkf Xf Xf X dd1()kf XK=n1?共軛梯度法評價：共軛梯度法評價：1)搜索方向是對負梯度方向搜索方向是對負梯度方向的修正，因此具有最速下的修正，因此具有最速下降法的優點（收斂速度比降法的優點（收斂速度比最速下降法快）；最速下降法快）；2)共軛梯度法需求一階導數共軛梯度法需求一階導數，所

20、用公式及算法簡單，所用公式及算法簡單，所需存儲量少（適用于大所需存儲量少（適用于大規模問題）。規模問題）。4.3 4.3 共軛梯度方法共軛梯度方法11()kkkkf X dd212()()kkkf Xf X迭代公式：迭代公式：x1x20Xk2212112( )242fxxxx xx，已知初始點，已知初始點1,1T 解：解： 1）第一次沿）第一次沿負梯度方向負梯度方向搜尋搜尋012(0)212244()422xxf Xxxx0(1)(0)000014141 212XX d為一維搜索最佳步長，應滿足為一維搜索最佳步長，應滿足(1)(0)0()min()min(40203)f Xf X2000d迭代

21、精度迭代精度 。 0.0014.3 4.3 共軛梯度方法共軛梯度方法得得:00.25(1)20.5X2）第二次迭代：）第二次迭代：2(1)20(0)()50.2520()f Xf X(1)1()2f X(1)00121.5()f Xdd(2)(1)122220.5 1.50.51.5XX1111d代入目標函數代入目標函數22()(22)2(0.5 1.5)2(22)(0.5 1.5)4(22)()f X 11111111()kkkkf X dd212()()kkkf Xf X得得11因因(2)()0f X,收斂。收斂。( )0 由由(2)(2)(2)40,()8,()20Xf Xf X 從而有

22、：從而有：仍從仍從 ，即，即 出發進行最速下降法尋優。出發進行最速下降法尋優。此時：此時：目標函數目標函數 引入變換引入變換: y1=x1, y2=5x2則函數則函數f(X)變為：變為：2212()25f Xxx221212(,)y yyy(0)2,2TX02,10TY 01(0)224()220yYyy4.4 變尺度法變尺度法利用最速下降法經利用最速下降法經10次迭代后，得到最優解次迭代后，得到最優解 00TX()0f X例題：例題：(1)(0)(0)0000()242410201020YYaYaaa搜索最佳步長可由極值條件：搜索最佳步長可由極值條件：(1)(0)(0)22()min ()m

23、in( )( )(24 )(1020 )aaYYaYaaaa 0()0a由由0260.552a 沿負梯度方向進行一維搜索：沿負梯度方向進行一維搜索：4.4 變尺度法變尺度法0(1)(1)0240,()010200aYYa 經變換后，只需一次迭代，就可找到最優解。經變換后，只需一次迭代，就可找到最優解。這是因為經過尺度變換：這是因為經過尺度變換：1122,5yx yx等值線由橢圓變成圓。等值線由橢圓變成圓。從而算得一步計算后設計點的位置及其目標函數：從而算得一步計算后設計點的位置及其目標函數：x0 x1x2x1x20y2y1Y01. 基本思想基本思想 最速下降法法構造簡單，只用到一階偏導數，計最

24、速下降法法構造簡單，只用到一階偏導數，計算量小，迭代初期收斂速度快，但當迭代到最優點附算量小，迭代初期收斂速度快，但當迭代到最優點附近時收斂速度很慢；近時收斂速度很慢；牛頓法收斂很快，對于二次函數只需迭代一次便牛頓法收斂很快，對于二次函數只需迭代一次便達到最優點，對非二次函數也能較快迭代到最優點，達到最優點，對非二次函數也能較快迭代到最優點，但要計算二階偏導數矩陣及其逆陣，對維數較高的優但要計算二階偏導數矩陣及其逆陣，對維數較高的優化問題，其計算工作和存儲量都太大。化問題，其計算工作和存儲量都太大。 變量的尺度變換是放大或縮小各個坐標。通過尺變量的尺度變換是放大或縮小各個坐標。通過尺度變換可以

25、把函數的偏心程度降到最低限度。度變換可以把函數的偏心程度降到最低限度。 4.4 變尺度法變尺度法XQX進行尺度變換進行尺度變換在新的坐標系中，函數在新的坐標系中，函數f(X)的二次項變為：的二次項變為：1122TTTXXX QQXGG目的：目的：減少二次項的偏心減少二次項的偏心如如G是正定，則總存在矩陣是正定，則總存在矩陣Q，使得：，使得：GITQQ 對于二次函數對于二次函數:1()2TTf XXXXGbc4.4 變尺度法變尺度法 用矩陣用矩陣Q-1右乘等式兩邊，得：右乘等式兩邊，得：1GTQQ用矩陣用矩陣Q左乘等式兩邊，得：左乘等式兩邊，得：GITQQ所以所以1GTQQ4.4 變尺度法變尺度

26、法上式說明：二次函數矩陣上式說明：二次函數矩陣G的逆陣，可以通過尺度變換的逆陣，可以通過尺度變換矩陣矩陣 來求得。來求得。TAQQGITQQ 1()kkkkkXXf XAAk 是需要構造是需要構造nn的一個對稱方陣的一個對稱方陣 ，稱為，稱為尺度矩陣尺度矩陣如如Ak=I, 則得到則得到最速下降法最速下降法 ；1kGA ，則得到，則得到阻尼牛頓法阻尼牛頓法 ；如如當矩陣當矩陣Ak 不斷地迭代而能很好地逼近不斷地迭代而能很好地逼近 1G時，就可以不再需要計算二階導數。時，就可以不再需要計算二階導數。 變尺度法的關鍵在于尺度矩陣變尺度法的關鍵在于尺度矩陣Ak的產生的產生 。4.4 變尺度法變尺度法1

27、）對變尺度矩陣的要求：）對變尺度矩陣的要求：2.構造尺度矩陣構造尺度矩陣Ak要求要求Ak 中的每一個矩陣都是對稱正定矩陣中的每一個矩陣都是對稱正定矩陣 要求要求dk=- Ak f(Xk)為下降方向為下降方向 要求要求f(Xk) Tdk0 f(Xk) TAk f(Xk) 0 f(Xk) T Ak f(Xk) 0 既要求既要求Ak為對稱正定為對稱正定1()kkkkkXXf XAx1x20- -f(Xk)f(Xk)最速上升方向最速上升方向最速下降方向最速下降方向下降方向下降方向上升方向上升方向Xk1）對變尺度矩陣的要求：）對變尺度矩陣的要求：2.構造尺度矩陣構造尺度矩陣Ak 要求要求Ak之間的迭代具

28、有簡單的形式之間的迭代具有簡單的形式 Ak1 Ak Ak Ak為校正矩陣為校正矩陣1()kkkkkXXf XA 要求要求Ak必須滿足擬牛頓條件必須滿足擬牛頓條件11()()kkkkf Xf XG XX111()()kkkkGf Xf XXX111()()kkkkkAf Xf XXX擬牛頓條件擬牛頓條件1kkkAAA中修正矩陣中修正矩陣 的不斷修正，在迭代中逐步逼近于的不斷修正，在迭代中逐步逼近于 kA1()kXGDFP法法:TkkkkkTkkkTkkTkkXXffXfffAAAA11()()kkkkkkff Xf XXXX 式中式中2）具體構造方法：）具體構造方法： 從初始矩陣從初始矩陣A0=

29、I(單位矩陣單位矩陣)開始，通過對公式開始，通過對公式 2.構造尺度矩陣構造尺度矩陣Ak開開 始始初始點初始點 ,誤差誤差 ,0X計算計算 ，1kkkkXXd計算計算 ，:min ()kkkkf Xd變尺度法變尺度法1*kXX結結 束束1kk01kXX000,kdfK=n11kkXXkkkdAf 1kkkAAA變尺度法評價：變尺度法評價：1) 收斂速度快，且只需求一階導數，不需要求收斂速度快，且只需求一階導數，不需要求出海賽矩陣（適用于大規模問題，出海賽矩陣（適用于大規模問題，20個變量個變量以上）以上） ；2)由于舍入誤差和一維搜索的不精確，可能導由于舍入誤差和一維搜索的不精確，可能導致尺度

30、矩陣奇異，進而在穩定性方面不夠理致尺度矩陣奇異，進而在穩定性方面不夠理想。可進一步改進（想。可進一步改進（BFGS算法）。算法）。解：解： 1）取初始點）取初始點 ，為了按，為了按DFP法構造第一法構造第一次搜尋方向次搜尋方向d0，需計算初始點處的梯度，需計算初始點處的梯度2212112()242f Xxxxx x(0)1 1TX012(0)212244()422xxf Xxxx取初始變尺度矩陣為單位矩陣取初始變尺度矩陣為單位矩陣A0=I，則第一次搜尋方向為，則第一次搜尋方向為 00(0)1044()0122f X dA例例:用用DFP算法求下列問題的極值：算法求下列問題的極值：0(1)(0)

31、000014141 212XX d一維搜索最佳步長應滿足一維搜索最佳步長應滿足(1)(0)02000()min()min(40203)f Xf Xd得得:00.25(1)20.5X2）再按）再按DFP法構造點法構造點X (1)處的搜尋方向處的搜尋方向d1，需計算，需計算12(1)212241()422xxf Xxx 沿沿d0方向進行一維搜索，得方向進行一維搜索，得0(1)(0)143()()224ff Xf X (0)(1)(0)2110.510.5XXX 代入校正公式代入校正公式1310.5340.543310.53444=TkTTTXXffXfff00000000000AAAA100AAA

32、21191010.5912112550010.50.251216194152550100=第二次搜尋方向為第二次搜尋方向為11(1)86()65f X dA再沿再沿d1進行一維搜索，得進行一維搜索，得1(2)(1)11182560.55XXda1為一維搜索最佳步長，應滿足為一維搜索最佳步長，應滿足(2)(1)12111811()min()min(4)52f Xf Xd154(2)42X ,得得3）判斷）判斷X (2)是否為極值點是否為極值點梯度梯度: 12(2)212240()420 xxf Xxx 海賽矩陣海賽矩陣 :2(2)22()24f X梯度為零向量梯度為零向量,海賽矩陣正定。可見滿足

33、極值充要海賽矩陣正定。可見滿足極值充要條件，因此為極小點。條件，因此為極小點。 *(2)42TXX*()8f X 4.5 4.5 坐標輪換法坐標輪換法一一. . 坐標輪換法：坐標輪換法：1. 1. 基本思想：基本思想：每次搜索只允許一個變量每次搜索只允許一個變量變化，其余變量保持不變，變化，其余變量保持不變，即沿坐標方向輪流進行搜即沿坐標方向輪流進行搜索的尋優方法。它把多變索的尋優方法。它把多變量的優化問題輪流地轉化量的優化問題輪流地轉化成單變量（其余變量視為成單變量（其余變量視為常量）的優化問題，因此常量）的優化問題，因此又稱這種方法為變量輪換又稱這種方法為變量輪換法。此種方法只需目標函法。

34、此種方法只需目標函數的數值信息而不需要目數的數值信息而不需要目標函數的導數。標函數的導數。x1x20X11X12X21X*X00X22計算步驟計算步驟:任選初始點任選初始點,確定搜索方向確定搜索方向第一輪的起點第一輪的起點 ，置，置n個坐標軸方向矢量為單位坐標矢量個坐標軸方向矢量為單位坐標矢量00X00011e00102e1000ne4.5 4.5 坐標輪換法坐標輪換法迭代計算迭代計算1kkkiiiiXXek為迭代輪數的序號，取為迭代輪數的序號，取k=1，2，；i為該輪中一維搜索的序號，取為該輪中一維搜索的序號，取i=1，2，n步長步長一般通過一維優化方法求出其最優步長。一般通過一維優化方法求

35、出其最優步長。判斷是否中止迭代判斷是否中止迭代0?kknXX如滿足，迭代中止，如滿足，迭代中止，并輸出最優解并輸出最優解最優解最優解*kXX*)(*xFF 否則，令否則，令kk+1返回步驟（返回步驟（2）4.5 4.5 坐標輪換法坐標輪換法 應該是一輪迭代應該是一輪迭代的始點和終點，的始點和終點，不是某搜索方向不是某搜索方向的前后迭代點。的前后迭代點。10kknXX1kk 1ii 開開 始始初始點初始點 , 誤差誤差 ,X 00坐標輪換法的流程圖坐標輪換法的流程圖0?kknXX1k結結 束束*knXX?in沿著沿著ei方向一維搜索方向一維搜索ai 計算計算 ，1kkkiiiiXXe,()kiX

36、Xff X1i例例:用坐標輪換法求下列目標函數的無約束最優解。用坐標輪換法求下列目標函數的無約束最優解。 給定初始點給定初始點 ，精度要求，精度要求=0.122121212()10460F Xxxx xxx000X 解：解：做第一輪迭代計算做第一輪迭代計算沿沿e1方向進行一維搜索方向進行一維搜索10101 1XXe式中式中, X00 為第一輪的起始點，取為第一輪的起始點，取111101000X 按最優步長原則確定最優步長按最優步長原則確定最優步長1，即極小化，即極小化12111min()1060F X此問題可由某種一維優化方法求出此問題可由某種一維優化方法求出1: 01021511150X 以

37、以X11為新起點，沿為新起點，沿e2方向一維搜索方向一維搜索11212 22255001XXe 以最優步長原則確定以最優步長原則確定2，即為極小化，即為極小化12122min()935F X5 . 421254.5X對于第一輪按終止條件檢驗對于第一輪按終止條件檢驗10222054.56.7XX計算計算5輪后，有輪后，有55200.0413XX故近似優化解為故近似優化解為527.9883*5.9981XX*(*)7.95025ff X4.54.5 坐標輪換坐標輪換法法 3. 方法評價：方法評價： 方法簡單，容易實現。方法簡單，容易實現。 當維數增加時，效率明顯下降。當維數增加時，效率明顯下降。

38、收斂慢，以振蕩方式逼近最優點收斂慢，以振蕩方式逼近最優點。 受目標函數的性態影響很大。受目標函數的性態影響很大。 如圖如圖 a) 所示，二次就收斂到極值點；所示，二次就收斂到極值點； 如圖如圖 b) 所示，多次迭代后逼近極值點；所示，多次迭代后逼近極值點； 如圖如圖 c) 所示，目標函數等值線出現山脊（或稱陡所示，目標函數等值線出現山脊（或稱陡谷），若搜索到谷），若搜索到 A 點，再沿兩個坐標軸以點，再沿兩個坐標軸以t0步長步長測試，目標函數值均上升，計算機判斷測試，目標函數值均上升，計算機判斷 A 點為最優點為最優點。事實上發生錯誤。點。事實上發生錯誤。x1x2最優點最優點 X*X(0) x

39、1x2最優點最優點 X*X(0) x2x1最優點最優點 X*終點終點 A脊線脊線 X(0) 鮑威爾方法是直接搜索法中一個十鮑威爾方法是直接搜索法中一個十分有效的算法。該算法是沿著逐步產生的分有效的算法。該算法是沿著逐步產生的共軛方向進行搜索的，因此本質上是一種共軛方向進行搜索的，因此本質上是一種共軛方向法。共軛方向法。4.64.6 鮑威爾方法鮑威爾方法 一、共軛方向的生成一、共軛方向的生成4.64.6 鮑威爾方法鮑威爾方法 ()0Tjkdf X1()0Tjkdf XXk, Xk+1為兩個極小點為兩個極小點1()()0Tjkkdf Xf X根據梯度與等值面之間關系可知根據梯度與等值面之間關系可知

40、f (Xk)f (Xk+1)d jd jXkXk+1一、共軛方向的生成一、共軛方向的生成4.64.6 鮑威爾方法鮑威爾方法 對于二次函數，對于二次函數，Xk, Xk+1兩點處的梯度可表示為兩點處的梯度可表示為()kkf XGXb11()kkf XGXb11()()()kkkkf Xf XG XX1()()0Tjkkdf Xf X代入到公式：代入到公式：一、共軛方向的生成一、共軛方向的生成4.64.6 鮑威爾方法鮑威爾方法 1()0TjkkdG XX結論：結論：從不同的點出從不同的點出發沿某一方向分別對發沿某一方向分別對函數作兩次一維搜索函數作兩次一維搜索，得到兩個，得到兩個極小點極小點，那么這

41、兩個極小點的那么這兩個極小點的連線方向與該方向對連線方向與該方向對G共軛共軛f (Xk)f (Xk+1)d jd jd kXkXk+1二、鮑威爾基本算法二、鮑威爾基本算法鮑威爾基本算法的搜索過程（二維）鮑威爾基本算法的搜索過程（二維）x1x2X10X20X11d2d1 X*X0X01X21二、鮑威爾基本算法二、鮑威爾基本算法鮑威爾基本算法的搜索過程（三鮑威爾基本算法的搜索過程（三維）維）x1x2x30X0(1)e1e3S1S1e2e2e3X2(3)X(3)S2S3S1X(2)S2e3第一輪：第一輪：e1, e2, e3第二輪：第二輪：e2,e3, S1第三輪：第三輪：e3, S1, S2 X(

42、1)X3(1)X2(1)X1(1)X1(2)X2(2)X3(2)X1(3)X3(3) 鮑威爾基本算法的步驟：鮑威爾基本算法的步驟： 1） 第一輪基本方向組取單位坐標矢量系第一輪基本方向組取單位坐標矢量系e1、 e2、 e3 、 en，沿這些方向依次作一維搜索，然后將始末兩點相，沿這些方向依次作一維搜索，然后將始末兩點相連作為新生方向。連作為新生方向。 2）再沿新生方向作一維搜）再沿新生方向作一維搜索，完成第一輪的迭代索，完成第一輪的迭代。以后每輪的基本方向。以后每輪的基本方向組是將上輪的第一個方組是將上輪的第一個方向淘汰，上輪的新生方向淘汰，上輪的新生方向補入本輪的最后而構向補入本輪的最后而構

43、成：成： d2k , d3k , dnk , dk 鮑威爾基本算法的缺陷：鮑威爾基本算法的缺陷： 可能在某一輪迭代中出現基本方向組為線性相關的可能在某一輪迭代中出現基本方向組為線性相關的矢量系的情況。如第矢量系的情況。如第k輪中，產生新的方向：輪中，產生新的方向： dk=Xnk-X0k= 1kd1k+ 2kd2k + + nkdnk 式中，式中， d1k、d2k 、 、 dnk為第為第k輪基本方向組矢輪基本方向組矢量，量， 1k 、 2k、 、 nk為各方向的最優步長。為各方向的最優步長。 若在第若在第k輪的優化搜索過程中出現輪的優化搜索過程中出現 1k=0，則方向，則方向dk表表示為示為d2

44、k、 d3k 、 、 dnk的線性組合，以后的各次搜索的線性組合，以后的各次搜索將在降維的空間進行，無法得到將在降維的空間進行，無法得到n維空間的函數極小值，維空間的函數極小值，計算將失敗。計算將失敗。鮑威爾基本算法的退化鮑威爾基本算法的退化x1x2x3 1=0如圖所示為一個如圖所示為一個三維優化問題的三維優化問題的示例，設第一輪示例，設第一輪中中 1 =0 ，則新，則新生方向生方向S1與與e2 、e3共面，隨后的共面，隨后的各環方向組中，各環方向組中，各矢量必在該平各矢量必在該平面內，使搜索局面內，使搜索局限于二維空間，限于二維空間，不能得到最優解。不能得到最優解。e2e3S1 2e2 3e

45、3S1三、鮑威爾修正算法三、鮑威爾修正算法 在某輪已經取得的在某輪已經取得的n+1個方向中，選取個方向中，選取n個線性無關的個線性無關的并且共軛程度盡可能高的方向作為下一輪的基本方向組并且共軛程度盡可能高的方向作為下一輪的基本方向組 鮑威爾修正算法的搜索方向的構造：在第鮑威爾修正算法的搜索方向的構造：在第k輪的搜索中輪的搜索中， X0k 為初始點，搜索方向為為初始點，搜索方向為d1k、d2k 、 、 dnk，產生，產生的新方向為的新方向為dk ，此方向的極小點為，此方向的極小點為X k。沿。沿dk方向移動得到方向移動得到點點 Xn+1k=2Xnk-X0k ， 稱之為稱之為X0k對對Xnk的映射

46、點。的映射點。 計算計算X0k 、 X1k、 、 Xnk、Xk、Xn+1k 各點的函數值各點的函數值，記作：，記作： F1=F(X0k) F2=F(Xnk) F3=F(Xn+1k) = F(Xm-1k)-F(Xmk) 是第是第k輪方向組中，依次沿各方向搜索函數下降值輪方向組中，依次沿各方向搜索函數下降值11maxmimmi nff 鮑威爾算法的方向淘汰鮑威爾算法的方向淘汰kXknd1kmXkmX3kd1kX1kd2kX2kdkd(F3)(F2)(F1)函數最大下降量函數最大下降量m始點始點終點終點1knX反射點反射點knX0kX為了構造第為了構造第k+1輪基本方向組，采用如下判輪基本方向組，采

47、用如下判別式別式： 按照以下兩種情況處理按照以下兩種情況處理： 1) 不滿足判別式不滿足判別式，則第，則第k+1輪的基本方向仍用輪的基本方向仍用老方向組老方向組d1k、d2k、 、 dnk。 k+1輪的初始點取輪的初始點取 X0k+1=Xnk F2F3 X0k+1=Xn+1k F2 F331221231213(2)()()2mmFFFFFFFFF目標函數值小的點作目標函數值小的點作為下一輪的起始點為下一輪的起始點2）滿足判別式）滿足判別式，則淘汰函數值下降最大的方向，則淘汰函數值下降最大的方向，并用第并用第k輪的新生方向補入輪的新生方向補入k+1輪基本方向組的最輪基本方向組的最后，即后，即k+

48、1輪的方向組為輪的方向組為d1k、d2k 、 、 dm-1k、dm+1k 、 、dnk、 dk 。1knXkXknXknd0kX1kmXkmX3kd2kX1kX1kd2kdkd(F3)(F2)(F1)反射點反射點始點始點終點終點函數最大下降量函數最大下降量mkmdk+1輪的初始點取輪的初始點取: X0k+1=X k Xk是第是第k輪沿輪沿dk方向搜索的極小點。方向搜索的極小點。 1knXkXknXknd0kX1kmXkmX3kd2kX1kX1kd2kdkd(F3)(F2)(F1)反射點反射點始點始點終點終點函數最大下降量函數最大下降量mkmd四、四、 修正算法的迭代步驟及流程圖修正算法的迭代步

49、驟及流程圖Powell算法的步驟如下：算法的步驟如下： 任選初始迭代點任選初始迭代點X01 ，選定迭代精度，選定迭代精度，取初始基本，取初始基本 方向組為單位坐標矢量系方向組為單位坐標矢量系1iide其中，其中，i=1，2n 然后令然后令k=1（輪數）開始迭代（輪數）開始迭代 沿沿dik 諸方向依次進行諸方向依次進行n次一維搜索，確定各步長次一維搜索，確定各步長 11()min()kkkkkiiiiiiF XdF Xd得到點陣得到點陣 i=1，2n1kkkkiiiiXXd構成新生方向構成新生方向k0kkndXX沿沿dk 方向進行一維搜索求得優化步長方向進行一維搜索求得優化步長akkkkknXX

50、d(3)計算各迭代點的函數值計算各迭代點的函數值 F(Xik) ，找出相鄰點函數值差最大者，找出相鄰點函數值差最大者11max ()()kkmiimmF XF XFF（1mn）及與之相對應的兩個點及與之相對應的兩個點 和和 ，并以，并以 表示兩點表示兩點的連線方向。的連線方向。()kiF X1kmXkmXkmd（4）關鍵點函數值關鍵點函數值102kkknnXXX31()knFF X10()kFF X2()knFF X（5） 判斷是否滿足迭代終止條件。判斷是否滿足迭代終止條件。0kkXX則可結束迭代，最優解為則可結束迭代，最優解為*kXX*(*)FF X停止計算。否則，繼續進行下步。停止計算。否

51、則，繼續進行下步。檢驗鮑威爾判別條件是否成立檢驗鮑威爾判別條件是否成立31221231213(2)()()2mmFFFFFFFFF 不滿足判別式轉下步，否則轉步驟不滿足判別式轉下步，否則轉步驟 確定確定k+1輪的基本方向組和起始點輪的基本方向組和起始點1kkiidd（即取原方向組即取原方向組）1002knkkknXXXX當當F2F3當當F2F3令令kk+1，返回步驟，返回步驟 確定確定k+1輪的方向組和起始點輪的方向組和起始點1111(,)kkkkimmkddddd10kkxx令令kk+1，返回步驟，返回步驟例例 試用鮑威爾修正算法求目標函數的最優解。已知試用鮑威爾修正算法求目標函數的最優解。

52、已知 初始點初始點 ，迭代精度，迭代精度=0.00101 1TX011X 01()3FF X 2112221242)(xxxxxxF解解：第一輪迭代計算第一輪迭代計算沿第一坐標方向沿第一坐標方向e1進行一維搜索進行一維搜索021 111min()43F Xe1=21011 11132101XXe 11()7F X 以以X11 為起點，改沿第二坐標軸方向為起點，改沿第二坐標軸方向e2進行一維搜索進行一維搜索1212222min()227F Xe2=0.511212 23030.5111.5XXe 122()7.5FF X 構成新方向構成新方向111203121.510.5dXX 沿沿d1方向進行

53、一維搜索得極小點與極小值方向進行一維搜索得極小點與極小值11951710X 1()7.9F X 計算點距計算點距2201917112.886510kkXX需進行第二輪迭代計算需進行第二輪迭代計算第二輪迭代計算第二輪迭代計算首先確定上輪中的最大函數下降量及其相應方向首先確定上輪中的最大函數下降量及其相應方向11101()()4F XF X 11212()()0.5F XF X 12max,4m 11mde映射點及其函數值映射點及其函數值111120315221.512nXXX 131()7nFF x 檢查鮑威爾條件檢查鮑威爾條件221231213(2)()()2mmFFFFFFF 212312(

54、2)()1.25mFFFFF 213()322mFF于是可知于是可知13FF 滿足判別式。第二輪方向組和起始點為滿足判別式。第二輪方向組和起始點為122(,)ide d210XX210()7.9FF X 31221231213(2)()()2mmFFFFFFFFF沿沿e2方向作一維搜索得方向作一維搜索得211951910X 21()7.98F X 以以 為起點沿為起點沿d1方向一維搜索得方向一維搜索得21X2299259750X 222()7.996FF X 構成新生方向構成新生方向222209919425525971712551050dXX沿沿d2方向一維搜索得方向一維搜索得242X 2()

55、8F X 檢查迭代終止條件檢查迭代終止條件222201917420.360510XX需再作第三輪迭代計算需再作第三輪迭代計算?根據具體情況來分析，根據具體情況來分析，d1，d2實際上為共軛方向，見下圖。實際上為共軛方向，見下圖。本題又是二次函數，有共軛方向的二次收斂性，上面結果本題又是二次函數，有共軛方向的二次收斂性，上面結果就是問題的最優解。可以預料，如果做第三輪迭代，則一就是問題的最優解。可以預料，如果做第三輪迭代，則一定各一維搜索的步長為零，必有定各一維搜索的步長為零，必有33200XX故得最優解故得最優解4*2X 8*Fx*F(X)= -3-7.0-7.50 x1x2121234221

56、2112()242F Xxxxx xx1(0)x1(1)x(1)x2(1)在不計算導數的情況下，先算出若干點處的函數值，在不計算導數的情況下，先算出若干點處的函數值，從它們之間的大小關系中也可以看出函數變化的大概從它們之間的大小關系中也可以看出函數變化的大概趨勢，為尋求函數的下降方向提供依據。趨勢，為尋求函數的下降方向提供依據。原理：原理：構造具有構造具有n+1個頂點的單純形，利用單純形的頂個頂點的單純形，利用單純形的頂點，計算其函數值并加以比較，從中確定有利的搜索點，計算其函數值并加以比較，從中確定有利的搜索方向和步長，找到一個較好的點取代單純形中較差的方向和步長，找到一個較好的點取代單純形

57、中較差的點，組成新的單純形來代替原來的單純形。使新單純點，組成新的單純形來代替原來的單純形。使新單純形不斷的向目標函數的極小點靠近，直到搜索到極小形不斷的向目標函數的極小點靠近，直到搜索到極小點位置點位置4.74.7 單形替換法單形替換法方法方法 4.74.7 單形替換法單形替換法方法方法 設設123()()()f Xf Xf X544141()2XXXXXXX5稱為稱為X1點相對于點相對于X4點的反射點點的反射點取取X4為為X2點、點、X3點連線的中點點連線的中點x1x20X2X1X4X3X5最好點最好點最差點最差點次差點次差點4.74.7 單形替換法單形替換法方法方法 五種情況：五種情況：1）如果如果f(X6) f(X5)構成新的單純形構成新的單純形X2X3X6如果如果f(X6) f(X5)構成新的單純形構成新的單純形X2X3X553()()f Xf X6441()1.2 2.0XXXXx1x20X1X3X2X5x4X6最好點最好點最差