1、第四章 無約束優化方法 最速下降法，牛頓型方法 概述 在求解目標函數的極小值的過程中，若對設計變量的取值范圍不加限制，則稱這種最優化問題為無約束優化問題。盡管對于機械的優化設計問題，多數是有約束的，無約束最優化方法仍然是最優化設計的基本組成部分。因為約束最優化問題可以通過對約束條件的處理，轉化為無約束最優化問題來求解。為什么要研究無約束優化問題? （1）有些實際問題，其數學模型本身就是一個無約束優化問題。 （2）通過熟悉它的解法可以為研究約束優化問題打下良好的基礎。 （3）約束優化問題的求解可以通過一系列無約束優化方法來達到。 所以無

2、約束優化問題的解法是優化設計方法的基本組成部分，也是優化方法的基礎。 根據構成搜索方向所使用的信息性質的不同，無約束優化方法可以分為兩類。一：間接法要使用導數的無約束優化方法，如梯度法、（阻尼）牛頓法、變尺度法、共軛梯度法等。 二：直接法只利用目標函數值的無約束優化問題，如坐標輪換法、鮑威爾法單純形法等。無約束優化問題的一般形式可描述為：求n維設計變量 使目標函數 目前已研究出很多種無約束優化方法，它們的主要不同點在于構造搜索方向上的差別。無約束優化問題的求解：1、解析法可以利用無約束優化問題的極值條件求得。即將求目標函數的極值問題變成求方程的解。也就是求使其滿足解上述方程

3、組，求得駐點后，再根據極值點所需滿足的充分條件來判定是否為極小值點。但上式是一個含有個未知量，個方程的方程組，在實際問題中一般是非線性的，很難用解析法求解，要用數值計算的方法。由第二章的講述我們知道，優化問題的一般解法是數值迭代的方法。因此，與其用數值方法求解非線性方程組，還不如用數值迭代的方法直接求解無約束極值問題。2、數值方法數值迭代法的基本思想是從一個初始點出發，按照一個可行的搜索方向搜索，確定最佳的步長使函數值沿方向下降最大，得到點。依此一步一步地重復數值計算，最終達到最優點。優化計算所采用的基本迭代公式為 （4.2）在上式中， 是第是 k+1 次搜索或迭代方向，稱為搜索方向（迭代方向

4、）。由上面的迭代公式可以看出，采用數值法進行迭代求優時，需要確定初始點、搜索方向和迭代步長，稱為優化方法迭代算法的三要素。第三章我們已經討論了如何在搜索方向上確定最優步長的方法，本章我們將討論如何確定搜索方向。最常用的數值方法是搜索方法，其基本思想如下圖所示：無約束優化方法可以分為兩類。一類是通過計算目標函數的一階或二階導數值確定搜索方向的方法，稱為間接法，如最速下降法、牛頓法、變尺度法和共軛梯度法。另一類是直接利用目標函數值確定搜索方向的方法，稱為直接法，如坐標輪換法、鮑威爾法和單形替換法。各種無約束優化方法的區別在于確定其搜索方向0d的方法不同。 41最速下降法最速下降法是一個求

5、解極值問題的古老算法，1847年由柯西（Cauchy）提出。最速下降法的基本原理由第二章優化設計的數學基礎可知，梯度方向是函數增加最快的方向，負梯度方向是函數下降最快的方向，所以最速下降法以負梯度方向為搜索方向，每次迭代都沿著負梯度方向進行一維搜索，直到滿足精度要求為止。因此，最速下降法又稱為梯度法。由公式（4.2）可知，若某次選代中己取得點，從該點出發，取負梯度方向為搜索方向。則最速下降法的迭代公式為 （4.3）當第次的迭代初始點和搜索方向已經確定的情況下，原目標函數成為關于步長的一維函數。即最優步長可以利用一維搜索的方法求得根據一元函數極值的必要條件和多元復合函數的求導公式，得或寫成 由此

6、可知，在最速下降法中相鄰兩個搜索方向互相正交。也就是說在用最速下降法迭代求優的過程中，走的是一條曲折的路線，該次搜索方向與前一次搜索方向垂直，形成“之”字形的鋸齒現象，如圖4.1所示。最速下降法剛開始搜索步長比較大，愈靠近極值點其步長愈小，收斂速度愈來愈慢。特別是對于二維二次目標函數的等值線是較扁的橢圓時，這種缺陷更加明顯。因此所謂最速下降是指目標函數在迭代點附近出現的局部性質，從迭代過程的全局來看，負梯度方向并非是目標函數的最快搜索方向。 圖4.1最速下降法的搜索路徑此外，最速下降法的迭代公式也可以寫成下面的形式 （4.4）將其與式4.3相比較，可知，此處等于4.3式中步長除以函數在點導數的

7、模，而此時的搜索方向也不再是個單位向量。最速下降法的迭代過程） 給定初始點，收斂精度，并令計算次數；） 計算點的梯度及梯度的模，并令） 判斷是否滿足精度指標；若滿足，為最優點，迭代停止，輸出最優解和，否則進行下一步計算；） 以為出發點，沿進行一維搜索，求能使函數值下降最多的步長，即） 令，轉到步驟2)。最速下降法的程序框圖如圖4.2所示。開始輸入 ，計算 及搜索方向一維搜索求最優步長 結束4.2最速下降法的程序框圖例題4.1 用最速下降法求目標函數的極小值，設初始點，計算精度。解 （）計算初始點處目標函數的梯度和梯度的模（）由于，不滿足精度指標，轉下一步計算。（）確定搜索方向（）計算新的迭代點

