【正文】 第四章 無約束優(yōu)化方法 167。 41 最速下降法（梯度法） 167。 42 牛頓類方法 167。 43 變尺度法 167。 44 共軛方向法 167。 45 鮑威爾方法 167。 46 其它方法（如坐標(biāo)輪換法、單純形法） 第 1章所列舉的機(jī)械優(yōu)化設(shè)計(jì)問題 ， 都是在一定的限制條件下追求某一指標(biāo)為最小 ， 它們都屬于約束優(yōu)化問題 。 工程問題大都如此 。 為什么要研究無約束優(yōu)化問題 ? （ 1） 有些實(shí)際問題 ， 其數(shù)學(xué)模型本身就是一個(gè)無約束優(yōu)化問題 。 （ 2） 通過熟悉它的解法可以為研究約束優(yōu)化問題打下良好的基礎(chǔ) 。 （ 3） 約束優(yōu)化問題的求解可以通過一系列無約束優(yōu)化方法來達(dá)到 。 所以無約束優(yōu)化問題的解法是優(yōu)化設(shè)計(jì)方法的基本組成部分 ， 也是優(yōu)化方法的基礎(chǔ) 。 （ 4） 對于多維無約束問題來說 ， 古典極值理論中令一階導(dǎo)數(shù)為零 ， 但要求二階可微 ， 且要判斷海賽矩陣為正定才能求得極小點(diǎn) ， 這種方法有理論意義 ，但無實(shí)用價(jià)值 。 和一維問題一樣 ， 若多元函數(shù) F(X)不可微 ， 亦無法求解 。 但古典極值理論是無約束優(yōu)化方法發(fā)展的基礎(chǔ) 。 目前已研究出很多種無約束優(yōu)化方法，它們的主要不同點(diǎn)在于 構(gòu)造搜索方向 上的差別。 m in ( ) nfR ?xx（ 1）間接法 —— 要使用導(dǎo)數(shù)，如梯度法、（阻尼）牛頓法、變尺度法、共軛梯度法等。 （ 2）直接法 —— 不使用導(dǎo)數(shù)信息，如坐標(biāo)輪換法、鮑威爾法單純形法等。 無約束優(yōu)化問題是： 12[] Tnx x x?x求 n維設(shè)計(jì)變量 ( ) m inf ?x使目標(biāo)函數(shù) 1 ( 0 , 1 , 2 , )k k kk sk?? ? ? ?xx搜索方向的構(gòu)成問題乃是無約束優(yōu)化方法的關(guān)鍵 。 用直接法尋找極小點(diǎn)時(shí)，不必求函數(shù)的導(dǎo)數(shù)，只要計(jì)算目標(biāo)函數(shù)值。這類方法較適用于解決變量個(gè)數(shù)較少的（ n ≤20）問題，一般情況下比間接法效率低。間接法除要計(jì)算目標(biāo)函數(shù)值外，還要計(jì)算目標(biāo)函數(shù)的梯度，有的還要計(jì)算其海賽矩陣。 41 梯度法 1 ( 0 , 1 , 2 , )k k kk sk?? ? ? ?xx1 ( ) ( 0 , 1 , 2 , )k k kka f k? ? ? ? ?x x x 基本思想 ：函數(shù)的負(fù)梯度方向是函數(shù)值在該點(diǎn)下降最快的方向。將 n維問題轉(zhuǎn)化為一系列沿負(fù)梯度方向用一維搜索方法尋優(yōu)的問題，利用負(fù)梯度作為搜索方向，故稱最速下降法或梯度法。 ()f?? x 搜索方向 s取該點(diǎn)的負(fù)梯度方向 (最速下降方向 ) ，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快 。 為了使目標(biāo)函數(shù)值沿搜索方向 能夠獲得最大的下降值 ， 其步長因子 應(yīng)取一維搜索的最佳步長 。 即有 ()kf?? xk?1( ) [ ( ) ] m in [ ( ) ]m in ( )k k k k kkk aaf f a f f a f??? ? ? ? ? ? ??x x x x x 根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得 ? ?39。( ) [ ( ) ] ( ) 0Tk k kkf f f? ? ?? ? ? ? ? ? ?x x x1[ ( ) ] ( ) 0k T kff?? ? ?xx1( ) 0k T kss? ? 在最速下降法中，相鄰兩個(gè)迭代點(diǎn)上的函數(shù)梯度相互垂直。而搜索方向就是負(fù)梯度方向，因此相鄰兩個(gè)搜索方向互相垂直。這就是說在迭代點(diǎn)向函數(shù)極小點(diǎn)靠近的過程，走的是曲折的路線。形成 “ 之 ” 字形的鋸齒現(xiàn)象，而且越接近極小點(diǎn)鋸齒越細(xì)。 圖 41 最速下降法的搜索路徑 方法特點(diǎn) （ 1）初始點(diǎn)可任選，每次迭代計(jì)算量小，存儲(chǔ)量少，程序簡短。即使從一個(gè)不好的初始點(diǎn)出發(fā)，開始的幾步迭代，目標(biāo)函數(shù)值下降很快，然后慢慢逼近局部極小點(diǎn)。 （ 2）任意相鄰兩點(diǎn)的搜索方向是正交的，它的迭代路徑為繞道逼近極小點(diǎn)。當(dāng)?shù)c(diǎn)接近極小點(diǎn)時(shí)，步長變得很小，越走越慢。 開始給定結(jié)束0, ?x()kkf? ??dx1: m i n ( )k k kkkkkf????????x x dxd1kk????xx*1 k ??xx否是1kk ??0k ?sk 00102( ) 10 42 4()50 100xfxfx??? ??? ? ??? ??????xx沿負(fù)梯度方向進(jìn)行一維搜索 ， 有 01 0 00024()2 10 0f??????? ? ? ??????x x x0? 為一維搜索最佳步長，應(yīng)滿足極值必要條件 ? ?1 2 2( ) m i n ( 2 4 ) 25 ( 2 100 ) m i n ( )f ?? ? ? ? ?? ? ? ? ?x例 4－ 1 求目標(biāo)函數(shù) 的極小點(diǎn) 。 解 取初始點(diǎn) 則初始點(diǎn)處函數(shù)值及梯度分別為 0 [ 2 , 2 ]T?x2212( ) 2 5f x x??x0039。( ) 8 ( 2 4 ) 5 0 0 0 ( 2 1 0 0 ) 0? ? ? ?? ? ? ? ? ?算出一維搜索最佳步長 0626 0 .0 2 0 0 3 0 7 23 1 2 5 2? ??第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值 012024 9 8772 100 7 178 5 10?? ?? ?????? ????? ???? ??x1( ) 3 . 6 8 6 1 6 4f ?x繼續(xù)作下去，經(jīng) 10次迭代后，得到最優(yōu)解 ? ?00 T? ?x( ) 0f ? ?x 這個(gè)問題的目標(biāo)函數(shù)的等值線為一簇橢圓 ,迭代點(diǎn)從 走的是一段鋸齒形路線，見圖 42。 0x1 圖 42 將上例中目標(biāo)函數(shù) 引入變換 2212( ) 2 5f x x??x221 2 1 2( , )y y y y? ??其等值線由橢圓變成一簇同心圓。 仍從 即 出發(fā)進(jìn)行最速下降法尋優(yōu)。此時(shí)： 0 [ 2 , 2 ]T?x 0 [ 2 ,1 0 ]T?y00102( ) 1042 4()2 20yy????? ??? ? ??? ?????? yyy沿負(fù)梯度方向進(jìn)行一維搜索： 則函數(shù) f(X)變?yōu)椋? y1=x1, y2=5x2 1 0 00000()242410 2022 20?????? ? ????? ? ? ??? ??? ? ? ??? ? ? ? ??y y yβ 為一維搜索最佳步長，可由極值條件： 1 0 022( ) m in [ ( ) ] m in ( )( ) ( 2 4 ) ( 10 20 )??? ? ? ? ?? ? ?? ? ? ? ?? ? ? ? ?y y y0( ) 0????由 026 52? ??從而算得一步計(jì)算后設(shè)計(jì)點(diǎn)的位置及其目標(biāo)函數(shù)： 010124 010 20 0( ) 0?????? ?????? ??? ?????yy經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。 這是因?yàn)榻?jīng)過尺度變換： 11225yxyx??等值線由橢圓變成圓。 梯度法的特點(diǎn) ? （ 1）理論明確，程序簡單，對初始點(diǎn)要求不嚴(yán)格。 ? （ 2）對一般函數(shù)而言，梯度法的收斂速度并不快，因?yàn)樽钏傧陆捣较騼H僅是指某點(diǎn)的一個(gè) 局部性質(zhì) 。 ? （ 3）梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈 鋸齒 狀，在遠(yuǎn)離極小點(diǎn)時(shí)逼近速度較快，而在接近極小點(diǎn)時(shí)逼近速度較慢。 ? （ 4）梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)密切相關(guān)。對于等值線 (面 )為同心圓（球）的目標(biāo)函數(shù)，一次搜索即可達(dá)到極小點(diǎn)。 42 牛頓法及其改進(jìn) 2( ) ( ) ( ) ( ) ( )1( ) ( ) ( )2k k T kk T k kf f ff?? ? ? ? ?? ? ? ?x x x x x xx x x x x設(shè) 為 的極小點(diǎn) 1k?x ()? x1( ) 0k? ???x基本思想 ： 在 xk鄰域內(nèi)用一個(gè)二次函數(shù) 來近似代替原目標(biāo)函數(shù)，并將 的極小點(diǎn)作為對目標(biāo)函數(shù) 求優(yōu)的下一個(gè)迭代點(diǎn) 。經(jīng)多次迭代，使之逼近目標(biāo)函數(shù) 的極小點(diǎn)。 牛頓法是求函數(shù)極值的最古老算法之一。 ()? x()? x ()f x1k?x()f x21( ) ( ) ( ) 0k k k kff ?? ? ? ? ?x x x x1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kf f k??? ? ? ? ?x x x x這就是多元函數(shù)求極值的牛頓法迭代公式。 對于二次函數(shù) ， 海賽矩陣 H是一個(gè)常矩陣，其中各元素均為常數(shù)。因此，無論從任何點(diǎn)出發(fā)，只需一步就可找到極小點(diǎn)。 例 4－ 2 求目標(biāo)函數(shù) 的極小點(diǎn) 。 解 取初始點(diǎn) 2212( ) 2 5f x x??x0 [ 2 , 2 ]T?x1 0 2 0 1 0102 4 02( ) ( )12 10 0 0050ff?????? ? ? ? ? ?? ? ? ? ? ? ??? ??? ? ? ? ? ???? ? ? ? ? ???????x x x x? ?00? ?x( ) 0f ? ?x 從牛頓法迭代公式的推演中可以看到，迭代點(diǎn)的位置是按照極值條件確定的，其中并未含有沿下降方向搜尋的概念。因此對于非二次函數(shù)，如果采用上述牛頓迭代公式，有時(shí)會(huì)使函數(shù)值上升 。 阻尼牛頓法 1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k k k kkks f f k????? ? ? ? ? ? ?x x x x xk? 阻尼因子 ， 沿牛頓方向進(jìn)行一維搜索的最佳步長，由下式求得：