1、第四章 無(wú)約束優(yōu)化方法 最速下降法，牛頓型方法 概述 在求解目標(biāo)函數(shù)的極小值的過(guò)程中，若對(duì)設(shè)計(jì)變量的取值范圍不加限制，則稱(chēng)這種最優(yōu)化問(wèn)題為無(wú)約束優(yōu)化問(wèn)題。盡管對(duì)于機(jī)械的優(yōu)化設(shè)計(jì)問(wèn)題，多數(shù)是有約束的，無(wú)約束最優(yōu)化方法仍然是最優(yōu)化設(shè)計(jì)的基本組成部分。因?yàn)榧s束最優(yōu)化問(wèn)題可以通過(guò)對(duì)約束條件的處理，轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題來(lái)求解。為什么要研究無(wú)約束優(yōu)化問(wèn)題? （1）有些實(shí)際問(wèn)題，其數(shù)學(xué)模型本身就是一個(gè)無(wú)約束優(yōu)化問(wèn)題。 （2）通過(guò)熟悉它的解法可以為研究約束優(yōu)化問(wèn)題打下良好的基礎(chǔ)。 （3）約束優(yōu)化問(wèn)題的求解可以通過(guò)一系列無(wú)約束優(yōu)化方法來(lái)達(dá)到。 所以無(wú)

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

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

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

5、解極值問(wèn)題的古老算法，1847年由柯西（Cauchy）提出。最速下降法的基本原理由第二章優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ)可知，梯度方向是函數(shù)增加最快的方向，負(fù)梯度方向是函數(shù)下降最快的方向，所以最速下降法以負(fù)梯度方向?yàn)樗阉鞣较颍看蔚佳刂?fù)梯度方向進(jìn)行一維搜索，直到滿足精度要求為止。因此，最速下降法又稱(chēng)為梯度法。由公式（4.2）可知，若某次選代中己取得點(diǎn)，從該點(diǎn)出發(fā)，取負(fù)梯度方向?yàn)樗阉鞣较颉t最速下降法的迭代公式為 （4.3）當(dāng)?shù)诖蔚牡跏键c(diǎn)和搜索方向已經(jīng)確定的情況下，原目標(biāo)函數(shù)成為關(guān)于步長(zhǎng)的一維函數(shù)。即最優(yōu)步長(zhǎng)可以利用一維搜索的方法求得根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)的求導(dǎo)公式，得或?qū)懗?由此

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

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

8、由公式（4.2）可得代入目標(biāo)函數(shù) 沿方向進(jìn)行一維搜索（或?qū)η髮?dǎo)，并令其為零）令，求得最優(yōu)步長(zhǎng)。（）計(jì)算新迭代點(diǎn)（）計(jì)算新迭代點(diǎn)的梯度及梯度的模因已滿足精度要求，停止迭代，得最優(yōu)解為，可見(jiàn)，對(duì)于目標(biāo)函數(shù)的等值線為圓的情況，只要一次迭代就能達(dá)到極小值點(diǎn)。這是因?yàn)閳A周上任意一點(diǎn)的負(fù)梯度方向總是指向圓心的，如圖4.3所示。圖4.3例題4.1目標(biāo)函數(shù)極小值的搜索過(guò)程通過(guò)上面的分析可知最速下降法具有以下特點(diǎn)：（1）理論明確，程序簡(jiǎn)單，對(duì)初始點(diǎn)要求不嚴(yán)格，每次迭代所需的計(jì)算量和存儲(chǔ)量也較小，適用于計(jì)算機(jī)計(jì)算。（2）對(duì)一般函數(shù)而言，最速下降法的收斂速度并不快，因?yàn)樽钏傧陆捣较騼H僅是指某點(diǎn)的一個(gè)局部性質(zhì)。（3）

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

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

11、函數(shù)求極值的牛頓法迭代公式。式中取稱(chēng)為牛頓方向，為常數(shù)。式中沒(méi)有步長(zhǎng)，或者可以看成步長(zhǎng)恒等于1，所以牛頓法是一種定步長(zhǎng)的迭代。例題4.4 用牛頓法求目標(biāo)函數(shù)的極小值。解 （）取初始點(diǎn)（）計(jì)算梯度、二階偏導(dǎo)數(shù)矩陣及其逆矩陣（）計(jì)算新的迭代點(diǎn)經(jīng)過(guò)一次迭代即可求得極小值點(diǎn)，函數(shù)極小值。 阻尼牛頓法由以上的兩個(gè)例題可以看出，對(duì)于二次函數(shù)，用牛頓法迭代一次即可得到最優(yōu)點(diǎn)；對(duì)于非二次函數(shù)，若函數(shù)的迭代點(diǎn)已進(jìn)入極小點(diǎn)的鄰域，則其收斂速度也是很快的。但是從牛頓法迭代公式的推導(dǎo)可以看出，迭代點(diǎn)是由近似二次函數(shù)的極值條件確定的，該點(diǎn)可能是極小值點(diǎn)，也可能是的極大值點(diǎn)。因此在用牛頓法迭代時(shí)，可能會(huì)出現(xiàn)函數(shù)上升的現(xiàn)象

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

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