非線性規(guī)劃(教案)

非線性規(guī)劃線性規(guī)劃及其擴(kuò)展問(wèn)題的約束條件和目標(biāo)函數(shù)都是關(guān)于決策變量的一次函數(shù)。雖然大量的實(shí)際問(wèn)題可以簡(jiǎn)化為線性規(guī)劃及其擴(kuò)展問(wèn)題來(lái)求解，但是還有相當(dāng)多的問(wèn)題很難用線性函數(shù)加以描述。如果目標(biāo)函數(shù)或約束條件中包含有非線性函數(shù)，就稱這樣的規(guī)劃問(wèn)題為非線性規(guī)劃問(wèn)題。由于人們對(duì)實(shí)際問(wèn)題解的精度要求越來(lái)越高，非線性規(guī)劃自20世紀(jì)70年代以來(lái)得到了長(zhǎng)足的發(fā)展；目前，已成為運(yùn)籌學(xué)的一個(gè)重要分支，在管理科學(xué)、最優(yōu)設(shè)計(jì)、系統(tǒng)控制等許多領(lǐng)域得到了廣泛的應(yīng)用。一般來(lái)講，非線性規(guī)劃問(wèn)題的求解要比線性規(guī)劃問(wèn)題的求解困難得多；而且也不象線性規(guī)劃問(wèn)題那樣具有一種通用的求解方法（單純形法）。非線性規(guī)劃沒(méi)有能夠適應(yīng)所有問(wèn)題的一般求解方法，各種方法都只能在其特定的范圍內(nèi)發(fā)揮作用。本章在簡(jiǎn)要介紹非線性規(guī)劃基本概念和一維搜索的基礎(chǔ)上，重點(diǎn)介紹無(wú)約束極值問(wèn)題和約束極值問(wèn)題的求解方法。§1非線性規(guī)劃的數(shù)學(xué)模型非線性規(guī)劃問(wèn)題[例1]某商店經(jīng)銷、兩種產(chǎn)品，售價(jià)分別為20和380元。據(jù)統(tǒng)計(jì)，售出一件產(chǎn)品的平均時(shí)間為0.5小時(shí)，而售出一件產(chǎn)品的平均時(shí)間與其銷售的數(shù)量成正比，表達(dá)式為。若該商店總的營(yíng)業(yè)時(shí)間為1000小時(shí)，試確定使其營(yíng)業(yè)額最大的營(yíng)業(yè)計(jì)劃。解：設(shè)和分別代表商店經(jīng)銷A、B兩種產(chǎn)品的件數(shù)，于是有如下數(shù)學(xué)模型：非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型同線性規(guī)劃問(wèn)題的數(shù)學(xué)模型一樣，非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型可以具有不同的形式；但由于我們可以自由地實(shí)現(xiàn)不同形式之間的轉(zhuǎn)換，因此我們可以用如下一般形式來(lái)加以描述：其中是維歐氏空間中的向量點(diǎn)。又因等價(jià)于兩個(gè)不等式：；因此非線性規(guī)劃的數(shù)學(xué)模型也可以表示為：非線性規(guī)劃問(wèn)題的圖示[例3]求解下述非線性規(guī)劃問(wèn)題若令其目標(biāo)函數(shù)，目標(biāo)函數(shù)成為一條曲線或一張曲面；通常稱為等值線或等值面。此例，若設(shè)和可得兩個(gè)圓形等值線，見(jiàn)圖1。222066圖1圖解示意圖由圖1可見(jiàn)，等值線和約束條件直線6-6相切，切點(diǎn)即為此問(wèn)題的最優(yōu)解，，其目標(biāo)函數(shù)值。在此例中，約束對(duì)最優(yōu)解發(fā)生了影響，若以代替原來(lái)的約束，則新的非線性規(guī)劃的最優(yōu)解變?yōu)椋磮D1中的點(diǎn)，此時(shí)。由于此最優(yōu)點(diǎn)位于可行域的內(nèi)部，故事實(shí)上約束并未發(fā)揮約束作用，問(wèn)題相當(dāng)于一個(gè)無(wú)約束極值問(wèn)題。注意：線性規(guī)劃存在最優(yōu)解，最優(yōu)解只能在其可行域的邊緣上（特別能在可行域的頂點(diǎn)上）得到；而非線性規(guī)劃的最優(yōu)解（如果存在）則可能在可行域的任意一點(diǎn)上得到，并非僅局限在邊緣上?！?極值問(wèn)題2-1局部極值與全局極值因?yàn)榫€性規(guī)劃的目標(biāo)函數(shù)和約束條件都是線性函數(shù)，所以其可行域是凸集，因此求得的最優(yōu)解就一定是整個(gè)可行域上的全局最優(yōu)解。非線性規(guī)劃則不然，局部最優(yōu)解未必就一定是全局最優(yōu)解。下面就局部和全局極值問(wèn)題給出如下一些定義：（1）對(duì)于均有不等式，則稱為在上的局部極小點(diǎn)，為局部極小值；（2）對(duì)于均有不等式，則稱為在上的嚴(yán)格局部極小點(diǎn)，為嚴(yán)格局部極小值；（3）對(duì)于均有不等式，則稱為在上的全局極小點(diǎn)，為全局極小值；（4）對(duì)于均有不等式，則稱為在上的嚴(yán)格全局極小點(diǎn)，為嚴(yán)格全局極小值。2-2極值點(diǎn)存在的條件[定理1（必要條件）]設(shè)是上的一個(gè)開(kāi)集，在上有一階連續(xù)偏導(dǎo)數(shù)，且在點(diǎn)取得局部極值，則必有（1）或（2）式（2）中，稱為函數(shù)在點(diǎn)處的梯度。由數(shù)學(xué)分析可知，的方向?yàn)辄c(diǎn)處等值面（等值線）的法線方向，沿這一方向函數(shù)值增加最快，見(jiàn)圖2。方向方向點(diǎn)圖2梯度方向示意圖滿足或的點(diǎn)稱為平穩(wěn)點(diǎn)或駐點(diǎn)。極值點(diǎn)一定是駐點(diǎn)，但駐點(diǎn)不一定是極值點(diǎn)。[定理2（充分條件）]設(shè)是上的一個(gè)開(kāi)集，在上具有二階連續(xù)偏導(dǎo)數(shù)，，若且對(duì)任何非零向量都存在：則為的嚴(yán)格局部極小點(diǎn)。此外，稱為在點(diǎn)處的海賽（Hesse）矩陣。注：二次型，對(duì)于任意總有：若，則稱二次型和對(duì)稱矩陣正定；若，則稱二次型和對(duì)稱矩陣半正定；若，則稱二次型和對(duì)稱矩陣負(fù)定；若，則稱二次型和對(duì)稱矩陣半負(fù)定；若二次型不定，則稱對(duì)稱矩陣不定。由線性代數(shù)知識(shí)可知：若矩陣正定，則其各階左對(duì)角方陣的行列式大于零；若矩陣負(fù)定，則其各階左對(duì)角方陣的行列式負(fù)、正交替。現(xiàn)以代表矩陣中的元素，上述矩陣正定的條件可表示為：；；；矩陣負(fù)定的條件可表示為：；；；；定理2（充分條件）等價(jià)于，如果在點(diǎn)的梯度為零且海賽矩陣正定，則為的嚴(yán)格局部極小點(diǎn)。2-3凸函數(shù)和凹函數(shù)1．定義設(shè)為定義在中某一凸集上的函數(shù)，若對(duì)于任何實(shí)數(shù)（）以及中的任意兩點(diǎn)和，恒有：則稱為定義在上的凸函數(shù)，見(jiàn)圖3；若上式為嚴(yán)格不等式，則稱為定義在上的嚴(yán)格凸函數(shù)。改變不等號(hào)的方向，即可得到凹函數(shù)和嚴(yán)格凹函數(shù)的定義。圖3凸函數(shù)示意圖圖3凸函數(shù)示意圖凸函數(shù)和凹函數(shù)的幾何意義是十分明顯的，若函數(shù)圖形上任意兩點(diǎn)的連線，處處都不在函數(shù)圖形的下方，則此函數(shù)是凸函數(shù)；若函數(shù)圖形上任意兩點(diǎn)的連線，處處都不在函數(shù)圖形的上方，則此函數(shù)是凹函數(shù)。因?yàn)橥购瘮?shù)是研究非線性規(guī)劃求解的基礎(chǔ)，所以凸函數(shù)的性質(zhì)就顯得非常重要了。2．性質(zhì)[性質(zhì)1]設(shè)為定義在凸集上的凸函數(shù)，則對(duì)于任意實(shí)數(shù)，函數(shù)也是定義在上的凸函數(shù)。[性質(zhì)2]設(shè)和為定義在凸集上的兩個(gè)凸函數(shù)，則其和=+仍然是定義在上的凸函數(shù)。[性質(zhì)3]設(shè)為定義在凸集上的凸函數(shù)，則對(duì)于任意實(shí)數(shù)，集合是凸集。[性質(zhì)4]設(shè)為定義在凸集上的凸函數(shù)，則它的任一極小點(diǎn)就是它在上的最小點(diǎn)（全局極小點(diǎn)）；而且它的極小點(diǎn)形成一個(gè)凸集。[性質(zhì)5]設(shè)為定義在凸集上的可微凸函數(shù)，若它存在點(diǎn)，使得對(duì)于所有的有，則是在上的最小點(diǎn)（全局極小點(diǎn)）。3．判定根據(jù)凸函數(shù)的定義進(jìn)行判定根據(jù)一階條件進(jìn)行判定設(shè)為上的開(kāi)凸集，在上具有一階連續(xù)偏導(dǎo)數(shù)，則為上的凸函數(shù)的充分必要條件是，對(duì)于屬于的任意兩個(gè)不同點(diǎn)和恒有：根據(jù)二階條件進(jìn)行判定設(shè)為上的開(kāi)凸集，在上具有二階連續(xù)偏導(dǎo)數(shù)，則為上的凸函數(shù)的充分必要條件是：的海賽矩陣在上處處半正定（）。[例4]試證明是嚴(yán)格的凸函數(shù)（1）定義證明：對(duì)取任意兩點(diǎn)和，分別構(gòu)造兩點(diǎn)的線性組合和兩點(diǎn)函數(shù)值的線性組合；即在的情況下，取，看下式是否成立：顯然恒成立為嚴(yán)格的凸函數(shù)，同理也為嚴(yán)格的凸函數(shù)；所以為嚴(yán)格的凸函數(shù)。（2）一階條件證明：取任意兩點(diǎn)、，從而，，看下式是否成立：顯然恒成立所以為嚴(yán)格的凸函數(shù)。（3）二階條件證明：的海賽矩陣，因正定，固為嚴(yán)格的凸函數(shù)?！?凸規(guī)劃3-1凸規(guī)劃的定義考慮非線性規(guī)劃：假定其中為凸函數(shù)，為凹函數(shù)（為凸函數(shù)），這樣的非線性規(guī)劃稱為凸規(guī)劃。凸規(guī)劃的可行域是凸集，其局部最優(yōu)解即為全局最優(yōu)解；若為嚴(yán)格凸函數(shù)，最優(yōu)解若存在必唯一。由此可見(jiàn)，凸規(guī)劃是一類比較簡(jiǎn)單而又具有重要理論意義的非線性規(guī)劃。由于線性函數(shù)既可以視為凸函數(shù)也可以視為凹函數(shù)，故線性規(guī)劃也屬于凸規(guī)劃。[例5]判斷下述非線性規(guī)劃是否是凸規(guī)劃解：的海賽矩陣正定，故為嚴(yán)格凸函數(shù)；的海賽矩陣半負(fù)定，故為凹函數(shù)。由于其他約束條件均為線性函數(shù)，所以此非線性規(guī)劃是凸規(guī)劃。3-2下降迭代算法1．基本思想給定一個(gè)初始估計(jì)解，然后按某種規(guī)則（即算法）找出一個(gè)比更好的解，如此遞推即可得到一個(gè)解的序列，若這一解的序列有極限，即則稱為最優(yōu)解。2．基本問(wèn)題由于遞推步驟的有限性，一般說(shuō)很難得到精確解，當(dāng)滿足所要求的精度時(shí)即可停止迭代而得到一個(gè)近似解。3．下降算法若某種算法產(chǎn)生的解序列能使目標(biāo)函數(shù)逐步減少，那么就稱此算法為下降算法?！跋陆怠钡囊笃鋵?shí)是很容易滿足的，因此下降算法包括了很多具體的算法。若從出發(fā)沿任何方向移動(dòng)都不能使目標(biāo)函數(shù)下降，則是一個(gè)局部極小點(diǎn)；若從出發(fā)至少存在一個(gè)方向能使目標(biāo)函數(shù)下降，則可選定某一下降方向，沿這一方向前進(jìn)一步，得到下一個(gè)點(diǎn)。沿方向前進(jìn)一步相當(dāng)于在射線上選定新的點(diǎn)；其中為搜索方向，為步長(zhǎng)。確定搜索方向是關(guān)鍵的一步，各種算法的區(qū)別主要在于確定搜索方向的方法不同。步長(zhǎng)的選定一般都是以使目標(biāo)函數(shù)在搜索方向上下降最多為依據(jù)的，稱為最佳步長(zhǎng)；即沿射線求目標(biāo)函數(shù)的極小值：k：min()由于確定步長(zhǎng)是通過(guò)求以為變量的一元函數(shù)()的極小點(diǎn)來(lái)實(shí)現(xiàn)的，故稱這一過(guò)程為一維搜索。101020圖4一維搜索有一個(gè)非常重要的性質(zhì)，即在搜索方向上所得最優(yōu)點(diǎn)的梯度和搜索方向正交；這一性質(zhì)可表達(dá)成：()則有：其幾何意義如圖4所示。因?yàn)檎嬲臉O值點(diǎn)在求解之前并不知道，因此只能根據(jù)相繼兩次迭代的結(jié)果來(lái)建立終止準(zhǔn)則。通常采用的準(zhǔn)則（1，2，3，4，5是事先給定的充分小的正數(shù)）有：相繼兩次迭代的絕對(duì)誤差：1，2相繼兩次迭代的相對(duì)誤差：3，4目標(biāo)函數(shù)梯度的模充分?。?§4一維搜索一維搜索即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)，一維搜索的方法很多，我們只介紹斐波那契和黃金分割兩種方法。4-1斐波那契法一維搜索過(guò)程是建立在一個(gè)被稱為斐波那契數(shù)序列基礎(chǔ)上的，斐波那契數(shù)序列是具有如下遞推關(guān)系的無(wú)窮序列：（）n012345678Fn112358132134斐波那契法成功地實(shí)現(xiàn)了單峰函數(shù)極值范圍的縮減。設(shè)某一單峰函數(shù)在上有一極小點(diǎn)，在此區(qū)間內(nèi)任意取兩點(diǎn)和，使，計(jì)算其函數(shù)值可能出現(xiàn)以下兩種情況：（1），如圖5所示；此時(shí)極小點(diǎn)必在內(nèi)。（2），如圖6所示；此時(shí)極小點(diǎn)必在內(nèi)。f(x)f(x)aa1xb1bx圖5f(x)f(x)aa1xb1bx圖6這說(shuō)明只要在區(qū)間內(nèi)任意取兩點(diǎn)和（）并計(jì)算其函數(shù)值加以比較，就可以把搜索區(qū)間縮減成或。若要繼續(xù)縮小搜索區(qū)間或，只需在區(qū)間內(nèi)再取一點(diǎn)算出其函數(shù)值并與或加以比較即可。由此可見(jiàn)，計(jì)算函數(shù)的次數(shù)越多，搜索區(qū)間就縮得越小，即區(qū)間的縮短率（縮短后的區(qū)間長(zhǎng)度與原區(qū)間長(zhǎng)度之比）與函數(shù)的計(jì)算次數(shù)有關(guān)?，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ū)間才行。實(shí)際上這里的就是前面所說(shuō)的斐波那契數(shù)。計(jì)算個(gè)函數(shù)值所能獲得的最大縮短率為，即計(jì)算個(gè)函數(shù)值可把原長(zhǎng)度為的區(qū)間縮短為： 例如計(jì)算12個(gè)函數(shù)值可把原長(zhǎng)度為的區(qū)間縮短為：若要想將區(qū)間長(zhǎng)度縮短為原長(zhǎng)度的（0<<1）倍，只要足夠大一定能使：（3）這里的稱為區(qū)間縮減的相對(duì)精度。斐波那契法使用對(duì)稱的搜索方式，逐步縮減搜索的區(qū)間，所采取的具體步驟可概括如下：根據(jù)相對(duì)精度或絕對(duì)精度，確定試點(diǎn)個(gè)數(shù)；確定兩個(gè)試點(diǎn)的位置、（對(duì)稱搜索，見(jiàn)圖7）；計(jì)算函數(shù)值和并比較其大小，從而縮減搜索區(qū)間；重復(fù)（2）、（3）兩步，直到得到近似最小點(diǎn)。FFn-2Fn-1aba1b1Fn-2Fn-1圖7[例6]試用斐波那契法求函數(shù)的近似極小點(diǎn)和極小值，要求縮短后的區(qū)間不大于初始區(qū)間的0.05倍。解：容易證明函數(shù)在區(qū)間上是嚴(yán)格凸函數(shù)。為了進(jìn)行比較，在此給出函數(shù)的精確最優(yōu)解，最優(yōu)值。已知=0.05、a=1、b=4，由式（3）有，即。；由于，搜索區(qū)間可以從縮減為。從新的區(qū)間（，）開(kāi)始，繼續(xù)選取對(duì)稱試點(diǎn)比較函數(shù)值，以使區(qū)間進(jìn)一步縮短。由于在新的區(qū)間內(nèi)，已經(jīng)存在一個(gè)已知的試點(diǎn)及其函數(shù)值，所以我們僅需再計(jì)算一個(gè)試點(diǎn)，上述過(guò)程如圖8所示。bb1=2.143b=2.857a=1a1=1.707Fn-2=8Fn-1=13a=1b=4a1=2.143b1=2.857Fn-2Fn-1圖82.040-1.937=0.103<0.152.040-1.937=0.103<0.15a1=1.937b1=2.04073a=1.707b=2.857圖9b1=2.143a1=1.873a1=1.9787a1=2.143b1=2.419新的試點(diǎn)，將原來(lái)的試點(diǎn)視為已知的試點(diǎn)。由于，搜索區(qū)間可以進(jìn)一步從縮減為，如圖9所示。再?gòu)男碌膮^(qū)間（，）開(kāi)始，繼續(xù)選取對(duì)稱試點(diǎn)比較函數(shù)值，以使區(qū)間進(jìn)一步縮短，直到區(qū)間長(zhǎng)度不大于。因此，符合精度要求的近似極小點(diǎn)為，近似極小值為。4-2黃金分割法用斐波那契法以個(gè)點(diǎn)縮減某一區(qū)間時(shí)，區(qū)間長(zhǎng)度的縮減率依次為?，F(xiàn)將以上數(shù)列分為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)，可以證明這兩個(gè)數(shù)列收斂于同一個(gè)極限。設(shè)當(dāng)時(shí)奇數(shù)項(xiàng)偶數(shù)項(xiàng)由于故同理 將代入 ，求解有 若將代入，則有所以以不變的區(qū)間縮減率，代替斐波那契法每次不同的縮減率，就得到了黃金分割法。黃金分割法是一種等速對(duì)稱的搜索方法，每次試點(diǎn)均取在區(qū)間長(zhǎng)度的和處，見(jiàn)圖10。bb1a10.6180.6180.382ba圖10[例7]求函數(shù)在區(qū)間上的極小點(diǎn)，要求縮短后的區(qū)間長(zhǎng)度不大于原區(qū)間長(zhǎng)度的。解：，，，，，，，，，由于從一定的搜索區(qū)間出發(fā)所進(jìn)行的黃金分割搜索與斐波那契搜索在原理上是完全相同的，故在此省略一些計(jì)算細(xì)節(jié)，只將搜索過(guò)程用圖11加以展示。aa1=3.34b1=4.034.03-3.34=0.69<205%=1b1=3.60a1=1.80a=0b=20圖11a1=2.92a1=4.72a1=7.64b1=12.36因此，符合精度要求的近似極小點(diǎn)為，近似極小值為?！?無(wú)約束極值問(wèn)題求解無(wú)約束極值問(wèn)題通常采用迭代法，迭代法可大體分為兩大類：一類要用到函數(shù)的一階導(dǎo)數(shù)和（或）二階導(dǎo)數(shù)，由于此種方法涉及函數(shù)的解析性質(zhì)，故稱為解析法；另一類在迭代過(guò)程中只用到函數(shù)的數(shù)值，而不要求函數(shù)的解析性質(zhì)，故稱為直接法。一般來(lái)講，直接法的收斂速度較慢，只有在變量較少時(shí)才能使用。當(dāng)然，直接法也有其自身的長(zhǎng)處，那就是它的迭代過(guò)程簡(jiǎn)單，并能處理導(dǎo)數(shù)難以求得或根本不存在的函數(shù)極值問(wèn)題。5-1梯度法（最速下降法）1．基本原理假設(shè)無(wú)約束極值問(wèn)題的目標(biāo)函數(shù)有一階連續(xù)偏導(dǎo)數(shù)，且具有極小點(diǎn)；以表示極小點(diǎn)的第次近似，為了求其第次近似點(diǎn)，在點(diǎn)沿方向作射線+，在此稱為步長(zhǎng)并且?，F(xiàn)將在處作泰勒展開(kāi)，有：0（）其中0（）是的高階無(wú)窮小。對(duì)于充分小的，只要（4）即可保證。此時(shí)，若?。?）就一定能使目標(biāo)函數(shù)得到改善?，F(xiàn)在考察不同的方向，假設(shè)的模一定且不為零，并設(shè)（否則是平穩(wěn)點(diǎn)）；那么，使式（4）成立的有無(wú)窮多個(gè)，為了使目標(biāo)函數(shù)能得到盡量大的改善，必須尋求能使取最小值的。由于=，當(dāng)與反向（即）時(shí)，取最小值。被稱為負(fù)梯度方向，在的某一小的鄰域內(nèi)，負(fù)梯度方向是使函數(shù)值下降最快的方向。為了得到下一個(gè)近似點(diǎn)，在選定搜索方向之后，還要確定步長(zhǎng)。的計(jì)算可以采用試算法，即首先選取一個(gè)值進(jìn)行試算，看它是否滿足不等式；如果滿足就迭代下去，否則縮小使不等式成立。由于采用負(fù)梯度方向，滿足該不等式的總是存在的。另一種方法是通過(guò)在負(fù)梯度方向上的一維搜索，來(lái)確定使得最小的k，這種梯度法就是所謂的最速下降法。2．基本步驟給定一個(gè)初始近似點(diǎn)及其精度，若，則即為近似極小點(diǎn)；若，求步長(zhǎng)0并計(jì)算=0。求步長(zhǎng)可以用一維搜索法、微分法，也可以利用試算法；若求最佳步長(zhǎng)，則只能選用前兩種方法。一般地，若，則即為近似極小點(diǎn)；否則求步長(zhǎng)k并計(jì)算=k。如此反復(fù)，直到達(dá)到要求的精度。若具有二階連續(xù)偏導(dǎo)，在處將作泰勒展開(kāi)，即：+對(duì)求導(dǎo)并令其為零，則有最佳步長(zhǎng)k=，可見(jiàn)最佳步長(zhǎng)不僅與梯度有關(guān)，而且與海賽矩陣有關(guān)。[例8]試用梯度法求的極小點(diǎn)，。解：取初始近似點(diǎn)，0==0=xx2x1極小點(diǎn)圖12圖12展示了該例的迭代過(guò)程，即從經(jīng)過(guò)負(fù)梯度方向一步到達(dá)極小點(diǎn)。其實(shí)，對(duì)于等值線為圓的問(wèn)題，不管初始近似點(diǎn)選在哪里，負(fù)梯度方向總是直接指向圓心，一次迭代即能達(dá)到最優(yōu)。[例9]試用梯度法求的極大點(diǎn)。解：該二次函數(shù)的絕對(duì)最優(yōu)解，迭代過(guò)程見(jiàn)圖6-13，任何兩個(gè)相鄰點(diǎn)的梯度一定是正交的。22121圖13設(shè)，因有，所以有。下一個(gè)迭代點(diǎn)是這樣得到的：由有令函數(shù)對(duì)的導(dǎo)數(shù)為零，可求得最佳步長(zhǎng)于是有，同理可進(jìn)行后續(xù)的各步迭代。第二次迭代：，，第三次迭代：，，第四次迭代：，，第五次迭代：，，第六次迭代：因此步，所以由于已經(jīng)很小，所以過(guò)程可以在這一點(diǎn)結(jié)束。近似的極大點(diǎn)是。由于負(fù)梯度方向的最速下降性和正梯度方向的最速上升性，人們很容易認(rèn)為梯度方向是最理想的搜索方向。必須指出點(diǎn)處的梯度方向，僅在點(diǎn)的一個(gè)小鄰域內(nèi)才具有最速的性質(zhì)，而對(duì)于整個(gè)優(yōu)化過(guò)程來(lái)說(shuō)，那就是另外一回事了。由上例可以看出，當(dāng)二次函數(shù)的等值線為同心橢圓時(shí)，采用梯度法其搜索路徑呈直角鋸齒狀；最初幾步函數(shù)值變化顯著，但是越接近最優(yōu)點(diǎn)，收斂的速度越不夠理想。因此，梯度法經(jīng)常與其他方法聯(lián)合使用，在前期使用梯度法，而在接近最優(yōu)點(diǎn)時(shí)使用其他方法。5-2牛頓法利用必要條件來(lái)確定駐點(diǎn)的一個(gè)障礙是在求解聯(lián)立方程時(shí)存在困難。牛頓法是解非線性聯(lián)立方程的一種迭代程序，是前述梯度法的一部分。若非線性目標(biāo)函數(shù)具有二階連續(xù)偏導(dǎo)，在為其極小點(diǎn)的某一近似，在這一點(diǎn)取的二階泰勒展開(kāi)，即：+（6-6）則其梯度為：這一近似函數(shù)的極小點(diǎn)應(yīng)滿足：從而即（7）如果是二次函數(shù)，則其海賽矩陣為常數(shù)，式（6）是精確的。在這種情況下，從任意一點(diǎn)出發(fā)，用式（7）只要一步即可求出的極小點(diǎn)（假設(shè)海賽矩陣正定）。如果不是二次函數(shù)，式（6）僅是一個(gè)近似表達(dá)式。此時(shí)，按式（7）求得的極小點(diǎn)，只是的近似極小點(diǎn)。在這種情況下，常按下式選取搜索方向：（8）=k（9）k：k）（10）按照這種方式求函數(shù)極小點(diǎn)的方法稱為牛頓法，式（8）所示的搜索方向稱為牛頓方向。牛頓法收斂的速度很快，當(dāng)?shù)亩A導(dǎo)數(shù)及其海賽矩陣的逆矩陣便于計(jì)算時(shí)，這一方法非常有效。[例10]試用牛頓法求的極小值。解：是正定矩陣取，則：，，因，故為的極小點(diǎn)，極小值是“0”。[例11]試用牛頓法求的極小值。解：是正定矩陣取，則：，，因，故為的極小點(diǎn)，極小值是“-1”。5-3變尺度法變尺度法（VariableMetricAlgorithm）是近40年來(lái)發(fā)展起來(lái)的求解無(wú)約束極值問(wèn)題的一種有效方法。其主要的優(yōu)點(diǎn)是：既避免了計(jì)算二階導(dǎo)數(shù)矩陣及其求逆過(guò)程，又比梯度法收斂的速度快，特別是對(duì)高維問(wèn)題具有顯著的優(yōu)越性。變尺度法最早由Davidon于1959年提出，后經(jīng)Fletcher和Powell二人改進(jìn)，因此變尺度法也被稱為DFP法。由于實(shí)際問(wèn)題的目標(biāo)函數(shù)往往相當(dāng)復(fù)雜，計(jì)算二階導(dǎo)數(shù)矩陣及其逆矩陣相當(dāng)困難或根本不可能，因此，確定牛頓方向（見(jiàn)式（8））存在很大的障礙。為避免計(jì)算二階導(dǎo)數(shù)矩陣及其逆矩陣，設(shè)法構(gòu)造另一個(gè)矩陣來(lái)逼近二階導(dǎo)數(shù)矩陣的逆矩陣。為實(shí)現(xiàn)逼近的目的，的構(gòu)造應(yīng)遵循如下三條原則：（1）每一步均能按已有的信息確定下一個(gè)搜索方向；（2）每一步迭代均能使目標(biāo)函數(shù)有所下降；（3）近似矩陣最終應(yīng)收斂于解點(diǎn)處的海賽矩陣的逆矩陣。如果是二次函數(shù)，則其海賽矩陣為常數(shù)，式+是精確的，對(duì)于任意兩點(diǎn)和其梯度之差為：即對(duì)于非二次函數(shù)，仿照二次函數(shù)的情形，要求其海賽矩陣逆陣的第次近似矩陣應(yīng)滿足：（11）式（11）就是所謂的擬牛頓條件。若令：則擬牛頓條件可變?yōu)椋含F(xiàn)設(shè)：=于是：或（12）設(shè)想的一種簡(jiǎn)單形式為：（13）式（13）中和是兩個(gè)待定的向量，將式（13）代入式（12）可得：對(duì)照等式兩端，可以推斷：（14）由于應(yīng)為對(duì)稱矩陣，最簡(jiǎn)單的辦法就是?。海?5）將式（15）代入式（14）可得：設(shè)和均不為“0”，則有：（16）于是將式（15）、式（16）代入式（13）可得校正矩陣：從而可以得到：（17）式（17）被稱為尺度矩陣，在整個(gè)迭代過(guò)程中尺度矩陣是不斷變化的，因此該方法稱為變尺度法。通常取初始的尺度矩陣為單位矩陣，以后的尺度矩陣按式（17）逐步形成。下面通過(guò)例題來(lái)展示變尺度法的計(jì)算過(guò)程。[例12]試用變尺度法（DFP）求的極小值，初始搜索點(diǎn)。解：，于是利用一維搜索0：，可得0，于是：利用式（17）有：再利用一維搜索1：，可得1，于是：于是即為極小點(diǎn)，函數(shù)的極小為。在以上的討論中，第一個(gè)尺度矩陣為單位矩陣（對(duì)稱正定陣），以后的尺度矩陣由式（17）逐步形成?？梢宰C明，如此構(gòu)造的尺度矩陣均為對(duì)稱正定陣，進(jìn)而可以確保搜索方向?yàn)橄陆捣较??！?約束極值問(wèn)題大多數(shù)的工程最優(yōu)化問(wèn)題，其變量的取值是受到一定限制的，這種限制是通過(guò)約束條件來(lái)實(shí)現(xiàn)的。帶有約束條件的極值問(wèn)題稱為約束極值問(wèn)題（也成為規(guī)劃問(wèn)題）。求解約束極值問(wèn)題要比求解無(wú)約束極值問(wèn)題困難得多。對(duì)極小化問(wèn)題來(lái)說(shuō)，除了要使目標(biāo)函數(shù)每次迭代都有所下降外，還必須要時(shí)刻注意解的可行性（某些算法除外），這就給優(yōu)化工作帶來(lái)了許多困難。為了簡(jiǎn)化優(yōu)化工作，通常采用如下解題思路：將約束極值問(wèn)題轉(zhuǎn)化為無(wú)約束極值問(wèn)題；將非線性規(guī)劃問(wèn)題轉(zhuǎn)化為線性規(guī)劃問(wèn)題；將復(fù)雜的問(wèn)題分解為若干簡(jiǎn)單問(wèn)題。6-1最優(yōu)性條件現(xiàn)考慮一般形式的非線性規(guī)劃數(shù)學(xué)模型：假設(shè)、和均具有一階連續(xù)偏導(dǎo)數(shù)，是非線性規(guī)劃的一個(gè)可行解?，F(xiàn)考慮某一不等式約束，滿足該不等式有兩種可能：（1），此時(shí)不在由該約束形成的可行域邊界上，因此該約束對(duì)的微小變動(dòng)不起限制作用，從而稱該約束為無(wú)效約束；（2），此時(shí)處在由該約束形成的可行域邊界上，因此該約束對(duì)的微小變動(dòng)會(huì)起某種限制作用，從而稱該約束為有效約束。顯而易見(jiàn)，所有等式約束都是有效約束。是非線性規(guī)劃的一個(gè)可行解，對(duì)于此點(diǎn)的某一方向，若存在實(shí)數(shù)0使任意0均有，就稱方向是點(diǎn)的一個(gè)可行方向，此處代表非線性規(guī)劃的可行域。若是點(diǎn)的任一可行方向，則對(duì)該點(diǎn)所有有效約束均有：，（18）其中代表在點(diǎn)所有有效約束下標(biāo)的集合，如圖14所示。圖14圖14另一方面，由泰勒展開(kāi)式（）可知對(duì)所有有效約束，當(dāng)足夠小時(shí)，只要，（19）就有，此外，對(duì)點(diǎn)所有的無(wú)效約束來(lái)講，由于約束函數(shù)的連續(xù)性，當(dāng)足夠小時(shí)，上式依然成立。從而，只要方向滿足式（19），即可保證是點(diǎn)的可行方向。非線性規(guī)劃的某一可行點(diǎn)，對(duì)該點(diǎn)的任一方向來(lái)說(shuō)，若存在實(shí)數(shù)0使任意0均有，就稱方向是點(diǎn)的一個(gè)下降方向。將目標(biāo)函數(shù)在處作一階泰勒展開(kāi)，若方向滿足（20）則必是點(diǎn)的一個(gè)下降方向。如果方向既是點(diǎn)的一個(gè)可行方向又是一個(gè)下降方向，就稱是點(diǎn)的一個(gè)可行下降方向。顯然，如果某點(diǎn)存在可行下降方向，那么該點(diǎn)就不會(huì)是極小點(diǎn)；另一方面，如果某點(diǎn)是極小點(diǎn)，則該點(diǎn)不存在可行下降方向。[定理3]設(shè)是非線性規(guī)劃的一個(gè)局部極小點(diǎn)，目標(biāo)函數(shù)在處可微，而且在處可微，當(dāng)時(shí)在處連續(xù)，當(dāng)時(shí)（此處代表在處有效約束的下標(biāo)集合）則在點(diǎn)不存在可行下降方向，從而不存在向量同時(shí)滿足，（21）事實(shí)上，若在點(diǎn)存在向量滿足式（21），則從點(diǎn)出發(fā)沿方向搜索可找到比點(diǎn)更好的點(diǎn)，這與點(diǎn)是一個(gè)局部極小點(diǎn)的假設(shè)相矛盾；所以這個(gè)定理是顯然成立的。式（21）的幾何意義是十分明顯的，即點(diǎn)處滿足該條件的方向與點(diǎn)目標(biāo)函數(shù)負(fù)梯度方向的夾角為銳角，與點(diǎn)所有有效約束梯度方向的夾角也為銳角。假設(shè)是非線性規(guī)劃的極小點(diǎn)，該點(diǎn)可能處于可行域的內(nèi)部，也可能處于可行域的邊緣上。若為前者，該規(guī)劃問(wèn)題實(shí)質(zhì)是一個(gè)無(wú)約束極值問(wèn)題，必滿足；若為后者，情況就復(fù)雜多了，接下來(lái)我們就對(duì)這一復(fù)雜情況進(jìn)行分析。不失一般性，設(shè)位于第一個(gè)約束所形成的可行域的邊緣上，即第一個(gè)約束是點(diǎn)處的有效約束，。若是極小點(diǎn)，則必與在同一直線上，且方向相反（這里假定和皆不為“0”）；否則，在點(diǎn)處就一定存在可行下降方向，如圖15所示。圖15中的點(diǎn)是滿足上述條件的極小點(diǎn)，角度表示非極小點(diǎn)處的可行下降方向的范圍。既然與在同一直線上，且方向相反，則必存在一個(gè)實(shí)數(shù)，使。若點(diǎn)處在兩個(gè)有效約束邊緣上，比如說(shuō)和。在這種情況下，必處于和的夾角之內(nèi)；如若不然，點(diǎn)必存在可行下降方向，這與是極小點(diǎn)的相矛盾，如圖16所示。圖6-15圖6-15圖16圖16由此可見(jiàn)，如果是極小點(diǎn)，而且點(diǎn)的有效約束的梯度和線性獨(dú)立，則可以將表示成為和的非負(fù)線性組合；也就是說(shuō)，存在實(shí)數(shù)和，使：如此類推，可以得到：（22）為使所有無(wú)效約束也同上述有效約束一樣包含在式（22）中，增加約束條件，當(dāng)時(shí)；當(dāng)時(shí)。如此即可得到式（23）所示的庫(kù)恩-塔克條件（Kuhn-Tucker，簡(jiǎn)稱K-T條件，滿足這一條件的點(diǎn)稱為K-T點(diǎn)）。設(shè)是非線性規(guī)劃的極小點(diǎn)，而且點(diǎn)各有效約束的梯度線性獨(dú)立，則存在向量，使下述條件成立：，（23），由于等式約束總是有效約束，所以一般形式的非線性規(guī)劃的庫(kù)恩-塔克條件可表達(dá)為：設(shè)是非線性規(guī)劃的極小點(diǎn)，而且點(diǎn)的所有有效約束的梯度和線性獨(dú)立，則存在向量和，使下述條件成立：，（24），式（24）中的和稱為廣義拉格朗日乘子（LagrangeMultipliers）。庫(kù)恩-塔克條件是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是確定某點(diǎn)為極值點(diǎn)的必要條件；但一般來(lái)講它并不是充分條件，因此滿足這一條件的點(diǎn)并非一定就是極值點(diǎn)。對(duì)于凸規(guī)劃，庫(kù)恩-塔克條件是極值點(diǎn)存在的充分必要條件。[例13]求解下述非線性規(guī)劃問(wèn)題S.t.：解：由于是正定矩陣，所以是嚴(yán)格的凸函數(shù)，又由于約束條件是線性函數(shù)，所以此非線性規(guī)劃是凸規(guī)劃，即此時(shí)庫(kù)恩-塔克條件是極值點(diǎn)存在的充分必要條件。引入拉格朗日乘子，設(shè)K-T點(diǎn)為，則該問(wèn)題的K-T條件為：即，，求解此二式與約束條件所形成的聯(lián)立方程組可得：，，所以有最優(yōu)解，最優(yōu)值。[例14]求解下述非線性規(guī)劃問(wèn)題解：設(shè)K-T點(diǎn)為，目標(biāo)函數(shù)極小化，各函數(shù)的梯度分別為：，，對(duì)兩個(gè)約束條件分別引入拉格朗日乘子和，則有如下K-T條件：，為求解該方程組，需要考慮以下幾種情況：（1），時(shí)，無(wú)解；（2），時(shí)，，；（3），時(shí)，，；（4），時(shí)，，。圖17圖1794641對(duì)應(yīng)第（2）、（3）、（4）三種情況，得到三個(gè)K-T點(diǎn)；其中和是極大值點(diǎn)，而是極小值點(diǎn)。參照?qǐng)D6-17，很容易得到此題的最優(yōu)解，最優(yōu)值。6-2二次規(guī)劃若某非線性規(guī)劃的目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性函數(shù)，則稱此規(guī)劃為二次規(guī)劃。二次規(guī)劃是非線性規(guī)劃中較為簡(jiǎn)單的一種，許多方面的問(wèn)題都可以抽象為二次規(guī)劃，而且它和線性規(guī)劃有著非常直接的關(guān)系。二次規(guī)劃的數(shù)學(xué)模型可表示為：（25）式（25）中是一個(gè)二次型，為對(duì)稱矩陣。如果問(wèn)題極大化，假設(shè)為負(fù)定；如果問(wèn)題極小化，假設(shè)為正定。約束條件的線性假設(shè)，確保了二次規(guī)劃有一個(gè)凸的解空間。二次規(guī)劃屬于凸規(guī)劃，其局部極值即為全局極值，同時(shí)庫(kù)恩-塔克條件是極值點(diǎn)存在的充分必要條件。二次規(guī)劃的數(shù)學(xué)模型可作如下變形：設(shè)和分別是對(duì)應(yīng)兩組約束條件和的廣義拉格朗日乘子，應(yīng)用K-T條件可得：，，現(xiàn)在設(shè)（約束條件的松弛變量），以上條件可簡(jiǎn)寫(xiě)成：（對(duì)于一切的和）因，將第一個(gè)方程組轉(zhuǎn)置可得：于是上面的充分必要條件合并成：（26）（對(duì)于一切的和）模型中除了這個(gè)條件以外，其余的方程都是關(guān)于，，和的線性函數(shù)。因此，問(wèn)題等價(jià)于求解一組滿足附加條件的線性方程組。因?yàn)槭菄?yán)格的凹函數(shù)且具有一個(gè)凸的解空間，所以上述方程組的解若存在一定唯一，而這唯一解一定就是最優(yōu)解。[例15]求解二次規(guī)劃問(wèn)題這一問(wèn)題可以用矩陣形式表示為：這就形成了式（26）所需要的全部信息：引入人工變量和得到第一階段的初始單純形表，見(jiàn)表1。表1cj000000-1-1CBXBx1x2112s1R1R2-1-10R1R2s1421-100102420-100112000100462j663-1-1000-10第一次迭代：，可以讓入基，按最小比值確定出基，見(jiàn)表2。表2cj000000-1-1CBXBx1x2112s1R1R20-10x1R2s111/21/4-1/4001/40033/21/2-10-1/2103/2-1/41/401-1/40141j033/21/2-10-3/20-4第二次迭代：，可以讓入基，按最小比值確定出基，見(jiàn)表3。表3cj000000-1-1CBXBx1x2112s1R1R20-10x1R2x2101/3-1/30-1/31/300020-1-20101-11/602/3-1/602/322/3j0020-1-2-10-2第三次迭代：，可以讓入基，按最小比值確定出基，見(jiàn)表4。表4cj000000-1-1CBXBx1x2112s1R1R2000x11x2100-1/31/601/3-1/60010-1/2-101/20101/6-1/121/2-1/61/121/315/6j000000-1-10表4給出了第一階段的最優(yōu)解，由于，所以此解對(duì)于原二次規(guī)劃不僅是可行的而且是最優(yōu)的，即最優(yōu)解，最優(yōu)值。6-3可行方向法設(shè)是非線性規(guī)劃的一個(gè)可行解，但不是極小點(diǎn)。為了求解出它的極小點(diǎn)或近似極小點(diǎn)，應(yīng)在點(diǎn)的可行下降方向中選取某一方向并確定步長(zhǎng)，使（代表可行域）且。若此時(shí)已滿足精度要求，迭代結(jié)束，就是所求的極小點(diǎn)；否則，從出發(fā)繼續(xù)迭代，直到滿足精度要求為止。此種方法稱為可行方向法，其特點(diǎn)是“迭代所采用的搜索方向?yàn)榭尚蟹较?，所產(chǎn)生的迭代點(diǎn)序列始終在可行域的內(nèi)部，目標(biāo)函數(shù)單調(diào)下降”。由此可見(jiàn)，許多方法可歸入可行方向法這一類別；但人們通常所講的可行方向法，一般指的是Zoutendijk在1960年提出的算法及其變形，下面就來(lái)介紹一下Zoutendijk的可行方向法。設(shè)點(diǎn)的有效約束集非空，為求點(diǎn)的可行下降方向，可由下述不等式組來(lái)確定向量：（對(duì)于所有的）這等價(jià)于由下面的不等式組來(lái)求向量和實(shí)數(shù)：（對(duì)于所有的）現(xiàn)使和（對(duì)于所有的）的最大值極小化（同時(shí)必須限制向量的模），即可將上述選取搜索方向的工作轉(zhuǎn)化為求解下述線性規(guī)劃問(wèn)題：（27）（對(duì)于所有的）式中是向量的各個(gè)分量。式（27）中加入最后一個(gè)約束條件，為的是使該線性規(guī)劃問(wèn)題有有限最優(yōu)解。此外，由于我們的目的在于尋找搜索向量，所以只要知道的各分量的相對(duì)大小即可?，F(xiàn)將式（27）所示的線性規(guī)劃的最優(yōu)解記為，如果求得的，說(shuō)明在點(diǎn)處不存在可行下降方向，在（對(duì)于所有的）線性獨(dú)立的條件下，點(diǎn)即為一個(gè)K-T點(diǎn)；如果求得的，則得到可行下降方向，這就是點(diǎn)處所要的搜索方向。下面通過(guò)例題來(lái)說(shuō)明利用可行方向法求解非線性規(guī)劃的一般步驟。[例16]用可行方向法求解解：取初始點(diǎn)，于是有由于，于是有由于，故約束不是初始點(diǎn)的有效約束。取，從而：令，可得。令，；取，于是：，，，，。構(gòu)造線性規(guī)劃：為便于求解，令，，，于是：用單純形法求解，可得最優(yōu)解，即：，，所以，現(xiàn)暫時(shí)用該步長(zhǎng)計(jì)算，有。因?yàn)椋f(shuō)明是可行點(diǎn)，選取是可行的。繼續(xù)迭代下去，可得最優(yōu)解，最優(yōu)值。6-4制約函數(shù)法制約函數(shù)法是通過(guò)加到非線性規(guī)劃目標(biāo)函數(shù)上的某種制約函數(shù)，將約束極值問(wèn)題轉(zhuǎn)化為無(wú)約束極值問(wèn)題的一類算法。由于制約函數(shù)需要求解一系列無(wú)約束極值問(wèn)題，故也稱為序列無(wú)約束極小化技術(shù)，簡(jiǎn)記為SUMT（SequentialUnconstrainedMinimizationTechnique）。常用的制約函數(shù)有兩種基本類型，一類為懲罰函數(shù)（也稱為外點(diǎn)法），另一類為障礙函數(shù)（也稱為內(nèi)點(diǎn)法）。外點(diǎn)法考慮非線性規(guī)劃，為求其最優(yōu)解，構(gòu)造一個(gè)函數(shù)，現(xiàn)把當(dāng)作所構(gòu)造函數(shù)的自變量來(lái)看待，顯然當(dāng)（代表可行域）時(shí)，（）；當(dāng)時(shí)，。再構(gòu)造一個(gè)函數(shù)，求解，假設(shè)該問(wèn)題有最優(yōu)解，則（），即最優(yōu)解一定是可行解。因此，不僅是的極小解，同時(shí)也是原函數(shù)的極小解。這樣一來(lái)，就把約束極值問(wèn)題轉(zhuǎn)化成了無(wú)約束極值問(wèn)題。用上述方法構(gòu)造的函數(shù)在處不連續(xù)，更不存在導(dǎo)數(shù)。為此，將修改為：修改后的在處連續(xù)且導(dǎo)數(shù)為“0”；而且及其導(dǎo)數(shù)對(duì)任何都連續(xù)。當(dāng)時(shí)，仍有；當(dāng)時(shí)，。取一個(gè)充分大的正數(shù)，將修改為：（28）或從而可使的解為原問(wèn)題的極小解或近似極小解。若，則必定是原問(wèn)題的極小解。事實(shí)上，對(duì)于所有的都有：即當(dāng)時(shí)，有。式（28）中的函數(shù)稱為懲罰函數(shù)，第二項(xiàng)稱為懲罰項(xiàng)，稱為懲罰因子。若對(duì)于某一懲罰因子，如果，就加大懲罰因子的值。隨著懲罰因子數(shù)值的