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

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