【正文】 第六章* 非線性規(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é)的一個(gè)重要分支，在管理科學(xué)、最優(yōu)設(shè)計(jì)、系統(tǒng)控制等許多領(lǐng)域得到了廣泛的應(yīng)用。一般來講，非線性規(guī)劃問題的求解要比線性規(guī)劃問題的求解困難得多；而且也不象線性規(guī)劃問題那樣具有一種通用的求解方法（單純形法）。非線性規(guī)劃沒有能夠適應(yīng)所有問題的一般求解方法，各種方法都只能在其特定的范圍內(nèi)發(fā)揮作用。本章在簡要介紹非線性規(guī)劃基本概念和一維搜索的基礎(chǔ)上，重點(diǎn)介紹無約束極值問題和約束極值問題的求解方法。167。1非線性規(guī)劃的數(shù)學(xué)模型 非線性規(guī)劃問題[例61] 某商店經(jīng)銷、兩種產(chǎn)品，售價(jià)分別為20和380元。據(jù)統(tǒng)計(jì)，而售出一件產(chǎn)品的平均時(shí)間與其銷售的數(shù)量成正比，表達(dá)式為。若該商店總的營業(yè)時(shí)間為1000小時(shí)，試確定使其營業(yè)額最大的營業(yè)計(jì)劃。解：設(shè)和分別代表商店經(jīng)銷A、B兩種產(chǎn)品的件數(shù)，于是有如下數(shù)學(xué)模型：[例62] 在層次分析（Analytic Hierarchy Process, 簡記為 AHP）中，為了進(jìn)行多屬性的綜合評價(jià)，需要確定每個(gè)屬性的相對重要性，即它們各自的權(quán)重。為此，將各屬性進(jìn)行兩兩比較可得如下判斷矩陣：其中：是第個(gè)屬性與第個(gè)屬性的重要性之比?，F(xiàn)需要從判斷矩陣求出各屬性的權(quán)重，為使求出的權(quán)重向量在最小二乘意義上能最好地反映判斷矩陣的估計(jì)，由可得： 非線性規(guī)劃問題的數(shù)學(xué)模型同線性規(guī)劃問題的數(shù)學(xué)模型一樣，非線性規(guī)劃問題的數(shù)學(xué)模型可以具有不同的形式；但由于我們可以自由地實(shí)現(xiàn)不同形式之間的轉(zhuǎn)換，因此我們可以用如下一般形式來加以描述：其中是維歐氏空間中的向量點(diǎn)。又因等價(jià)于兩個(gè)不等式：；因此非線性規(guī)劃的數(shù)學(xué)模型也可以表示為： 非線性規(guī)劃問題的圖示[例63] 求解下述非線性規(guī)劃問題若令其目標(biāo)函數(shù)，目標(biāo)函數(shù)成為一條曲線或一張曲面；通常稱為等值線或等值面。此例，若設(shè)和可得兩個(gè)圓形等值線，見圖61。22066圖61 圖解示意圖由圖61可見，等值線和約束條件直線66相切，切點(diǎn)即為此問題的最優(yōu)解，其目標(biāo)函數(shù)值。在此例中，約束對最優(yōu)解發(fā)生了影響，若以代替原來的約束，則新的非線性規(guī)劃的最優(yōu)解變?yōu)?，即圖61中的點(diǎn)，此時(shí)。由于此最優(yōu)點(diǎn)位于可行域的內(nèi)部，故事實(shí)上約束并未發(fā)揮約束作用，問題相當(dāng)于一個(gè)無約束極值問題。注意：線性規(guī)劃存在最優(yōu)解，最優(yōu)解只能在其可行域的邊緣上（特別能在可行域的頂點(diǎn)上）得到；而非線性規(guī)劃的最優(yōu)解（如果存在）則可能在可行域的任意一點(diǎn)上得到，并非僅局限在邊緣上。167。2極值問題21局部極值與全局極值因?yàn)榫€性規(guī)劃的目標(biāo)函數(shù)和約束條件都是線性函數(shù)，所以其可行域是凸集，因此求得的最優(yōu)解就一定是整個(gè)可行域上的全局最優(yōu)解。非線性規(guī)劃則不然，局部最優(yōu)解未必就一定是全局最優(yōu)解。下面就局部和全局極值問題給出如下一些定義：（1）對于189。189。均有不等式，則稱為在上的局部極小點(diǎn)，為局部極小值；（2）對于189。189。均有不等式，則稱為在上的嚴(yán)格局部極小點(diǎn)，為嚴(yán)格局部極小值；（3）對于均有不等式，則稱為在上的全局極小點(diǎn)，為全局極小值；（4）對于均有不等式，則稱為在上的嚴(yán)格全局極小點(diǎn)，為嚴(yán)格全局極小值。22極值點(diǎn)存在的條件[定理1（必要條件）] 設(shè)是上的一個(gè)開集，在上有一階連續(xù)偏導(dǎo)數(shù)，且在點(diǎn)取得局部極值，則必有 （61）或 （62）式（62）中，稱為函數(shù)在點(diǎn)處的梯度。由數(shù)學(xué)分析可知，的方向?yàn)辄c(diǎn)處等值面（等值線）的法線方向，沿這一方向函數(shù)值增加最快，見圖62。方向點(diǎn)圖62 梯度方向示意圖滿足或的點(diǎn)稱為平穩(wěn)點(diǎn)或駐點(diǎn)。極值點(diǎn)一定是駐點(diǎn)，但駐點(diǎn)不一定是極值點(diǎn)。[定理2（充分條件）] 設(shè)是上的一個(gè)開集，在上具有二階連續(xù)偏導(dǎo)數(shù)，若且對任何非零向量都存在：則為的嚴(yán)格局部極小點(diǎn)。此外，稱為在點(diǎn)處的海賽（Hesse）矩陣。注：二次型，對于任意總有：（1） 若，則稱二次型和對稱矩陣正定；（2） 若，則稱二次型和對稱矩陣半正定；（3） 若，則稱二次型和對稱矩陣負(fù)定；（4） 若，則稱二次型和對稱矩陣半負(fù)定；（5） 若二次型不定，則稱對稱矩陣不定。由線性代數(shù)知識可知：若矩陣正定，則其各階左對角方陣的行列式大于零；若矩陣負(fù)定，則其各階左對角方陣的行列式負(fù)、正交替?，F(xiàn)以代表矩陣中的元素，上述矩陣正定的條件可表示為：；；188。；矩陣負(fù)定的條件可表示為：；；；188。；定理2（充分條件）等價(jià)于，如果在點(diǎn)的梯度為零且海賽矩陣正定，則為的嚴(yán)格局部極小點(diǎn)。23凸函數(shù)和凹函數(shù)1．定義設(shè)為定義在中某一凸集上的函數(shù)，若對于任何實(shí)數(shù)a（）以及中的任意兩點(diǎn)和，恒有：則稱為定義在上的凸函數(shù)，見圖63；若上式為嚴(yán)格不等式，則稱為定義在上的嚴(yán)格凸函數(shù)。改變不等號的方向，即可得到凹函數(shù)和嚴(yán)格凹函數(shù)的定義。圖63 凸函數(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ù)，則對于任意實(shí)數(shù)，函數(shù)也是定義在上的凸函數(shù)。[性質(zhì)2] 設(shè)和為定義在凸集上的兩個(gè)凸函數(shù)，則其和=+仍然是定義在上的凸函數(shù)。[性質(zhì)3] 設(shè)為定義在凸集上的凸函數(shù)，則對于任意實(shí)數(shù)，集合189。是凸集。[性質(zhì)4] 設(shè)為定義在凸集上的凸函數(shù)，則它的任一極小點(diǎn)就是它在上的最小點(diǎn)（全局極小點(diǎn)）；而且它的極小點(diǎn)形成一個(gè)凸集。[性質(zhì)5] 設(shè)為定義在凸集上的可微凸函數(shù)，若它存在點(diǎn)，使得對于所有的有，則是在上的最小點(diǎn)（全局極小點(diǎn)）。3．判定（1） 根據(jù)凸函數(shù)的定義進(jìn)行判定（2） 根據(jù)一階條件進(jìn)行判定設(shè)為上的開凸集，在上具有一階連續(xù)偏導(dǎo)數(shù)，則為上的凸函數(shù)的充分必要條件是，對于屬于的任意兩個(gè)不同點(diǎn)和恒有：（3） 根據(jù)二階條件進(jìn)行判定設(shè)為上的開凸集，在上具有二階連續(xù)偏導(dǎo)數(shù)，則為上的凸函數(shù)的充分必要條件是：的海賽矩陣在上處處半正定（）。[例64] 試證明是嚴(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ù)。167。3凸規(guī)劃31 凸規(guī)劃的定義考慮非線性規(guī)劃： 假定其中為凸函數(shù)，為凹函數(shù)（為凸函數(shù)），這樣的非線性規(guī)劃稱為凸規(guī)劃。凸規(guī)劃的可行域是凸集，其局部最優(yōu)解即為全局最優(yōu)解；若為嚴(yán)格凸函數(shù)，最優(yōu)解若存在必唯一。由此可見，凸規(guī)劃是一類比較簡單而又具有重要理論意義的非線性規(guī)劃。由于線性函數(shù)既可以視為凸函數(shù)也可以視為凹函數(shù)，故線性規(guī)劃也屬于凸規(guī)劃。[例65] 判斷下述非線性規(guī)劃是否是凸規(guī)劃解：的海賽矩陣正定，故為嚴(yán)格凸函數(shù)；的海賽矩陣半負(fù)定，故為凹函數(shù)。由于其他約束條件均為線性函數(shù)，所以此非線性規(guī)劃是凸規(guī)劃。32下降迭代算法1．基本思想給定一個(gè)初始估計(jì)解，然后按某種規(guī)則（即算法）找出一個(gè)比更好的解，如此遞推即可得到一個(gè)解的序列，若這一解的序列有極限，即則稱為最優(yōu)解。2．基本問題由于遞推步驟的有限性，一般說很難得到精確解，當(dāng)滿足所要求的精度時(shí)即可停止迭代而得到一個(gè)近似解。3．下降算法若某種算法產(chǎn)生的解序列能使目標(biāo)函數(shù)逐步減少，那么就稱此算法為下降算法。“下降”的要求其實(shí)是很容易滿足的，因此下降算法包括了很多具體的算法。若從出發(fā)沿任何方向移動(dòng)都不能使目標(biāo)函數(shù)下降，則是一個(gè)局