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

1、非線性規(guī)劃基礎(chǔ)理論 第1頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四引言什么是非線性規(guī)劃線性規(guī)劃問(wèn)題和整數(shù)規(guī)劃問(wèn)題，其共同的特征是最優(yōu)化問(wèn)題中的目標(biāo)函數(shù)和約束條件均為設(shè)計(jì)變量的線性函數(shù)。但在實(shí)際建模過(guò)程中還有大量的問(wèn)題，其目標(biāo)函數(shù)或約束條件很難用線性函數(shù)來(lái)表達(dá)，當(dāng)目標(biāo)函數(shù)或約束條件中有一個(gè)以上是非線性函數(shù)時(shí)，就不能用線性的方法來(lái)處理，而要采用非線性的方法，那么我們稱(chēng)這種問(wèn)題為非線性規(guī)劃問(wèn)題非線性規(guī)劃的產(chǎn)生和發(fā)展 自從1951年H. W. Kuhn及A. W. Tucker探討了非線性規(guī)劃解的最優(yōu)性條件，為非線性規(guī)劃奠定了理論基礎(chǔ)之后，非線性規(guī)劃逐漸形成了一門(mén)十分重要且比較活躍的新興

2、學(xué)科，出現(xiàn)了許多解非線性規(guī)劃問(wèn)題的有效的算法。由70年代開(kāi)始，該分支得到迅速發(fā)展：理論方面，非線性規(guī)劃借鑒了數(shù)學(xué)理論中其他分支的成果，逐步形成自身的學(xué)科特色；在應(yīng)用方面，非線性規(guī)劃為系統(tǒng)的優(yōu)化和管理提供了有力的工具。隨著電子計(jì)算機(jī)的應(yīng)用，非線性規(guī)劃在最優(yōu)設(shè)計(jì)、管理科學(xué)、質(zhì)量控制等許多領(lǐng)域得到越來(lái)越深入的應(yīng)用。非線性規(guī)劃發(fā)展到今天，雖然已經(jīng)提出許多求解方法和策略，但是對(duì)于非線性規(guī)劃的最優(yōu)化問(wèn)題目前還沒(méi)有適于各種不同情況的一般算法，各個(gè)方法都有自己特定的適用范圍。因而，這是需要人們更深入的進(jìn)行研究的一個(gè)領(lǐng)域。 第2頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四典型的非線性規(guī)劃問(wèn)題 選址問(wèn)

3、題 問(wèn)題的提出 一家大型連鎖超市在某地有家分店 ，為了數(shù)學(xué)語(yǔ)言描述的方便，可在平面直角坐標(biāo)系給出其位置表述：A1的坐標(biāo)為(x1,y1)，A2的坐標(biāo)為(x2,y2) ，以此類(lèi)推， An的坐標(biāo)為(xn,yn) 。現(xiàn)在超市擬在當(dāng)?shù)剡x擇一個(gè)理想的位置建立一個(gè)供貨點(diǎn)，由于該超市各分店在經(jīng)營(yíng)規(guī)模上的不同，出貨量也不同，導(dǎo)致供貨點(diǎn)對(duì)各分店的送貨頻率不同，假設(shè)供貨點(diǎn)每周給Ai送貨的次數(shù)為ci(i=1,2,n)，同時(shí)假設(shè)每公里的運(yùn)輸費(fèi)保持定值m元/公里。那么超市應(yīng)當(dāng)把供貨點(diǎn)設(shè)在什么地方可以使得運(yùn)輸成本最低？問(wèn)題分析 假設(shè)供貨點(diǎn)坐標(biāo)為(x,y) ，那么由供貨點(diǎn)到某分店Ai的距離和運(yùn)輸費(fèi)分別為： 故運(yùn)輸?shù)目偝杀緸閷?duì)