8、由公式（4.2）可得代入目標函數 沿方向進行一維搜索（或對求導，并令其為零）令，求得最優步長。（）計算新迭代點（）計算新迭代點的梯度及梯度的模因已滿足精度要求，停止迭代，得最優解為，可見，對于目標函數的等值線為圓的情況，只要一次迭代就能達到極小值點。這是因為圓周上任意一點的負梯度方向總是指向圓心的，如圖4.3所示。圖4.3例題4.1目標函數極小值的搜索過程通過上面的分析可知最速下降法具有以下特點：（1）理論明確，程序簡單，對初始點要求不嚴格，每次迭代所需的計算量和存儲量也較小，適用于計算機計算。（2）對一般函數而言，最速下降法的收斂速度并不快，因為最速下降方向僅僅是指某點的一個局部性質。（3）

9、最速下降法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，在遠離極小點時逼近速度較快，而在接近極小點時逼近速度較慢。（4）最速下降法的收斂速度與目標函數的性質以及初始點的選擇密切相關。對于等值線(面)為同心圓（球）的目標函數，一次搜索即可達到極小點。若目標函數為二次函數，等值線為橢圓，當初始點選在長軸或短軸上時，一次搜索也可達到極小值點。最速下降法的收斂速度和變量的尺度關系很大，這一點可從最速下降法收斂速度的估計式上看出來。在適當條件下，有 式中 的海賽矩陣最大特征值上界； 其最小特征值下界。當相鄰兩個迭代點之間滿足上式時（右邊的系數為小于等于1的正的常數），我們稱相應的迭代方法

10、是具有線性收斂速度的迭代法。因此，最速下降法是具有線性收斂速度的選代法。鑒于應用最速下降法可以使目標函數在開頭幾步下降很快，所以它可與其它無約束優化方法配合使用。即在開始階段用梯度法求得一個較優的初始點，然后用其它收斂快的方法繼續尋找極小點。42牛頓法牛頓法是根據目標函數的等值線在極值點附近為同心橢圓族的特點，在極值點鄰域內用一個二次函數來近似代替原目標函數，并將的極小值點作為對目標函數求優的下一個迭代點，經多次迭代，使之逼近原目標函數的極小值點。牛頓法的基本原理設目標函數是連續二階可微的，將函數在點按泰勒級數展開，并保留到二次項，得此式是個二次函數，設為的極小值點，則即 （4.5）這就是多元

11、函數求極值的牛頓法迭代公式。式中取稱為牛頓方向，為常數。式中沒有步長，或者可以看成步長恒等于1，所以牛頓法是一種定步長的迭代。例題4.4 用牛頓法求目標函數的極小值。解 （）取初始點（）計算梯度、二階偏導數矩陣及其逆矩陣（）計算新的迭代點經過一次迭代即可求得極小值點，函數極小值。 阻尼牛頓法由以上的兩個例題可以看出，對于二次函數，用牛頓法迭代一次即可得到最優點；對于非二次函數，若函數的迭代點已進入極小點的鄰域，則其收斂速度也是很快的。但是從牛頓法迭代公式的推導可以看出，迭代點是由近似二次函數的極值條件確定的，該點可能是極小值點，也可能是的極大值點。因此在用牛頓法迭代時，可能會出現函數上升的現象

12、，即，使迭代不能收斂于最優點。例如上例中若取初始點，第一次迭代點的函數值就增大。這表明牛頓法不能保證函數值穩定地下降，在嚴重的情況下甚至不能收斂而導致計算失敗。可見，牛頓法對初始點的要求是比較苛刻的，所選取的初始點離極小值點不能太遠。而在極小值點位置未知的情況下，上述要求很難達到。為了消除牛頓法的上述這些弊病，需要對其做一些修改。將牛頓法定步長的迭代，改為變步長的迭代，引入步長，在的牛頓方向進行一維搜索，保證每次迭代點的函數值都是下降的。這種方法稱為阻尼牛頓法，其迭代公式為 （4.6）式中，為牛頓方向的最優步長。這種方法對初始點的選取不再苛刻，從而提高了牛頓法的可靠度。但采用阻尼牛頓法，每次迭

13、代都要進行一維搜索，使收斂速度大大降低。例如，對于例4.6所示的目標函數，取同樣的初始點，采用阻尼牛頓法進行迭代，達到同樣的精度，要經過25次的迭代，越靠近極小值點收斂速度越慢，使牛頓法收斂速度快的優勢損失殆盡。阻尼牛頓法的迭代過程：阻尼牛頓法的計算步驟如下：）給定初始點，收斂精度，并令計算次數；）計算點的梯度和梯度的模；）判斷是否滿足精度指標；若滿足，為最優點，迭代停止，輸出最優解和，否則進行下一步計算；5）計算點的牛頓方向6）以為出發點，沿進行一維搜索，求能使函數值下降最多的步長，即令，轉到步驟2)。阻尼牛頓法的程序框圖如圖4.7所示：開始輸入 ，計算 及其一維搜索求最優步長 結束計算 點的牛頓方向 圖表 Error! No text of specified style in document.1圖4.6阻尼牛頓法的程序框圖4.7阻尼牛頓法的程序框圖牛頓法的總結牛頓法和阻尼牛頓法統稱為牛頓型方法。這類方法的最大優點是收斂速度快。也就是說，它的迭代次數相對其他