【正文】 行分析。式（621）的幾何意義是十分明顯的，即點(diǎn)處滿足該條件的方向與點(diǎn)目標(biāo)函數(shù)負(fù)梯度方向的夾角為銳角，與點(diǎn)所有有效約束梯度方向的夾角也為銳角。顯然，如果某點(diǎn)存在可行下降方向，那么該點(diǎn)就不會(huì)是極小點(diǎn)；另一方面，如果某點(diǎn)是極小點(diǎn)，則該點(diǎn)不存在可行下降方向。將目標(biāo)函數(shù)在處作一階泰勒展開(kāi)，若方向滿足 （620）則必是點(diǎn)的一個(gè)下降方向。從而，只要方向滿足式（619），即可保證是點(diǎn)的可行方向。若是點(diǎn)的任一可行方向，則對(duì)該點(diǎn)所有有效約束均有：， （618）其中代表在點(diǎn)所有有效約束下標(biāo)的集合，如圖614所示。顯而易見(jiàn)，所有等式約束都是有效約束。61 最優(yōu)性條件現(xiàn)考慮一般形式的非線性規(guī)劃數(shù)學(xué)模型：假設(shè)、和均具有一階連續(xù)偏導(dǎo)數(shù)，是非線性規(guī)劃的一個(gè)可行解。對(duì)極小化問(wèn)題來(lái)說(shuō)，除了要使目標(biāo)函數(shù)每次迭代都有所下降外，還必須要時(shí)刻注意解的可行性（某些算法除外），這就給優(yōu)化工作帶來(lái)了許多困難。帶有約束條件的極值問(wèn)題稱為約束極值問(wèn)題（也成為規(guī)劃問(wèn)題）。167。在以上的討論中，第一個(gè)尺度矩陣為單位矩陣（對(duì)稱正定陣），以后的尺度矩陣由式（617）逐步形成。[例612] 試用變尺度法（DFP）求的極小值，初始搜索點(diǎn)。通常取初始的尺度矩陣為單位矩陣，以后的尺度矩陣按式（617）逐步形成。如果是二次函數(shù)，則其海賽矩陣為常數(shù)，式+是精確的，對(duì)于任意兩點(diǎn)和其梯度之差為：即對(duì)于非二次函數(shù)，仿照二次函數(shù)的情形，要求其海賽矩陣逆陣的第次近似矩陣應(yīng)滿足： （611）式（611）就是所謂的擬牛頓條件。為避免計(jì)算二階導(dǎo)數(shù)矩陣及其逆矩陣，設(shè)法構(gòu)造另一個(gè)矩陣來(lái)逼近二階導(dǎo)數(shù)矩陣的逆矩陣。變尺度法最早由Davidon于1959年提出，后經(jīng)Fletcher和Powell二人改進(jìn)，因此變尺度法也被稱為DFP法。53變尺度法變尺度法（Variable Metric Algorithm）是近40年來(lái)發(fā)展起來(lái)的求解無(wú)約束極值問(wèn)題的一種有效方法。[例611] 試用牛頓法求的極小值。[例610] 試用牛頓法求的極小值。在這種情況下，常按下式選取搜索方向： （68）=lk （69）lk：lk） （610）按照這種方式求函數(shù)極小點(diǎn)的方法稱為牛頓法，式（68）所示的搜索方向稱為牛頓方向。如果不是二次函數(shù)，式（66）僅是一個(gè)近似表達(dá)式。若非線性目標(biāo)函數(shù)具有二階連續(xù)偏導(dǎo)，在為其極小點(diǎn)的某一近似，在這一點(diǎn)取的二階泰勒展開(kāi)，即：+ （66）則其梯度為：這一近似函數(shù)的極小點(diǎn)應(yīng)滿足：從而即 （67）如果是二次函數(shù)，則其海賽矩陣為常數(shù)，式（66）是精確的。52牛頓法利用必要條件來(lái)確定駐點(diǎn)的一個(gè)障礙是在求解聯(lián)立方程時(shí)存在困難。由上例可以看出，當(dāng)二次函數(shù)的等值線為同心橢圓時(shí)，采用梯度法其搜索路徑呈直角鋸齒狀；最初幾步函數(shù)值變化顯著，但是越接近最優(yōu)點(diǎn)，收斂的速度越不夠理想。由于負(fù)梯度方向的最速下降性和正梯度方向的最速上升性，人們很容易認(rèn)為梯度方向是最理想的搜索方向。第二次迭代：，第三次迭代：，第四次迭代：，第五次迭代：，第六次迭代：因此步，所以由于已經(jīng)很小，所以過(guò)程可以在這一點(diǎn)結(jié)束。2121圖613設(shè)，因有，所以有。[例69] 試用梯度法求的極大點(diǎn)。解：取初始近似點(diǎn)，el0 ==l0=ex2x1極小點(diǎn)圖612圖612展示了該例的迭代過(guò)程，即從經(jīng)過(guò)負(fù)梯度方向一步到達(dá)極小點(diǎn)。若具有二階連續(xù)偏導(dǎo)，在處將作泰勒展開(kāi)，即：ll +ll對(duì) l 求導(dǎo)并令其為零，則有最佳步長(zhǎng)lk =，可見(jiàn)最佳步長(zhǎng)不僅與梯度有關(guān)，而且與海賽矩陣有關(guān)。一般地，若e，則即為近似極小點(diǎn)；否則求步長(zhǎng) lk并計(jì)算=lk。2．基本步驟給定一個(gè)初始近似點(diǎn)及其精度e，若e，則即為近似極小點(diǎn)；若e，求步長(zhǎng)l0并計(jì)算=l0。由于采用負(fù)梯度方向，滿足該不等式的 l 總是存在的。為了得到下一個(gè)近似點(diǎn)，在選定搜索方向之后，還要確定步長(zhǎng) l 。由于=，當(dāng)與反向（即）時(shí)，取最小值。此時(shí)，若取l （65）就一定能使目標(biāo)函數(shù)得到改善?，F(xiàn)將在處作泰勒展開(kāi)，有：ll0（l）其中0（l）是 l 的高階無(wú)窮小。當(dāng)然，直接法也有其自身的長(zhǎng)處，那就是它的迭代過(guò)程簡(jiǎn)單，并能處理導(dǎo)數(shù)難以求得或根本不存在的函數(shù)極值問(wèn)題。5無(wú)約束極值問(wèn)題求解無(wú)約束極值問(wèn)題通常采用迭代法，迭代法可大體分為兩大類：一類要用到函數(shù)的一階導(dǎo)數(shù)和（或）二階導(dǎo)數(shù)，由于此種方法涉及函數(shù)的解析性質(zhì)，故稱為解析法；另一類在迭代過(guò)程中只用到函數(shù)的數(shù)值，而不要求函數(shù)的解析性質(zhì)，故稱為直接法。5%=1b1=a1=a=0b=20圖611a1=a1=a1=b1=因此，符合精度要求的近似極小點(diǎn)為，近似極小值為。解：，，，由于從一定的搜索區(qū)間出發(fā)所進(jìn)行的黃金分割搜索與斐波那契搜索在原理上是完全相同的，故在此省略一些計(jì)算細(xì)節(jié)，只將搜索過(guò)程用圖611加以展示。黃金分割法是一種等速對(duì)稱的搜索方法，每次試點(diǎn)均取在區(qū)間長(zhǎng)度的和處，見(jiàn)圖610。現(xiàn)將以上數(shù)列分為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)，可以證明這兩個(gè)數(shù)列收斂于同一個(gè)極限。因此，符合精度要求的近似極小點(diǎn)為，近似極小值為。由于，搜索區(qū)間可以進(jìn)一步從縮減為，如圖69所示。由于在新的區(qū)間內(nèi)，已經(jīng)存在一個(gè)已知的試點(diǎn)及其函數(shù)值，所以我們僅需再計(jì)算一個(gè)試點(diǎn)，上述過(guò)程如圖68所示。；由于，搜索區(qū)間可以從縮減為。為了進(jìn)行比較，在此給出函數(shù)的精確最優(yōu)解，最優(yōu)值。Fn2Fn1aba1b1Fn2Fn1圖67 [例66] 試用斐波那契法求函數(shù)的近似極小點(diǎn)和極小值。計(jì)算個(gè)函數(shù)值所能獲得的最大縮短率為，即計(jì)算個(gè)函數(shù)值可把原長(zhǎng)度為的區(qū)間縮短為： 例如計(jì)算12個(gè)函數(shù)值可把原長(zhǎng)度為的區(qū)間縮短為：若要想將區(qū)間長(zhǎng)度縮短為原長(zhǎng)度的d（0d1）倍，只要足夠大一定能使： （63）這里的 d 稱為區(qū)間縮減的相對(duì)精度?，F(xiàn)在要問(wèn)“計(jì)算函數(shù)值次，能把區(qū)間縮減到什么程度呢？”或者換句話講“計(jì)算函數(shù)值次，能把原來(lái)多大的區(qū)間縮減成單位區(qū)間呢？”如果用表示計(jì)算個(gè)函數(shù)值能縮短為單位區(qū)間的最大原區(qū)間長(zhǎng)度，因?yàn)椴挥?jì)算函數(shù)值或只計(jì)算1個(gè)函數(shù)值是無(wú)法將區(qū)間縮短的，所以顯然有，即只有原來(lái)的區(qū)間就是單位區(qū)間才行。若要繼續(xù)縮小搜索區(qū)間或，只需在區(qū)間內(nèi)再取一點(diǎn)算出其函數(shù)值并與或加以比較即可。（2），如圖66所示；此時(shí)極小點(diǎn)必在內(nèi)。41斐波那契法一維搜索過(guò)程是建立在一個(gè)被稱為斐波那契數(shù)序列基礎(chǔ)上的，斐波那契數(shù)序列是具有如下遞推關(guān)系的無(wú)窮序列： （）n012345678Fn112358132134斐波那契法成功地實(shí)現(xiàn)了單峰函數(shù)極值范圍的縮減。通常采用的準(zhǔn)則（e1，e2，e3，e4，e5是事先給定的充分小的正數(shù)）有：（1） 相繼兩次迭代的絕對(duì)誤差：e1 ，e2（2） 相繼兩次迭代的相對(duì)誤差：e3 ，e4（3） 目標(biāo)函數(shù)梯度的模充分?。篹5167。1020圖64一維搜索有一個(gè)非常重要的性質(zhì)，即在搜索方向上所得最優(yōu)點(diǎn)的梯度和搜索方向正交；這一性質(zhì)可表達(dá)成：()則有：其幾何意義如圖64所示。確定搜索方向是關(guān)鍵的一步，各種算法的區(qū)別主要在于確定搜索方向的方法不同。若從出發(fā)沿任何方向移動(dòng)都不能使目標(biāo)函數(shù)下降，則是一個(gè)局部極小點(diǎn)；若從出發(fā)至少存在一個(gè)方向能使目標(biāo)函數(shù)下降，則可選定某一下降方向，沿這一方向前進(jìn)一步，得到下一個(gè)點(diǎn)。3．下降算法若某種算法產(chǎn)生的解序列能使目標(biāo)函數(shù)逐步減少，那么就稱此算法為下降算法。32下降迭代算法1．基本思想給定一個(gè)初始估計(jì)解，然后按某種規(guī)則（即算法）找出一個(gè)比更好的解