4、各個(gè)分店運(yùn)輸成本的總和，整個(gè)問(wèn)題的數(shù)學(xué)模型可以表達(dá)為： 上述問(wèn)題的目標(biāo)函數(shù)為設(shè)計(jì)變量x和y的非線性函數(shù)，故為非線性規(guī)劃問(wèn)題，由于設(shè)計(jì)變量x和y不受任何條件的約束，故為無(wú)約束非線性規(guī)劃。第3頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四典型的非線性規(guī)劃問(wèn)題營(yíng)業(yè)計(jì)劃制定問(wèn)題 問(wèn)題的提出 某公司銷(xiāo)售兩種建材A和B以滿足市場(chǎng)的需要，生產(chǎn)建材A和B均要消耗資原材料M和N，其中每噸A建材需要消耗10噸M和18噸N，每噸B需要消耗20噸M和12噸N，已知產(chǎn)品的利潤(rùn)是銷(xiāo)售量的函數(shù)，現(xiàn)有原材料200噸M和100噸N，產(chǎn)品的售價(jià)、和資源的對(duì)應(yīng)關(guān)系如表所示，該公司應(yīng)當(dāng)如何制定生產(chǎn)銷(xiāo)售計(jì)劃使得銷(xiāo)售額最大。

5、消耗資源M(噸)消耗資源N(噸)單位售價(jià)(萬(wàn)元/噸)A11.8p1=5-0.01x1B21.2p2=6-0.03x2資源限制200100第4頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四典型的非線性規(guī)劃問(wèn)題營(yíng)業(yè)計(jì)劃制定問(wèn)題 問(wèn)題分析 設(shè)x1和x2為產(chǎn)品A和產(chǎn)品B的銷(xiāo)售量，由A的單價(jià)為p1，B的單價(jià)為p2，則可知公司的銷(xiāo)售收入為 ，在該例中，單位售價(jià)為銷(xiāo)量的函數(shù)，故由表中的公式可得 最優(yōu)化的目標(biāo)為使得銷(xiāo)售額最大，即取得最大值。由原材料的限制，可得約束條件為： 且考慮到和的產(chǎn)量應(yīng)當(dāng)為非負(fù)實(shí)數(shù)，故該問(wèn)題的數(shù)學(xué)模型為： 上述問(wèn)題的目標(biāo)函數(shù)為設(shè)計(jì)變量x1和x2的非線性函數(shù)，約束條件為設(shè)計(jì)變量的

6、x1和x2的線性函數(shù)，為有約束的非線性規(guī)劃問(wèn)題。 第5頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四典型的非線性規(guī)劃問(wèn)題容器設(shè)計(jì)問(wèn)題 問(wèn)題的提出 某工廠按照客戶(hù)的要求定制專(zhuān)門(mén)的儲(chǔ)藏用容器，訂貨合同要求該工廠制造一種敞口的長(zhǎng)方體容器，容積為10m3，該種容器的底必須為正方形，容器總質(zhì)量不超過(guò)56kg已知用作容器四壁的材料為20元/m2，重量為3kg；用作容器底的材料30/m2，重量為2kg。則制造該容器所需的最小成本是多少？ 問(wèn)題分析 由于該容器的底為正方形，故設(shè)底邊長(zhǎng)為x1，高為x2，則該容器底部的面積為 m2，四壁的側(cè)面積為4x1x2，該容器的容積為10m3可得 ，根據(jù)題意，容器底

7、部的重量為 kg，側(cè)面的重量為 kg，由于容器的總質(zhì)量不得超過(guò)56kg，故可得約束關(guān)系 ，打造該容器的成本為底部的材料費(fèi)和四壁的材料費(fèi)之和，為 ，我們?cè)O(shè)計(jì)的目標(biāo)是使得制造該容器的最小成本，即使得取得最小值。且考慮到容器的底和高均為非負(fù)實(shí)數(shù)，故綜合上述各式得到該最優(yōu)化問(wèn)題的數(shù)學(xué)模型為： 上述問(wèn)題的目標(biāo)函數(shù)為設(shè)計(jì)變量x1和x2的非線性函 數(shù)，約束條件也為設(shè)計(jì)變量的x1和x2的非線性函 數(shù)，為有約束的非線性規(guī)劃問(wèn)題。 第6頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型 一般形式非線性規(guī)劃問(wèn)題涉及的領(lǐng)域非常廣泛，由實(shí)際的應(yīng)用問(wèn)題建立起來(lái)的非線性規(guī)劃問(wèn)題的具體形式也是各

