非線性規(guī)劃基礎(chǔ)理論

非線性規(guī)劃基礎(chǔ)理論第1頁，共23頁，2023年，2月20日，星期四引言什么是非線性規(guī)劃線性規(guī)劃問題和整數(shù)規(guī)劃問題，其共同的特征是最優(yōu)化問題中的目標函數(shù)和約束條件均為設(shè)計變量的線性函數(shù)。但在實際建模過程中還有大量的問題，其目標函數(shù)或約束條件很難用線性函數(shù)來表達，當(dāng)目標函數(shù)或約束條件中有一個以上是非線性函數(shù)時，就不能用線性的方法來處理，而要采用非線性的方法，那么我們稱這種問題為非線性規(guī)劃問題非線性規(guī)劃的產(chǎn)生和發(fā)展自從1951年H.W.Kuhn及A.W.Tucker探討了非線性規(guī)劃解的最優(yōu)性條件，為非線性規(guī)劃奠定了理論基礎(chǔ)之后，非線性規(guī)劃逐漸形成了一門十分重要且比較活躍的新興學(xué)科，出現(xiàn)了許多解非線性規(guī)劃問題的有效的算法。由70年代開始，該分支得到迅速發(fā)展：理論方面，非線性規(guī)劃借鑒了數(shù)學(xué)理論中其他分支的成果，逐步形成自身的學(xué)科特色；在應(yīng)用方面，非線性規(guī)劃為系統(tǒng)的優(yōu)化和管理提供了有力的工具。隨著電子計算機的應(yīng)用，非線性規(guī)劃在最優(yōu)設(shè)計、管理科學(xué)、質(zhì)量控制等許多領(lǐng)域得到越來越深入的應(yīng)用。非線性規(guī)劃發(fā)展到今天，雖然已經(jīng)提出許多求解方法和策略，但是對于非線性規(guī)劃的最優(yōu)化問題目前還沒有適于各種不同情況的一般算法，各個方法都有自己特定的適用范圍。因而，這是需要人們更深入的進行研究的一個領(lǐng)域。第2頁，共23頁，2023年，2月20日，星期四典型的非線性規(guī)劃問題選址問題問題的提出一家大型連鎖超市在某地有家分店，為了數(shù)學(xué)語言描述的方便，可在平面直角坐標系給出其位置表述：A1的坐標為(x1,y1)，A2的坐標為(x2,y2)，以此類推，An的坐標為(xn,yn)。現(xiàn)在超市擬在當(dāng)?shù)剡x擇一個理想的位置建立一個供貨點，由于該超市各分店在經(jīng)營規(guī)模上的不同，出貨量也不同，導(dǎo)致供貨點對各分店的送貨頻率不同，假設(shè)供貨點每周給Ai送貨的次數(shù)為ci(i=1,2,…,n)，同時假設(shè)每公里的運輸費保持定值m元/公里。那么超市應(yīng)當(dāng)把供貨點設(shè)在什么地方可以使得運輸成本最低？問題分析假設(shè)供貨點坐標為(x,y)，那么由供貨點到某分店Ai的距離和運輸費分別為：故運輸?shù)目偝杀緸閷Ω鱾€分店運輸成本的總和，整個問題的數(shù)學(xué)模型可以表達為：上述問題的目標函數(shù)為設(shè)計變量x和y的非線性函數(shù)，故為非線性規(guī)劃問題，由于設(shè)計變量x和y不受任何條件的約束，故為無約束非線性規(guī)劃。第3頁，共23頁，2023年，2月20日，星期四典型的非線性規(guī)劃問題營業(yè)計劃制定問題

問題的提出某公司銷售兩種建材A和B以滿足市場的需要，生產(chǎn)建材A和B均要消耗資原材料M和N，其中每噸A建材需要消耗10噸M和18噸N，每噸B需要消耗20噸M和12噸N，已知產(chǎn)品的利潤是銷售量的函數(shù)，現(xiàn)有原材料200噸M和100噸N，產(chǎn)品的售價、和資源的對應(yīng)關(guān)系如表所示，該公司應(yīng)當(dāng)如何制定生產(chǎn)銷售計劃使得銷售額最大。

