第四章非線性規劃模型
第一節非線性規劃的例項與基本概念
一、非線性規劃的例項
例1 化學反應的平衡組成
設現有原料由種原子組成，各種原子數量依次為共生成種分子（產品），設生產數量（待求）依次為。設第種分子中含各種原子的數量依次為
所有產品中含第種原子數之和為
由熟知的質量守恆定律有
在一定的溫度、壓力下，每種化合物都具有一定的自由能，根據化學熱力學原理，當化學反應達到平衡狀態時，系統的總自由能最小。用表示第種化合物具有的自由能，它的表示式為
其中是與溫度、壓力及有關的常數。總自由能為
問題變為求使
（4-1）
4-2）
式（4-1），（4-2）構成的數學模型顯然與前幾章的數學模型不同，它就是我們即將介紹的非線性規劃模型。
例2 成組氣田開發的最優化模型
設有一組個氣田，要求在一定開發期內產氣總量為，而為第個
氣田的極限產量，為第個氣田的最優產量（待求），為第個氣田的生產井數，可按公式
計算，其中，分別為第個氣田的地層邊界壓力和井底流動壓力，，，是與第個氣田的地層形狀、流動條件、井排數、井排半徑及井距有關的常數。要求各氣田適當配產，使單產成本最低。
根據題意可得如下數學模型
4-3）
（4-4）
其中，，分別與第個氣田的管線成本、生產消耗、氣壓站和綜合處理站、鑽井成本有關的引數。式（4-3），（4-4）也是乙個非線性規劃模型。
二、非線性規劃的基本概念
1．非線性規劃的定義
稱形如4-5）
4-6）
4-7）
的數學模型為乙個數學規劃，稱為該數學規劃的目標函式，稱（4-6）式為等式約束，（4-7）式為不等式約束，若中至少有乙個是變數的非線性函式，則稱模型（4-5）—（4-7）是非線性規劃問題，否則稱（4-5）—（4-7）為線性規劃問題。當時，稱問題，為無約束最優化問題，簡稱為無約束問題。
2．最優解的概念
滿足（4-6），（4-7）的維向量稱為該數學規劃的乙個可行點，所有可行點做成的集合稱為可行集或可行域，即
對於，若有，使，對所有滿足的都成立，則稱為該規劃的乙個區域性最優解；若對所有都成立，則稱為該規劃的整體最優解或全域性最優解。
若對於，有，使，對所有滿足的且都成立，則稱為該規劃的乙個嚴格區域性最優解；若對所有且都成立,則稱為該規劃的乙個嚴格整體最優解。
例3 設有非線性規劃問題
可行集d如圖所示，由於，又，，因此是該問題的乙個整體最優解. 當然也是區域性最優解
圖1 例3的可行集d
第二節 n元函式微分學與最優性條件
一、n元函式微分學知識
為了給出非線性規劃問題的最優性條件，先來介紹一些元函式的微分學知識.在下邊的討論中，假設元函式具有討論中所遇到的可微性階數.
1．梯度
函式在點處的梯度，定義為在點處的個偏導數構成的列向量，記為，即
4-8）
2．二階偏導數矩陣（hesse矩陣）
稱如下的階方陣
4-9）
為函式在點處的二階偏導數矩陣亦稱為hesse矩陣，當時，為一實對稱矩陣.
3．公式
元函式在點處的公式（寫到二次項）為
4-10)
其中為比高階的無窮小量.
4．最速下降方向
下面證明，是在點處的最速下降方向.因為函式沿方向的變化率是，故在點處最速下降方向的單位向量應是問題
4-11）
的解，注意到，其中是與方向的夾角。極小化該式，便得到當即時，的值最小，這時，因此稱為函式在點處的最速下降方向，同樣理由稱為在點處的最速上公升方向。
5．一維搜尋與下降方向
給定點，方向向量，稱問題
為由點始沿方向的一維搜尋.這是一元函式求極小點的問題。
將函式在點展開得
4-12）
當且充分小時，由上式得即當充分小且時，函式值較小，因此，若，稱為函式在點處的下降方向，類似地，若，且充分小，由（4-8）式知，因此，此時稱為函式在點處的上公升方向。
二、無約束問題的最優性條件
定理1 （一階必要條件）設函式連續可微，若點是的區域性極小點，則。
證明用反證法，設，取，則，因而存在，使當時，，這與為的區域性極小點矛盾.故應有。
若有點使，則稱為的駐點或穩定點.由此，定理1表明，若函式連續可微，且不是駐點，則不是的區域性極小點。
定理 2 （二階必要條件）若函式二階連續可微，且是的區域性極小點，則，且半正定。
證明由題設及公式有
於是 （4-13）
令，由於，故由（4-9）式得，又由的任意性知，半正定。
定理3 （二階充分條件）設函式二階連續可微，且，正定，則為的嚴格區域性極小點。
證明據已知條件和公式得
4-14）
由正定知，存在正數使得，故由（4-14）式得：
4-15）
因此據式（4-15）知，存在使當時，即當
且時，，故為的嚴格區域性極小點。
三、約束極值問題的最優解的一階必要條件
定理4 設是約束極值問題
4-16）
4-17）
4-18）
的區域性最優解，且向量組，，，，線性無關，其中為在點處有效不等式約束的指標集，則存在向量，且，使
4-19）
4-20）
證明略.
條件（4-19），(4-20)稱為kuhn-tuker條件,這個條件是很重要的.它是設計演算法、研究演算法收斂性、給出判斷程式終止準則的理論基礎。常稱定理4為kuhn-tuker定理，滿足kuhn-tuker條件的可行點稱為k-t點。
四、凸規劃及其最優性條件
1．凸集中的乙個非空子集稱為凸集,若及,有。
2．凸函式在凸集上定義的函式稱為凸函式，若，及，有
若函式為凸集上的凸函式，則稱為上的凹函式.易知凸集上的線性函式即是凸函式又是凹函式。
3．凸規劃對於非線性規劃問題（4-16）—（4-18），若為一凸函式，為凹函式，而為線性函式，則稱該問題為一凸規劃問題。
4．凸規劃的最優性條件
定理 5 設為凸規劃問題（4-16）—（4-18）的乙個可行點，則為該問題的最優解的充分必要條件是為該問題的k-t點。
證明略。
應指出，對於凸規劃問題，任何區域性最優解均為全域性最優解。
第三節一維搜尋演算法
對於一元函式，,求使達到極小，對於，，當給定，，，問題
也是一種求一元函式的極小問題，這就是一維搜尋問題。
一維搜尋演算法一般分為兩步：第一步，找乙個包含極小點區間，稱為極小區間，第二步，逐步縮小極小區間，直到極小區間的長度已充分小，則區間中點可近似作為的極小點。本節先給出求極小區間的「倍增半減法」，再給出縮短極小區間的法。
一、求極小區間的倍增半減法
對於問題
可取一初始步長，及，計算，（其中），若
即向右搜尋時，下降，令，，計算，，表明向右搜尋時，仍下降，令，，直到第步有，且，則令，，為一極小區間。
圖2 求極小區間框圖
如果時已有
把的數值對換，且令，計算，若
則令；否則令，，直到函式值增加，即有某個使時，則令。
將以上步驟做成框圖，見圖2。
二、縮短極小區間的0.618法
前段已得到極小區間，現在要按比例來縮短區間的長度，待定.在內取點，.設下乙個較好區間為，見圖3。
圖3 法縮短區間過程
即設，在新區間內仍按比例縮短區間，即取點, ,由，得
今希望新點中有一點與重合，以便少算一次函式值.據的表示式知：若讓，則得，導致，不符合要求。若讓得，
，整理得，解得，取。由及得縮短區間的演算法框圖如圖4，設控制精度為。
圖4法縮短極小區間框圖
附註：法只是一維搜尋演算法的一部分，必須上接求極小區間的倍增半減法，二者合起來才構成乙個完整的一維搜尋演算法。
第四節共軛梯度法
共軛方向法是一模擬較有效的求解無約束問題的方法,此類方法中較常用的一種方法是共軛梯度法。本節內容分為三部分，第一部分介紹本節所需要的代數預備知識，第二部分一般地介紹共軛方向法的基本性質，第三部分給出共軛梯度法的迭代步驟與性質。
第4章非線性規劃張
第四章非線性規劃模型 第一節非線性規劃的例項與基本概念 一 非線性規劃的例項 例1 化學反應的平衡組成 設現有原料由種原子組成，各種原子數量依次為共生成種分子 產品 設生產數量 待求 依次為。設第種分子中含各種原子的數量依次為 所有產品中含第種原子數之和為 由熟知的質量守恆定律有 在一定的溫度 壓力...
非線性規劃
習題六6.1 試計算函式f x x12 x1x2 x22 的梯度和hesse矩陣。6.2 試證明下述函式f x 2x1x2x3 4x1x3 2x2x3 x12 x22 x32 2x1 4x2 4x3具有駐點 0，3，1 0，1，1 1，2，0 2，1，1 2，3，1 再應用充分性條件找出其極點。6....
求解非線性規劃
非線性規劃的例項與定義 如果目標函式或約束條件中包含非線性函式，就稱這種規劃問題為非線性規劃問題。一般說來，解非線性規劃要比解線性規劃問題困難得多。而且，也不象線性規劃有單純形法這一通用方法，非線性規劃目前還沒有適於各種問題的一般演算法，各個方法都有自己特定的適用範圍。1.2 線性規劃與非線性規劃的...