8、式各樣的，為了討論問(wèn)題的方便，我們將其用統(tǒng)一的數(shù)學(xué)形式表達(dá)，簡(jiǎn)單的說(shuō)，均可以將問(wèn)題轉(zhuǎn)化為求一個(gè)n維變量x的實(shí)函數(shù)f(x)的最大值或者最小值，同時(shí)受到一組約束的限制，這些約束可以是等式約束，也可以是不等式約束，其形式可以表達(dá)如下： 式中，x是n維歐氏空間Rn中的向量， f(x)為目標(biāo)函數(shù)， 為約束條件。非線性規(guī)劃要求目標(biāo)函數(shù)和約束條件中至少有一個(gè)是x的非線性函數(shù)。在后面的討論中，如果不特別指出，我們均采用上述標(biāo)準(zhǔn)模型。 若令D為非線性規(guī)劃問(wèn)題的可行解集合，即滿足所有約束關(guān)系的解的集合，則上述標(biāo)準(zhǔn)型也可以寫(xiě)成如下形式： 第7頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基

9、礎(chǔ) 等值面和等值線 最優(yōu)化問(wèn)題的目標(biāo)函數(shù)f(x)為設(shè)計(jì)變量x的可計(jì)算函數(shù)，這主要表現(xiàn)在如下兩個(gè)方面： 若給出一個(gè)設(shè)計(jì)方案，即設(shè)定一組x1,x2,xn的值，目標(biāo)函數(shù)f(x)必有一確定的數(shù)值；若給出目標(biāo)函數(shù)f(x)的值，則可能有無(wú)限多組x1,x2,xn數(shù)值與之對(duì)應(yīng)。也就是說(shuō)，當(dāng)f(x)=c時(shí)，x在設(shè)計(jì)空間中有一個(gè)點(diǎn)集。一般情況下，把該點(diǎn)集稱(chēng)為目標(biāo)函數(shù)的等值面。顯然，在一個(gè)特定的等值面上，每個(gè)設(shè)計(jì)方案的目標(biāo)函數(shù)值都是相等的。目標(biāo)函數(shù)的等值面具有以下性質(zhì) 不同值的等值面之間不相交；除了極值所在的等值面外，其余的等值面不會(huì)在區(qū)域的內(nèi)部中斷，這是因?yàn)槟繕?biāo)函數(shù)都是連續(xù)函數(shù)；等值面稠密的地方，目標(biāo)函數(shù)值變化較

10、快，稀疏的地方變化較慢。 第8頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ)全局最優(yōu)解和局部最優(yōu)解 非線性規(guī)劃問(wèn)題的可行域 把滿足非線性規(guī)劃中約束條件的解稱(chēng)為可行解（或可行點(diǎn)），所有可行點(diǎn)的集合稱(chēng)為可行集（或可行域），記為D。即局部極小值點(diǎn) 對(duì)于非線性規(guī)劃問(wèn)題，設(shè) ，若存在 ，使得對(duì)一切 ，且 ，都有 ，則稱(chēng) 是f(x)在D上的局部極小值點(diǎn)（局部最優(yōu)解） 特別的，當(dāng) 時(shí)，若 ，則稱(chēng) 是f(x)在D上的嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最優(yōu)解） 全局極小值點(diǎn) 對(duì)于非線性規(guī)劃問(wèn)題，設(shè) ，對(duì)任意的 ，都有 ，則稱(chēng) 是f(x)在D上的全局極小值點(diǎn)（全局最優(yōu)解） 特別的，當(dāng) 時(shí)，若

11、 ，則稱(chēng) 是f(x)在D上的嚴(yán)格全局極小值點(diǎn)（嚴(yán)格全局最優(yōu)解）。 第9頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)和凸規(guī)劃 上述有關(guān)最優(yōu)化問(wèn)題的極值點(diǎn)的定義描述了優(yōu)化問(wèn)題中解的判斷條件，一般而言，我們的優(yōu)化過(guò)程實(shí)際上就是找極值點(diǎn)或者最值點(diǎn)的過(guò)程，但是上面的定義往往并不便于執(zhí)行，我們需要引入其他的手段進(jìn)行分析和判斷，故我們首先介紹凸集、凸函數(shù)和凸規(guī)劃的概念，在這類(lèi)特殊的問(wèn)題之中，極值條件有著其特殊性。 對(duì)于一個(gè)非線性規(guī)劃的目標(biāo)函數(shù)，有局部極小值和全局極小值的概念，那么我們提出凸集和凸函數(shù)的概念就是為了區(qū)分目標(biāo)函數(shù)的極小值在什么情況下是局部極小值，什么情況下是

