非線性規(guī)劃的概念和原理

1、第五章非線性規(guī)劃的概念和原理非線性規(guī)劃的理論是在線性規(guī)劃的基礎(chǔ)上發(fā)展起來的。1951年，庫恩(H.W.Kuhn)和 塔克(A.W.Tucker)等人提出了非線性規(guī)劃的最優(yōu)性條件，為它的發(fā)展奠定了基礎(chǔ)。以后隨 著電子計算機(jī)的普遍使用，非線性規(guī)劃的理論和方法有了很大的發(fā)展，其應(yīng)用的領(lǐng)域也越來 越廣泛，特別是在軍事，經(jīng)濟(jì)，管理，生產(chǎn)過程自動化，工程設(shè)計和產(chǎn)品優(yōu)化設(shè)計等方面都 有著重要的應(yīng)用。一般來說，解非線性規(guī)劃問題要比求解線性規(guī)劃問題困難得多，而且也不像線性規(guī)劃那 樣有統(tǒng)一的數(shù)學(xué)模型及如單純形法這一通用解法。非線性規(guī)劃的各種算法大都有自己特定的 適用范圍。都有一定的局限性，到目前為止還沒有適合于各

2、種非線性規(guī)劃問題的一般算法。 這正是需要人們進(jìn)一步研究的課題。5.1非線性規(guī)劃的實例及數(shù)學(xué)模型例題6.1投資問題:假定國家的下一個五年計劃內(nèi)用于發(fā)展某種工業(yè)的總投資為b億元，可供選擇興建的項 目共有幾個。已知第j個項目的投資為.億元，可得收益為匕億元，問應(yīng)如何進(jìn)行投資， 才能使盈利率(即單位投資可得到的收益)為最高？解：令決策變量為，則應(yīng)滿足條件Xj 1廣1)= 0同時x應(yīng)滿足約束條件W a x_ bj=1乙X1,1j j最大。a xj jj=1例題6.2廠址選擇問題：設(shè)有n個市場，第j個市場位置為(七,),它對某種貨物的需要量為bj (j = 1,2, ,n)o 現(xiàn)計劃建立m個倉庫，第i個倉