消耗資源M(噸)消耗資源N(噸)單位售價(萬元/噸)A11.8p1=5-0.01x1B21.2p2=6-0.03x2資源限制200100第4頁，共23頁，2023年，2月20日，星期四典型的非線性規(guī)劃問題營業(yè)計劃制定問題問題分析設(shè)x1和x2為產(chǎn)品A和產(chǎn)品B的銷售量，由A的單價為p1，B的單價為p2，則可知公司的銷售收入為，在該例中，單位售價為銷量的函數(shù)，故由表中的公式可得最優(yōu)化的目標為使得銷售額最大，即取得最大值。由原材料的限制，可得約束條件為：且考慮到和的產(chǎn)量應(yīng)當(dāng)為非負實數(shù)，故該問題的數(shù)學(xué)模型為：上述問題的目標函數(shù)為設(shè)計變量x1和x2的非線性函數(shù)，約束條件為設(shè)計變量的x1和x2的線性函數(shù)，為有約束的非線性規(guī)劃問題。第5頁，共23頁，2023年，2月20日，星期四典型的非線性規(guī)劃問題容器設(shè)計問題問題的提出某工廠按照客戶的要求定制專門的儲藏用容器，訂貨合同要求該工廠制造一種敞口的長方體容器，容積為10m3，該種容器的底必須為正方形，容器總質(zhì)量不超過56kg．已知用作容器四壁的材料為20元/m2，重量為3kg；用作容器底的材料30/m2，重量為2kg。則制造該容器所需的最小成本是多少？問題分析由于該容器的底為正方形，故設(shè)底邊長為x1，高為x2，則該容器底部的面積為m2，四壁的側(cè)面積為4x1x2，該容器的容積為10m3可得，根據(jù)題意，容器底部的重量為kg，側(cè)面的重量為kg，由于容器的總質(zhì)量不得超過56kg，故可得約束關(guān)系，打造該容器的成本為底部的材料費和四壁的材料費之和，為，我們設(shè)計的目標是使得制造該容器的最小成本，即使得取得最小值。且考慮到容器的底和高均為非負實數(shù)，故綜合上述各式得到該最優(yōu)化問題的數(shù)學(xué)模型為：上述問題的目標函數(shù)為設(shè)計變量x1和x2的非線性函數(shù)，約束條件也為設(shè)計變量的x1和x2的非線性函數(shù)，為有約束的非線性規(guī)劃問題。第6頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃問題的數(shù)學(xué)模型一般形式非線性規(guī)劃問題涉及的領(lǐng)域非常廣泛，由實際的應(yīng)用問題建立起來的非線性規(guī)劃問題的具體形式也是各式各樣的，為了討論問題的方便，我們將其用統(tǒng)一的數(shù)學(xué)形式表達，簡單的說，均可以將問題轉(zhuǎn)化為求一個n維變量x的實函數(shù)f(x)的最大值或者最小值，同時受到一組約束的限制，這些約束可以是等式約束，也可以是不等式約束，其形式可以表達如下：式中，x是n維歐氏空間Rn中的向量，f(x)為目標函數(shù)，為約束條件。非線性規(guī)劃要求目標函數(shù)和約束條件中至少有一個是x的非線性函數(shù)。在后面的討論中，如果不特別指出，我們均采用上述標準模型。若令D為非線性規(guī)劃問題的可行解集合，即滿足所有約束關(guān)系的解的集合，則上述標準型也可以寫成如下形式：第7頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)等值面和等值線最優(yōu)化問題的目標函數(shù)f(x)為設(shè)計變量x的可計算函數(shù)，這主要表現(xiàn)在如下兩個方面：若給出一個設(shè)計方案，即設(shè)定一組x1,x2,…,xn的值，目標函數(shù)f(x)必有一確定的數(shù)值；若給出目標函數(shù)f(x)的值，則可能有無限多組x1,x2,…,xn數(shù)值與之對應(yīng)。也就是說，當(dāng)f(x)=c時，x在設(shè)計空間中有一個點集。一般情況下，把該點集稱為目標函數(shù)的等值面。顯然，在一個特定的等值面上，每個設(shè)計方案的目標函數(shù)值都是相等的。目標函數(shù)的等值面具有以下性質(zhì)不同值的等值面之間不相交；除了極值所在的等值面外，其余的等值面不會在區(qū)域的內(nèi)部中斷，這是因為目標函數(shù)都是連續(xù)函數(shù)；等值面稠密的地方，目標函數(shù)值變化較快，稀疏的地方變化較慢。第8頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)全局最優(yōu)解和局部最優(yōu)解非線性規(guī)劃問題的可行域把滿足非線性規(guī)劃中約束條件的解稱為可行解（或可行點），所有可行點的集合稱為可行集（或可行域），記為D。即局部極小值點對于非線性規(guī)劃問題，設(shè)，若存在，使得對一切，且，都有，則稱是f(x)在D上的局部極小值點（局部最優(yōu)解）特別的，當(dāng)時，若，則稱是f(x)在D上的嚴格局部極小值點（嚴格局部最優(yōu)解）全局極小值點對于非線性規(guī)劃問題，設(shè)，對任意的，都有，則稱是f(x)在D上的全局極小值點（全局最優(yōu)解）特別的，當(dāng)時，若，則稱是f(x)在D上的嚴格全局極小值點（嚴格全局最優(yōu)解）。第9頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)和凸規(guī)劃上述有關(guān)最優(yōu)化問題的極值點的定義描述了優(yōu)化問題中解的判斷條件，一般而言，我們的優(yōu)化過程實際上就是找極值點或者最值點的過程，但是上面的定義往往并不便于執(zhí)行，我們需要引入其他的手段進行分析和判斷，故我們首先介紹凸集、凸函數(shù)和凸規(guī)劃的概念，在這類特殊的問題之中，極值條件有著其特殊性。對于一個非線性規(guī)劃的目標函數(shù)，有局部極小值和全局極小值的概念，那么我們提出凸集和凸函數(shù)的概念就是為了區(qū)分目標函數(shù)的極小值在什么情況下是局部極小值，什么情況下是全局極小值。凸集設(shè)，若對于都有則稱T為凸集用形象一點的語言描述就是凸集的特征是集合中任兩點連成的線段必屬于這個集合。下圖是二維空間中具有典型特征的凸集和非凸集的例子。第10頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)和凸規(guī)劃

