無約束優(yōu)化方法(最速下降法-牛頓法)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第四章 無約束優(yōu)化方法 最速下降法，牛頓型方法 概述 在求解目標函數(shù)的極小值的過程中，若對設(shè)計變量的取值范圍不加限制，則稱這種最優(yōu)化問題為無約束優(yōu)化問題。盡管對于機械的優(yōu)化設(shè)計問題，多數(shù)是有約束的，無約束最優(yōu)化方法仍然是最優(yōu)化設(shè)計的基本組成部分。因為約束最優(yōu)化問題可以通過對約束條件的處理，轉(zhuǎn)化為無約束最優(yōu)化問題來求解。為什么要研究無約束優(yōu)化問題? （1）有些實際問題，其數(shù)學(xué)模型本身就是一個無約束優(yōu)化問題。 （2）通過熟悉它的解法可以為研究約束優(yōu)化問題打下良好的基礎(chǔ)。 （3）約束優(yōu)化問題的求解可以通過一系列無約束優(yōu)化方法

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

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

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

5、速下降法最速下降法是一個求解極值問題的古老算法，1847年由柯西（Cauchy）提出。4.1.1最速下降法的基本原理由第二章優(yōu)化設(shè)計的數(shù)學(xué)基礎(chǔ)可知，梯度方向是函數(shù)增加最快的方向，負梯度方向是函數(shù)下降最快的方向，所以最速下降法以負梯度方向為搜索方向，每次迭代都沿著負梯度方向進行一維搜索，直到滿足精度要求為止。因此，最速下降法又稱為梯度法。由公式（4.2）可知，若某次選代中己取得點，從該點出發(fā)，取負梯度方向為搜索方向。則最速下降法的迭代公式為 （4.3）當(dāng)?shù)诖蔚牡跏键c和搜索方向已經(jīng)確定的情況下，原目標函數(shù)成為關(guān)于步長的一維函數(shù)。即最優(yōu)步長可以利用一維搜索的方法求得根據(jù)一元函數(shù)極值的必要條件和多

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

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

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

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

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

11、是個二次函數(shù)，設(shè)為的極小值點，則即 （4.5）這就是多元函數(shù)求極值的牛頓法迭代公式。式中取稱為牛頓方向，為常數(shù)。式中沒有步長，或者可以看成步長恒等于1，所以牛頓法是一種定步長的迭代。例題4.4 用牛頓法求目標函數(shù)的極小值。解 （）取初始點（）計算梯度、二階偏導(dǎo)數(shù)矩陣及其逆矩陣（）計算新的迭代點經(jīng)過一次迭代即可求得極小值點，函數(shù)極小值。4.2.2 阻尼牛頓法由以上的兩個例題可以看出，對于二次函數(shù)，用牛頓法迭代一次即可得到最優(yōu)點；對于非二次函數(shù)，若函數(shù)的迭代點已進入極小點的鄰域，則其收斂速度也是很快的。但是從牛頓法迭代公式的推導(dǎo)可以看出，迭代點是由近似二次函數(shù)的極值條件確定的，該點可能是極小值點，

12、也可能是的極大值點。因此在用牛頓法迭代時，可能會出現(xiàn)函數(shù)上升的現(xiàn)象，即，使迭代不能收斂于最優(yōu)點。例如上例中若取初始點，第一次迭代點的函數(shù)值就增大。這表明牛頓法不能保證函數(shù)值穩(wěn)定地下降，在嚴重的情況下甚至不能收斂而導(dǎo)致計算失敗。可見，牛頓法對初始點的要求是比較苛刻的，所選取的初始點離極小值點不能太遠。而在極小值點位置未知的情況下，上述要求很難達到。為了消除牛頓法的上述這些弊病，需要對其做一些修改。將牛頓法定步長的迭代，改為變步長的迭代，引入步長，在的牛頓方向進行一維搜索，保證每次迭代點的函數(shù)值都是下降的。這種方法稱為阻尼牛頓法，其迭代公式為 （4.6）式中，為牛頓方向的最優(yōu)步長。這種方法對初始點

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