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

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

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

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

4、+口加(K)(k=0,1,2,)(4.2)(K)在上式中，d是第是k+1次搜索或迭代方向，稱為搜索方向(迭代方向)。由上面的迭代公式可以看出，采用數(shù)值法進(jìn)行迭代求優(yōu)時，需要確定初始點(diǎn)X(k)、搜索方向d(k)和迭代步長”k，稱為優(yōu)化方法迭代算法的三要素。第三章我們已經(jīng)討論了如何在搜索方向d(k)上確定最優(yōu)步長ak的方法，本章我們將討論如何確定搜索方向(k)d。最常用的數(shù)值方法是搜索方法，其基本思想如下圖所示:無約束優(yōu)化方法可以分為兩類。一類是通過計(jì)算目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)值確定搜索方向的方法，稱為間接法，如最速下降法、牛頓法、變尺度法和共食梯度法。另一類是直接利用目標(biāo)函數(shù)值確定搜索方向的方法

5、，稱為直接法，如坐標(biāo)輪換法、鮑威爾法和單形替換法。各種無約束優(yōu)化方法的區(qū)別在于確定其搜索方向0d的方法不同。4.1最速下降法最速下降法是一個求解極值問題的古老算法，1847年由柯西(Cauchy)提出。4.1.1 最速下降法的基本原理由第二章優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ)可知，梯度方向是函數(shù)增加最快的方向，負(fù)梯度方向是函數(shù)下降最快的方向，所以最速下降法以負(fù)梯度方向?yàn)樗阉鞣较?，每次迭代都沿著?fù)梯度方向進(jìn)行一維搜索，直到滿足精度要求為止。因此，最速下降法又稱為梯度法。由公式(4.2)X(K1)=X(K)=Kd(K)(k=0,1,2,)可知，若某次選代中己取得點(diǎn)X(k),從該點(diǎn)出發(fā)，取負(fù)梯度方向?yàn)樗阉鞣较?。則最

6、速下降法的迭代公式為X(Kd)=X(K)-：Kf(X(k)'|f(X(k)|(k=0,1,2,)(4.3)當(dāng)?shù)趉次的迭代初始點(diǎn)X的和搜索方向d(k)已經(jīng)確定的情況下，原目標(biāo)函數(shù)成為關(guān)于步長«的一維函數(shù)。即(：)=f(X(K):S(K)最優(yōu)步長«K可以利用一維搜索的方法求得min(：)=f(X(k1)=f(X(K)二kd(k)=minf(X(K):d(k)ota根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)的求導(dǎo)公式，得T(：)-'f(X(K)：d(k)”(X(K)=0”(X(K1)一f(X(K)=0或?qū)懗蒬(K1)Td(k)=0由此可知，在最速下降法中相鄰兩個搜索

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

8、等于4.3式中步長除以函數(shù)在X(K)點(diǎn)導(dǎo)數(shù)的模|f(X(k)|,而此時的搜索方向d(k)=Vf(X(k)也不再是個單位向量。4.1.2 最速下降法的迭代過程1) 給定初始點(diǎn)X(0),收斂精度J并令計(jì)算次數(shù)ku0;2) 計(jì)算X-點(diǎn)的梯度$f(X(K)及梯度的模|Vf(X(k)|,并令d(k)_"(X(k)h(X(k)|3) )判斷是否滿足精度指標(biāo)|Vf(X(k)|<ax若滿足，X(k)為最優(yōu)點(diǎn)，迭代停止,輸出最優(yōu)解X*=X(k、Df(X*)=f(X(k),否則進(jìn)行下一步計(jì)算；4) 以X為出發(fā)點(diǎn)，沿d(k)進(jìn)行一維搜索，求能使函數(shù)值下降最多的步長口即minf(X(k)：d的);f(

9、X(k)：Kd的)5) 令X(k+)=X(k)+o(Kd(k),k=k+1,轉(zhuǎn)到步驟2)。最速下降法的程序框圖如圖4.2所示。4.2最速下降法的程序框圖例題4.1用最速下降法求目標(biāo)函數(shù)f(X)=(%-1)2+(x2-1)2的極小值，設(shè)初始點(diǎn)X(0)=00T,計(jì)算精度8=10立。解(1)計(jì)算初始點(diǎn)X處目標(biāo)函數(shù)的梯度和梯度的模汗(X)Vf(X-)J二四一1)-2-X)匕(X2-1)1-2J一改2一|"f(X(0)-2.2(2)由于|Vf(X(0)|=2頁名，不滿足精度指標(biāo)，轉(zhuǎn)下一步計(jì)算。(3)確定搜索方向d(0)士Vf(X(0)_1-2_72vf(x(0)|"272，2-11(

10、4)計(jì)算新的迭代點(diǎn)由公式(4.2)可得1X=x(0)d(0)=00一一我一、一rr,9代入目標(biāo)函數(shù)f(X(1)=(-1)2(_-1)22.2V2=>/21a沿d的方向進(jìn)行一維搜索(或?qū)们髮?dǎo)，并令其為零)用(二一1)一2一(二一1)d：2222令3=0,d：(5)計(jì)算新迭代點(diǎn)2")=0_2(X2-1)_0(6)計(jì)算新迭代點(diǎn)的梯度及梯度的?！?X(1)二pf(X)=0名因已滿足精度要求，停止迭代，得最優(yōu)解為*11I*X=i,f(X)=0_1可見，對于目標(biāo)函數(shù)的等值線為圓的情況，只要一次迭代就能達(dá)到極小值點(diǎn)這是因?yàn)閳A周上任意一點(diǎn)的負(fù)梯度方向總是指向圓心的，如圖4.3所示。圖4.3例

11、題4.1目標(biāo)函數(shù)極小值的搜索過程通過上面的分析可知最速下降法具有以下特點(diǎn)：(1)理論明確，程序簡單，對初始點(diǎn)要求不嚴(yán)格，每次迭代所需的計(jì)算量和存儲量也較小，適用于計(jì)算機(jī)計(jì)算。(2)對一般函數(shù)而言，最速下降法的收斂速度并不快，因?yàn)樽钏傧陆捣较騼H僅是指某點(diǎn)的一個局部性質(zhì)。(3)最速下降法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，在遠(yuǎn)離極小點(diǎn)時逼近速度較快，而在接近極小點(diǎn)時逼近速度較慢。(4)最速下降法的收斂速度與目標(biāo)函數(shù)的性質(zhì)以及初始點(diǎn)的選擇密切相關(guān)。對于等值線(面)為同心圓(球)的目標(biāo)函數(shù)，一次搜索即可達(dá)到極小點(diǎn)。若目標(biāo)函數(shù)為二次函數(shù)，等值線為橢圓，當(dāng)初始點(diǎn)選在長軸或短軸上時