3、庫的存儲容量為aj (i = 1,2, ,m)。試確定倉庫的位置，使 各倉庫對各市場的運輸量與路程乘積之和為最小。.解：設(shè)第i個倉庫的位置為(土,七.)(i = 12,m)，第i個倉庫到第j個市場的貨物供應(yīng)量為乙一 (i = 1,2, ,m, j = 1,2,n)，則第i個倉庫到第j個市場的距離為d = ： 1 - p 2 +(-q)目標(biāo)函數(shù)為乙.二二,i=1 j=1i=1 j=1約束條件為：(1)(2)(3)i j(i = 1,2,每個倉庫向各市場提供的貨物量之和不能超過它的存儲容量; 每個市場從各倉庫得到的貨物量之和應(yīng)等于它的需要量； 運輸量不能為負(fù)數(shù)。因此，問題的數(shù)學(xué)模型為：min z

4、y(x -p)2 + (y -q)2i j t i ji ji=1 j=1s.t.乙.a,j=1Y z 0,(i = 1,2,m, j = 1,2, ,n)一般非線性規(guī)劃的數(shù)學(xué)模型可表示為：min f (x)；s.t. g,(X) 0 (i = 1,2,m),七(X)= 0,(j = 1,2,l)式中 X =(x,x , ,xg Rn 是 n 維向量，f, g. (i= 1,2；,m)，h(j= 1,2,l)都是12nIjRn - R1的映射(即自變量是n維向量，因變量是實數(shù)的函數(shù)關(guān)系)，且其中至少存在一個非線性映射。與線性規(guī)劃類似，把滿足約束條件的解稱為可行解。若記X =匕站(X ) 0,

5、i = 1,2, ,m, hj (X )= 0, j = 1,2, ,l則稱X為可行域。因此上述模型可簡記為.min f (X )s.t. X gx當(dāng)一個非線性規(guī)劃問題的自變量X沒有任何約束，或說可行域即是整個n維向量空間,即穴=Rn，則稱這樣的非線性規(guī)劃問題為無約束問題:min f(X )或 min f (X )X eRn有約束問題與無約束問題是非線性規(guī)劃的兩大類問題，它們在處理方法上有明顯的不 同。5.2無約束非線性規(guī)劃問題5.2.1無約束極值條件對于二階可微的一元函數(shù)f (x)，如果x*是局部極小點，則f ,(x *)= 0，并且 f，(x*) 0；反之，如果f r(x*)= 0，f r

6、r(x*)。5.2.3無約束極值問題的解法5.2.3.1梯度法（i）給定初始點X（。）， 0 ；，迭代停止，得近似極小點（ii）計算 f （x（k）和 Vf （x（k） X（k）和近似極小值f （X（k）；否則，進(jìn)行下一步;（iii） 做一維搜索或取入 kW （x a） w （x a）（V一（）（一作為近似最佳步長， Vfx （k），v 2 f X （k） Pfx （W并計算 X（k+i） = X（k）一人kNf Q（k），令k = k +1，轉(zhuǎn)向第二步。例題6.4求解無約束極值問題min f （X ）=（氣-2 ）2 +（%2 -1）2 解：取X （0 ）= （0,0，Vf （X）=（2（氣

7、-2）,2（氣一1，則Vf（X（0）= （一4, 一2，V2f（X（0）=Vf（x（0）vf（x（0）1Vf（X（0）v 2 f （x（0）vf（X（0）= 2， X（1）= X （0 ）-X 0Vf G（0）= （2,1 ，Vf（X（1）=（0,0，故x（1）為極值點，極小值為fG（1）=0。5.2.3.2牛頓法對正定二次函數(shù)，f （x）= XtAx + Btx + c，其中A為n階方陣，B為n維列向量， c為常數(shù)，設(shè)X*為其極小點，則Vf （X *）= AX *+ B = 0，所以AX * = -B ；任給X（0）e En， Vf G（0）= AX（0）+ B，消去 B，得Vf G（0）=

8、 AX（0）一 AX *所以 X* = X（。）- A-iVf （X（。），點。步長為1，一步即可達(dá)極小這說明，從任意近似點出發(fā)，沿-A-iVf （x（。）方向搜索，例題6.5求解無約束極值問題minf （X）=工2 + 5偵A-i =解：任取 X（。）=（2,1，Vf （X（。）=（4,1。X * = X （0） - A-iVf G（。）= （0,。由 Vf （X *）=（。,。）t 可知，x *確實為極小點。牛頓法與梯度法的搜索方向不同，優(yōu)點是收斂速度快，但有時不好用而需采取改進(jìn)措施，當(dāng)維數(shù)較高時，A-i的計算量很大。5.3約束非線性規(guī)劃問題前面我們介紹了無約束問題的最優(yōu)化方法，但實際問題

9、中，大多數(shù)都是有約束條件的問 題。求解帶有約束條件的問題比起無約束問題要困難得多，也復(fù)雜得多。在每次迭代時，不 僅要使目標(biāo)函數(shù)值有所下降，而且要使迭代點都落在可行域內(nèi)（個別算法除外）。求解帶有 約束的極值問題常用方法是：將約束問題化為一個或一系列的無約束極值問題；將非線性規(guī) 劃化為近似的線性規(guī)劃；將復(fù)雜問題變?yōu)檩^簡單問題等等。5.3.1凸規(guī)劃問題約束問題的情況較為復(fù)雜，先討論其中的一種較為特殊的情況，即凸規(guī)劃問題。一般來說，非線性規(guī)劃的局部最優(yōu)解和全局最優(yōu)解是不同的，但是，對凸規(guī)劃問題，局 部最優(yōu)解就是全局最優(yōu)解。定義6.1設(shè)f （X）為定義在非空凸集S匚En上的實值函數(shù)，如果對于任意的兩點X

10、 （i） e S， X（2） e S和任意實數(shù)人el。），恒有f GX（i） + （i-X）X（2）Xf （x（i）+（i-Df （x（2）則稱f （x）為S上的凸函數(shù)。定理6.4設(shè)S是n維歐氏空間E上的一個開凸集，/（X）是定義在S上的具有二階連 續(xù)導(dǎo)數(shù)的函數(shù)，那么，/（X）在S上為凸函數(shù)的充要條件是：對所有XeS,海賽矩陣 V2/（X）都是半正定的；如果對所有的XeS, V2/（X）都是正定的，則f（X）在s上 為嚴(yán)格凸函數(shù)。定義6.2非線性規(guī)劃問題：min/（x）, X eEns.t. g（X）VO, i = 1,2, ,mih（X）= O, j= 1/2, pj中，如果 f （x）和

11、g （x） （i = l,2, ,m）為 x 的凸函數(shù),3 （x）（頂= 1,2, ,p ）為XiJ的線性函數(shù)，則稱此問題為一凸規(guī)劃問題。.凸規(guī)劃具有兩個重要性質(zhì):1.凸規(guī)劃的可行集是凸集證：設(shè)凸規(guī)劃的可行集為s,即Rg（X）VO” = 1,2, ,m;h（X）=O” = 1,2, ,p; XeE ijn其中g(shù)（X）（，二 1,2, ,m）為X的凸函藪，h （x）（頂二 1,2,，萬）為X的線性函數(shù)。，j對于任意的x（共S, X（2）eS和任意實數(shù)人6（0,1）,利用彳（x） （i = l,2, ,m）i的凸性，對X=X（1）+ （1人）x（2）,有g(shù)（x） 二i但g（x（i）vo, g （i

12、i所以g （x）oi同理/z（X）= Ojg Gx（i）+ （1一人）x（2）v*g（X（1）+（1 Dg（x（2）iiX（2）VO因此，X=2iX（i）+ （l人）x（2）es,故s 為凸集。2.凸規(guī)劃的局部最小解就是它的全局最小解證：用反證法。設(shè)X*是凸規(guī)劃的一個局部最小解，又是它的全局最小解，但X。X*。 因為 X * S，X G S，所以 VX e(0,1), X =XX *+(1人)X e S 由 f (X)為凸函數(shù)得，f (X)= f (XX*+(1 X)X)Xf (X*)+(1 X)f (X)因為X是一個全局最小解，所以f (X )X f (X *)+(1 x) f (X ) 0

13、112g (X )= x2 + x 1 0 g4 (X)= x2 0解：第1，3, 4三個約束條件為線性函數(shù)，因此也是凸函數(shù);您(X)dx2第2個約束條件應(yīng)寫成g2 (X)=氣2 x2 +1 0, i = 1,2, ,m或?qū)懗?min f (X )X e/其中可行域 X = XI X e En, g (X) 0,i = 1,2, ,m。i定義6.3對于上述問題，設(shè)X e/，若有g(shù)i (X )= 0 (1 i 0為點X處的起作用約束；若有g(shù)i (X ) 0 (1 i 0為點X處的不起作用約束。定義6.4對于上述非線性規(guī)劃問題，如果可行點X處，各起作用約束的梯度向量線性無 關(guān)，則稱X是約束條件的一

14、個正則點。庫恩一塔克條件是非線性規(guī)劃領(lǐng)域中的重要理論成果之一，是確定某點為局部最優(yōu)解的 一階必要條件，只要是最優(yōu)點就必滿足這個條件。但一般來說它不是充分條件，即滿足這個 條件的點不一定是最優(yōu)點。但對于凸規(guī)劃，庫恩塔克條件既是必要條件，也是充分條件。對于只含有不等式約束的非線性規(guī)劃問題，有定理如下：定理6.5設(shè)X *是非線性規(guī)劃問題min f(X)X以X =XIXwE，g (X)0,/ = l,2,.,mi的極小點，若X*起作用約束的梯度Vg(X*)線性無關(guān)(即X*是一個正則點)，則 i*=(/*,丫*, ，丫*),使下式成立12mW(X*)-u Y* -Vg (X*) = 0i ii=l 0,

15、 z =i對同時含有等式與不等式約束的問題minf (%)；s.t. g(X)O G = 1,2, ,m),ih(X)=O,(y = l,2,/)j為了利用以上定理，將久(X)=0,用j/z (x)o0i j來代替。這樣即可得到同時含有等式與不等式約束條件的庫恩塔克條件如下：設(shè)X*為上述問題的極小點，若X*起作用約束的梯度Vg和WZj(x*)線性無關(guān),則m*=G*,y*, ，丫*)和*=(*,人*,，人*),使下式成立12m12m, fW(X*)-(X*)-2a* -V/z (X*) = 0i ij jZ=1j=l 0,z = 1,2,-,m例題6.7求下列非線性規(guī)劃問題的K-T點：min f

16、 (X ) = 2x2 + 2xx + x2 -10 x - 10 x解：將上述問題的約束條件改寫為g（X）0的形式:ig (X ) =-x 2 - x 2 + 5 0g (X ) = 3x x + 6 0Nf(X*)二設(shè)5點為X *=（x1，x2 ，有4 x + 2 x -101 22 x1 + 2 x2 -10由定理得Vgi (x *)二Ng2 (X *)=-2 xQ 1-2 x23-14x + 2x -10 + 2 x + 3 = 02x + 2x -10 + 2yx +y = 01(2 1 22y V5 - x2 - x2 )= 0y 2 (63尤-x2 )=0/ 01y2 0求解上述

17、方程組即可求出y 1 y 2 ,x1，x2 ,則可得到滿足K-T條件的點。上述方程組是非線性方程組，求解時一般都要利用松緊條件（即上述方程組中的第3 4個方程），其實質(zhì)是分析X *點處，哪些是不起作用約束，以便得到y(tǒng) i = 0,這樣分情況討論求解較為容易:（1）假設(shè)兩個約束均是X *點處的不起作用約束，即有則有4 x + 2 x -10 = 02 x + 2 x -10 = 012解得x1 = 0 x = 52但將該點代入約束條件，不滿足gj（X） 0，因此該點不是可行點。（2）若g1（X）0是起作用約束，g2（X）0是不起作用約束，則有Y2=。，則4 尤+ 2 x -10 + 2y x = 02 x + 2 x -10 + 2 x = 0121 25 - x2 - x2 ）= 01 1 2 0 1x1=1x = 2解得0是起作用約束，此時V 0，可以是V0，也可以是V= 0，若V= 0也成立，則結(jié)果同（1），已知求出的解不是可行點。（3）若g （X ） 0是不起作用約束，g 2 （X ） 0是起作用約束，即有V1 = 0，代入方程組，有4 x + 2 x -10 + 3丫 = 02； + 2； -1