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

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

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

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

4、各個分店運輸成本的總和，整個問題的數(shù)學模型可以表達為： 上述問題的目標函數(shù)為設計變量x和y的非線性函數(shù)，故為非線性規(guī)劃問題，由于設計變量x和y不受任何條件的約束，故為無約束非線性規(guī)劃。第3頁，共23頁，2022年，5月20日，3點49分，星期四典型的非線性規(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)品的售價、和資源的對應關系如表所示，該公司應當如何制定生產(chǎn)銷售計劃使得銷售額最大。

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

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

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

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

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

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

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

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

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

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

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

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

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

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