12、全局極小值。凸集 設(shè) ，若對(duì)于 都有 則稱(chēng)T為凸集 用形象一點(diǎn)的語(yǔ)言描述就是凸集的特征是集合中任兩點(diǎn)連成的線段必屬于這個(gè)集合。下圖是二維空間中具有典型特征的凸集和非凸集的例子。 第10頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)和凸規(guī)劃 凸函數(shù) 設(shè)f(x)是定義在非空凸集 上的函數(shù)，若 ，都有 ，則稱(chēng)f(x)為上的凸函數(shù)。 如果把上述“”換成“”，則可以定義上的凹函數(shù)和嚴(yán)格凹函數(shù)。換一種表述方法，如果-f為上的凸函數(shù)，則稱(chēng)f為上的凹函數(shù)。 一元凸函數(shù)有明顯的幾何意義：過(guò)函數(shù)圖象上任意兩點(diǎn)的弦線段，處處都在函數(shù)圖象的上方，而凹函數(shù)的情形則正好相反 第11頁(yè)，

13、共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)的性質(zhì)設(shè) 為定義在凸集上的凸函數(shù)，則 所有凸函數(shù)的線性組合 也為凸函數(shù)設(shè)為Rn中的一個(gè)非空凸集， f(x)為定義在凸集上的凸函數(shù)，是一個(gè)實(shí)數(shù)，則水平集 是凸集。設(shè)為Rn中的一個(gè)內(nèi)部非空的凸集， f(x)為定義在凸集上的凸函數(shù)，則f(x)在內(nèi)連續(xù)。 當(dāng)函數(shù)一階或二階可微時(shí)，除了可以根據(jù)定義判斷其是否為凸（凹）函數(shù)外，更常用的辦法是使用即將介紹的一階和二階判別條件這些條件中，有的是充要條件，有的僅僅是充分條件，在使用時(shí)要注意條件的性質(zhì)。 凸函數(shù)的一階充要條件 設(shè)是Rn中的非空開(kāi)凸集， f(x)是定義在上的可微函數(shù)。那么，

14、 f(x)是上的凸函數(shù)的充要條件是：對(duì) 恒有 第12頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)的性質(zhì)嚴(yán)格凸函數(shù)的一階充要條件 凸函數(shù)的二階充要條件嚴(yán)格凸函數(shù)的二階充分條件第13頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ)凸函數(shù)的性質(zhì)凸函數(shù)在其定義域上的任一極小點(diǎn)都是其在定義域上的全局極小點(diǎn)，且全體極小點(diǎn)的集合是凸集凸函數(shù)極小點(diǎn)的充分條件 第14頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ) 凸函數(shù)的性質(zhì)第15頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ)凸規(guī)劃第1

15、6頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ)無(wú)約束非線性規(guī)劃問(wèn)題的極值條件一元函數(shù)極值點(diǎn)存在的必要條件和充分條件 多元函數(shù)極大值點(diǎn)的充要條件 多元函數(shù)極小值點(diǎn)的充要條件 第17頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃的理論基礎(chǔ)多維有約束非線性規(guī)劃問(wèn)題的極值條件 K-T條件 一般的非線性規(guī)劃問(wèn)題可以表述為： 解上述問(wèn)題的實(shí)質(zhì)是在所有的約束條件所形成的可行域內(nèi)，求得目標(biāo)函數(shù)的極值點(diǎn)，即滿足約束條件的最優(yōu)點(diǎn)。由于約束最優(yōu)點(diǎn)不僅與目標(biāo)函數(shù)本身的性質(zhì)有關(guān)，還與約束函數(shù)的性質(zhì)有關(guān)，因此約束條件下的優(yōu)化問(wèn)題比無(wú)約束條件下的優(yōu)化問(wèn)題更為復(fù)雜和難以求解