12、，一次搜索也可達(dá)到極小值點(diǎn)。最速下降法的收斂速度和變量的尺度關(guān)系很大，這一點(diǎn)可從最速下降法收斂速度的估計(jì)式上看出來。在適當(dāng)條件下，有(一勒八門式中的海賽矩陣最大特征值上界;其最小特征值下界。當(dāng)相鄰兩個迭代點(diǎn)之間滿足上式時(右邊的系數(shù)為小于等于1的正的常數(shù))，我們稱相應(yīng)的迭代方法是具有線性收斂速度的迭代法。因此，最速下降法是具有線性收斂速度的選代法。鑒于應(yīng)用最速下降法可以使目標(biāo)函數(shù)在開頭幾步下降很快，所以它可與其它無約束優(yōu)化方法配合使用。即在開始階段用梯度法求得一個較優(yōu)的初始點(diǎn)，然后用其它收斂快的方法繼續(xù)尋找極小點(diǎn)。4.2牛頓法一.一，.*牛頓法是根據(jù)目標(biāo)函數(shù)的等值線在極值點(diǎn)附近為同心橢圓族的特

13、點(diǎn)，在極值點(diǎn)X鄰域內(nèi)用一個二次函數(shù)中(X)來近似代替原目標(biāo)函數(shù)f(X),并將平(X)的極小值點(diǎn)作為對目標(biāo)函數(shù)f(X)求優(yōu)的下一個迭代點(diǎn)，經(jīng)多次迭代，使之逼近原目標(biāo)函數(shù)f(X)的極小值點(diǎn)。4.2.1 牛頓法的基本原理設(shè)目標(biāo)函數(shù)是連續(xù)二階可微的，將函數(shù)在X(k)點(diǎn)按泰勒級數(shù)展開，并保留到二次項(xiàng)，得f(X)：(X)=f(X(K)f(X(K)T(X-X(K)：(X-X(K)2f(X(K)(X-X(K)此式是個二次函數(shù)，設(shè)X(k卻為平(X)的極小值點(diǎn)，則'(X(k1)=0即'f(X(k),2f(X(k)(X(k-X(k)=0X(K")=X(K)-2f(X(K)Tvf(X(K)(

14、k=0,1,2；)(4.5)_這就是多元函數(shù)求極值的牛頓法迭代公式。式中取d(k)=_V2f(X(K),Vf(X(K)稱為牛頓方向，為常數(shù)。式中沒有步長尊k,或者可以看成步長恒等于1,所以牛頓法是一種定步長的迭代。例題4.4用牛頓法求目標(biāo)函數(shù)f(X)=x2+25x2的極小值。解(1)取初始點(diǎn)X(0)=22T(2)計(jì)算梯度、二階偏導(dǎo)數(shù)矩陣及其逆矩陣f(X(0)=520；=l40；22'、f(X)=015012f(X),=一121500(3)計(jì)算新的迭代點(diǎn)X=X(0)一“2f(X)、f(X)=；250經(jīng)過一次迭代即可求得極小值點(diǎn)X=00T,函數(shù)極小值f(X)=0。4.2.2阻尼牛頓法由以上

15、的兩個例題可以看出，對于二次函數(shù)，用牛頓法迭代一次即可得到最優(yōu)點(diǎn)；對于非二次函數(shù)，若函數(shù)的迭代點(diǎn)已進(jìn)入極小點(diǎn)的鄰域，則其收斂速度也是很快的。但是從牛頓法迭代公式的推導(dǎo)可以看出，迭代點(diǎn)是由近似二次函數(shù)中(X)的極值條件確定的，該點(diǎn)可能是9(X)極小值點(diǎn)，也可能是中(X)的極大值點(diǎn)。因此在用牛頓法迭代時，可能會出現(xiàn)函數(shù)上升的現(xiàn)象，即f(X(k*)Af(X(k),使迭代不能收斂于最優(yōu)點(diǎn)。例如上例中若取初始點(diǎn)X(0)=01T,第一次迭代點(diǎn)的函數(shù)值就增大。這表明牛頓法不能保證函數(shù)值穩(wěn)定地下降，在嚴(yán)重的情況下甚至不能收斂而導(dǎo)致計(jì)算失敗?？梢?，牛頓法對初始點(diǎn)的要求是比較苛刻的，所選取的初始點(diǎn)離極小值點(diǎn)不能太

16、遠(yuǎn)。而在極小值點(diǎn)位置未知的情況下，上述要求很難達(dá)到。為了消除牛頓法的上述這些弊病，需要對其做一些修改。將牛頓法定步長的迭代，(k)改為變步長的迭代，引入步長1a，在X的牛頓方向進(jìn)行一維搜索，保證每次迭代點(diǎn)的函數(shù)值都是下降的。這種方法稱為阻尼牛頓法，其迭代公式為X(K1)=X(K)-二k2f(X(K)-1'f(X(K)(k=0,1,2,)(4.6)式中，ak為牛頓方向的最優(yōu)步長。這種方法對初始點(diǎn)的選取不再苛刻，從而提高了牛頓法的可靠度。但采用阻尼牛頓法，每次迭代都要進(jìn)行一維搜索，使收斂速度大大降低。例如，對于例4.6所示的目標(biāo)函數(shù)，取同樣的初始點(diǎn)，采用阻尼牛頓法進(jìn)行迭代，達(dá)到同樣的精度，

17、要經(jīng)過25次的迭代，越靠近極小值點(diǎn)收斂速度越慢，使牛頓法收斂速度快的優(yōu)勢損失殆盡。阻尼牛頓法的迭代過程：阻尼牛頓法的計(jì)算步驟如下：1)給定初始點(diǎn)X(0),收斂精度£,并令計(jì)算次數(shù)ku0；2)計(jì)算X(kL的梯度Vf(X(K)和梯度的模|Vf(X(k)|;3)判斷是否滿足精度指標(biāo)|pf(X(k)|;若滿足，X(k)為最優(yōu)點(diǎn)，迭代停止，輸出最優(yōu)解X*=X(k)和f(X*):f(X(k),否則進(jìn)行下一步計(jì)算；5)計(jì)算X(k)點(diǎn)的牛頓方向d(k)d的2f(X(K)Af(X(K)6)以X的為出發(fā)點(diǎn)，沿d(k)進(jìn)行一維搜索，求能使函數(shù)值下降最多的步長口即minf(X(k)：d的);f(X(k);Kd的)Ct令X=X(k)+口Kd(k),k=k+l,轉(zhuǎn)到步驟2)。阻尼牛頓法的程序框圖如圖4.7所示:4.7