凸函數(shù)設(shè)f(x)是定義在非空凸集上的函數(shù)，若，都有，則稱f(x)為Ω上的凸函數(shù)。如果把上述“≤”換成“<”，則稱f(x)為Ω上的嚴格凸函數(shù)。同樣的，我們可以通過將上面條件中不等號變?yōu)椤啊荨被蛘摺?gt;”，則可以定義上的凹函數(shù)和嚴格凹函數(shù)。換一種表述方法，如果-f為Ω上的凸函數(shù)，則稱f為Ω上的凹函數(shù)。一元凸函數(shù)有明顯的幾何意義：過函數(shù)圖象上任意兩點的弦線段，處處都在函數(shù)圖象的上方，而凹函數(shù)的情形則正好相反第11頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)的性質(zhì)設(shè)為定義在凸集Ω上的凸函數(shù)，則所有凸函數(shù)的線性組合也為凸函數(shù)設(shè)Ω為Rn中的一個非空凸集，f(x)為定義在凸集Ω上的凸函數(shù)，λ是一個實數(shù)，則水平集是凸集。設(shè)Ω為Rn中的一個內(nèi)部非空的凸集，f(x)為定義在凸集Ω上的凸函數(shù)，則f(x)在Ω內(nèi)連續(xù)。當(dāng)函數(shù)一階或二階可微時，除了可以根據(jù)定義判斷其是否為凸（凹）函數(shù)外，更常用的辦法是使用即將介紹的一階和二階判別條件．這些條件中，有的是充要條件，有的僅僅是充分條件，在使用時要注意條件的性質(zhì)。凸函數(shù)的一階充要條件設(shè)Ω是Rn中的非空開凸集，f(x)是定義在Ω上的可微函數(shù)。那么，f(x)是Ω上的凸函數(shù)的充要條件是：對恒有第12頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)的性質(zhì)嚴格凸函數(shù)的一階充要條件凸函數(shù)的二階充要條件嚴格凸函數(shù)的二階充分條件第13頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)的性質(zhì)凸函數(shù)在其定義域上的任一極小點都是其在定義域上的全局極小點，且全體極小點的集合是凸集凸函數(shù)極小點的充分條件第14頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)的性質(zhì)第15頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)凸規(guī)劃第16頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)無約束非線性規(guī)劃問題的極值條件一元函數(shù)極值點存在的必要條件和充分條件多元函數(shù)極大值點的充要條件多元函數(shù)極小值點的充要條件第17頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃的理論基礎(chǔ)多維有約束非線性規(guī)劃問題的極值條件K-T條件一般的非線性規(guī)劃問題可以表述為：解上述問題的實質(zhì)是在所有的約束條件所形成的可行域內(nèi)，求得目標函數(shù)的極值點，即滿足約束條件的最優(yōu)點。由于約束最優(yōu)點不僅與目標函數(shù)本身的性質(zhì)有關(guān)，還與約束函數(shù)的性質(zhì)有關(guān)，因此約束條件下的優(yōu)化問題比無約束條件下的優(yōu)化問題更為復(fù)雜和難以求解。庫恩-塔克（Kuhn-Tucker）條件（簡稱K-T條件）是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，它是由H.W.Kuhn和A.W.Tucker在1951年提出的，我們通常借助庫恩-塔克條件來判斷和檢驗約束優(yōu)化問題中某個可行點是否為約束極值點，即將K-T條件作為確定一般非線性規(guī)劃問題中某點是否為極值點的必要條件，對于凸規(guī)劃問題，K-T條件同時也是一個充分條件。但是如何判別所找到的極值點是全域最優(yōu)點還是局部極值點，至今還沒有一個統(tǒng)一而有效的判別方法。第18頁，共23頁，2023年，2月20日，星期四非線性規(guī)劃問題的求解分類根據(jù)非線性規(guī)劃問題的目標函數(shù)和約束形式的類型，我們可以將非線性規(guī)劃問題可以分為無約束的非線性規(guī)劃問題（即目標函數(shù)是決策變量的非線性函數(shù)，沒有約束條件）和有約束的非線性規(guī)劃問題。其中，有約束非線性規(guī)劃問題要比無約束非線性規(guī)劃問題的求解困難得多。而且非線性規(guī)劃問題也不像線性規(guī)劃問題那樣有類似于單純形法的通用算法。對非線性規(guī)劃問題目前還沒有適用于各種問題的一般算法，它的各種算法都有自己特定的適用范圍。方法目前常見的無約束非線性規(guī)劃問題的算法有不基于梯度信息的坐標輪換法、或者是基于梯度信息的最速下降法、牛頓法、共軛方向法等等。而對于有約束的非線性規(guī)劃問題，求解有約束極值問題要比求解無約束極值問題困難得多。對極小化問題來說，除了要使目標函數(shù)經(jīng)每次迭代后有所下降之外，還要時刻注意解的可行性問題，這就給尋優(yōu)工作帶來了很大困難。為了簡化優(yōu)化工作，通常的做法是：盡量將非線性規(guī)劃問題化為線性規(guī)劃問題，將有約束問題化為無約束問題。第19頁，共23頁