16、。 庫(kù)恩-塔克（Kuhn-Tucker）條件（簡(jiǎn)稱(chēng)K-T條件）是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，它是由H. W. Kuhn和A. W. Tucker在1951年提出的，我們通常借助庫(kù)恩-塔克條件來(lái)判斷和檢驗(yàn)約束優(yōu)化問(wèn)題中某個(gè)可行點(diǎn)是否為約束極值點(diǎn)，即將K-T條件作為確定一般非線性規(guī)劃問(wèn)題中某點(diǎn)是否為極值點(diǎn)的必要條件，對(duì)于凸規(guī)劃問(wèn)題，K-T條件同時(shí)也是一個(gè)充分條件。但是如何判別所找到的極值點(diǎn)是全域最優(yōu)點(diǎn)還是局部極值點(diǎn)，至今還沒(méi)有一個(gè)統(tǒng)一而有效的判別方法。第18頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃問(wèn)題的求解分類(lèi)根據(jù)非線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)和約束形式的類(lèi)型，我們可

17、以將非線性規(guī)劃問(wèn)題可以分為無(wú)約束的非線性規(guī)劃問(wèn)題（即目標(biāo)函數(shù)是決策變量的非線性函數(shù)，沒(méi)有約束條件）和有約束的非線性規(guī)劃問(wèn)題。其中，有約束非線性規(guī)劃問(wèn)題要比無(wú)約束非線性規(guī)劃問(wèn)題的求解困難得多。而且非線性規(guī)劃問(wèn)題也不像線性規(guī)劃問(wèn)題那樣有類(lèi)似于單純形法的通用算法。對(duì)非線性規(guī)劃問(wèn)題目前還沒(méi)有適用于各種問(wèn)題的一般算法，它的各種算法都有自己特定的適用范圍。方法目前常見(jiàn)的無(wú)約束非線性規(guī)劃問(wèn)題的算法有不基于梯度信息的坐標(biāo)輪換法、或者是基于梯度信息的最速下降法、牛頓法、共軛方向法等等。而對(duì)于有約束的非線性規(guī)劃問(wèn)題，求解有約束極值問(wèn)題要比求解無(wú)約束極值問(wèn)題困難得多。對(duì)極小化問(wèn)題來(lái)說(shuō)，除了要使目標(biāo)函數(shù)經(jīng)每次迭代后有

18、所下降之外，還要時(shí)刻注意解的可行性問(wèn)題，這就給尋優(yōu)工作帶來(lái)了很大困難。為了簡(jiǎn)化優(yōu)化工作，通常的做法是：盡量將非線性規(guī)劃問(wèn)題化為線性規(guī)劃問(wèn)題，將有約束問(wèn)題化為無(wú)約束問(wèn)題。第19頁(yè)，共23頁(yè)，2022年，5月20日，3點(diǎn)49分，星期四非線性規(guī)劃問(wèn)題的求解具體解法直接法 直接法是一種數(shù)值方法，其原理是利用函數(shù)的局部性質(zhì)和一些已知點(diǎn)的函數(shù)值，來(lái)確定下一步的迭代點(diǎn)，循環(huán)往復(fù)，以一定的條件作為迭代結(jié)束條件，求取函數(shù)極值。此類(lèi)方法的典型代表有基于梯度信息的一類(lèi)迭代方法，如牛頓法、變尺度算法等。對(duì)于目標(biāo)函數(shù)難以用解析式表達(dá)的問(wèn)題，這種方法較適用。解析法 解析法則是按照函數(shù)極值的必要條件，用數(shù)學(xué)分析的方法求出其相應(yīng)的解析解，再按照充分條件確定最優(yōu)解，如梯度投影法、容許方向法等。對(duì)于目標(biāo)函數(shù)是設(shè)計(jì)變量的顯函數(shù)，且解析性質(zhì)較好的這樣一類(lèi)問(wèn)題，這種方法較合適。用線性規(guī)劃或二次規(guī)劃逼近的方法 這是一種近似求解的方法。前者是將非線性規(guī)劃問(wèn)題在某個(gè)近似解處將約束條件和目標(biāo)函數(shù)展開(kāi)成泰勒級(jí)數(shù)，略去其二次項(xiàng)及二次以上的項(xiàng)，使約束條件和目標(biāo)函數(shù)都成為線性的，原來(lái)的問(wèn)題就用這個(gè)線性問(wèn)題來(lái)近似代替。這種算法比較適合求解變量和約束較多，但只有少量約束是非線性的規(guī)劃問(wèn)題；二次規(guī)劃適合于約