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

第五章非線性規(guī)劃的概念和原理非線性規(guī)劃的理論是在線性規(guī)劃的基礎(chǔ)上發(fā)展起來的。1951年，庫恩(H.W.Kuhn)和塔克(A.W.Tucker)等人提出了非線性規(guī)劃的最優(yōu)性條件，為它的發(fā)展奠定了基礎(chǔ)。以后隨著電子計算機的普遍使用，非線性規(guī)劃的理論和方法有了很大的發(fā)展，其應(yīng)用的領(lǐng)域也越來越廣泛，特別是在軍事，經(jīng)濟，管理，生產(chǎn)過程自動化，工程設(shè)計和產(chǎn)品優(yōu)化設(shè)計等方面都有著重要的應(yīng)用。一般來說，解非線性規(guī)劃問題要比求解線性規(guī)劃問題困難得多，而且也不像線性規(guī)劃那樣有統(tǒng)一的數(shù)學模型及如單純形法這一通用解法。非線性規(guī)劃的各種算法大都有自己特定的適用范圍。都有一定的局限性，到目前為止還沒有適合于各種非線性規(guī)劃問題的一般算法。這正是需要人們進一步研究的課題。非線性規(guī)劃的實例及數(shù)學模型[例題6.1]投資問題：假定國家的下一個五年計劃內(nèi)用于發(fā)展某種工業(yè)的總投資為b億元，可供選擇興建的項目共有幾個。已知第j個項目的投資為a億元，可得收益為c億元，問應(yīng)如何進行投資，jj才能使盈利率(即單位投資可得到的收益)為最高？解：令決策變量為x，則x應(yīng)滿足條件xC-1)=0jjjj同時x應(yīng)滿足約束條件2ax<bjjjj=1另ex目標函數(shù)是要求盈利率f目標函數(shù)是要求盈利率f(x,x,x)=12 最大。axjjj=1[例題6.2]廠址選擇問題：設(shè)有n個市場，第j個市場位置為(p,q)，它對某種貨物的需要量為b(j=12…,n)。jjj現(xiàn)計劃建立m個倉庫，第i個倉庫的存儲容量為a.C=1,2,…,m)。試確定倉庫的位置，使各倉庫對各市場的運輸量與路程乘積之和為最小。解：設(shè)第i個倉庫的位置為(x,y)(i=12…,m)，第i個倉庫到第j個市場的貨物供lI應(yīng)量為z(l=1,2,…,m,j=1,2,…,n)，則第i個倉庫到第j個市場的距離為ijd=<\x-p/+(y-q/ij ij ij目標函數(shù)為目標函數(shù)為i=1j=1zi=1j=1zijijiji=1j=1約束條件為：每個倉庫向各市場提供的貨物量之和不能超過它的存儲容量每個市場從各倉庫得到的貨物量之和應(yīng)等于它的需要量；運輸量不能為負數(shù)。因此，問題的數(shù)學模型為：min乞Kz p丄+(y-q丄minijij iji=1j=1s.t.Ks.t.Kz<aijij=1(i=1,2,…,m)Kz<b,(j=1,2,…,n)ijji=1z>0,(i=1,2,…,m,j=1,2,…,n)ij一般非線性規(guī)劃的數(shù)學模型可表示為：minf(x)；s.t.g(X)>0(i=1,2,…,m),ih(X)=0,(j=1,2,…,l)j式中X=(x,x,…,x)teRn是n維向量，f,g.(i=1,2,…,m),h(j=1,2,…,l)都是1 2 n i jRnTR1的映射(即自變量是n維向量，因變量是實數(shù)的函數(shù)關(guān)系)，且其中至少存在一個非線性映射。與線性規(guī)劃類似，把滿足約束條件的解稱為可行解。若記X={x|g(X)>0,i=1,2,???,m,hj(X)=0,j=1,2,…,/}則稱X為可行域。因此上述模型可簡記為minf(X)s.t.XeX當一個非線性規(guī)劃問題的自變量X沒有任何約束，或說可行域即是整個n維向量空間,

即咒二Rn，則稱這樣的非線性規(guī)劃問題為無約束問題：minf(X)或XeRn有約束問題與無約束問題是非線性規(guī)劃的兩大類問題，它們在處理方法上有明顯的不同。無約束非線性規(guī)劃問題5.2.1無約束極值條件對于二階可微的一元函數(shù)f(x)，如果x*是局部極小點，則f'C*)=0，并且"C)>o；反之，如果廣C*)=0，廠0<0，則x*是局部極大點。關(guān)于多元函數(shù),也有與此類似的結(jié)果，這就是下述的各定理?？紤]無約束極值問題：minf(x)，xeEn定理6?1(必要條件)設(shè)f(x)是n元可微實函數(shù)，如果x*是以上問題的局部極小解,則Vf(x*)=0。定理6.2(充分條件)設(shè)f(x)是n元二次可微實函數(shù)，如果x*是上述問題的局部最小解,則VfC)=0，V2f(x*)半正定；反之，如果在x*點有Vf(x*)=0，V2fC)正定,則x*為嚴格局部最小解。定理6.3設(shè)f(x)是n元可微凸函數(shù)，如果VfC)=0，則x*是上述問題的最小解。［例題6?3］試求二次函數(shù)f(xi,x2)=2xi2-8xi+2x22-4x2+20的極小點。解：由極值存在的必要條件求出穩(wěn)定點：=4x一8， =4x一4，則由Vf(x)=0得x=2，x=1dx 1 Qx 2 1 212再用充分條件進行檢驗：Q2f再用充分條件進行檢驗：Q2f=4=4Q2fQx2 Qx2 QxQx1212Q2fQxQx210，則由V2f=0)4丿為正定矩陣得極小點為x*=(2，1)t。5.2.3無約束極值問題的解法5.2.3.1梯度法2迭代停止，得近似極小點給定初始點X(o)，￡>0；2迭代停止，得近似極小點rR計算/(x(k))和Vf(x(k)),若||VfX()和近似極小值f(X())；否則，進行下一歹；rRVf(X(k))TVf(X(k))(iii) 做一維搜索或取九=—() ()作為近似最佳步長,kVfX(k)TV2fX(k)VfX(k)并計算X(k+i)=X(k)—九VfC(k)),令k=k+1，轉(zhuǎn)向第二步。k［例題6.4］求解無約束極值問題min/(X)=(x-2)2+(x-1)2解：取X解：取X(。)=(0,0>,Vf(X)=G(x—2),2(x—1)》，則21Vf(X(0))=(—4,—2)T，V2f(X(0))='20、<02>Vf(X(0))TVf(X(0)) 1VfCx(0))V2fCx(0)爲(X(0))2X(1)=X(0)—九Vf(X(0))=(2,1),0Vf(X(1))=(0,0)T，故X(1)為極值點，極小值為fC(1))=0。5.2.3.2牛頓法對正定二次函數(shù)，f(X)=2XtAX+BtX+c,其中A為n階方陣，B為n維列向量,c為常數(shù)，設(shè)X*為其極小點，則Vf(X*)=AX*+B=0，所以AX*=—B；任給X(o)eEn,Vf(x(o))=AX(o)+B，消去B,得Vf(x(o))=AX(o)—AX*

所以X*=X（0）-A-iVf（X（0））,步長為1，一步即可達極小這說明，從任意近似點出發(fā)，沿-A-iVf（X（0）步長為1，一步即可達極小點。點。［例題6.5］求解無約束極值問題minf（X）=x2+5x212解：任取X解：任取X（0）=（2,1>,Vf（X（0））=（4,10>,A=0、10丿,At=X*=X（0）-A-iVf（X（0））=（0,0）T由Vf（X*）=（0,0）t可知，x*確實為極小點。牛頓法與梯度法的搜索方向不同，優(yōu)點是收斂速度快，但有時不好用而需采取改進措施，當維數(shù)較高時，A-1的計算量很大。約束非線性規(guī)劃問題前面我們介紹了無約束問題的最優(yōu)化方法，但實際問題中，大多數(shù)都是有約束條件的問題。求解帶有約束條件的問題比起無約束問題要困難得多，也復雜得多。在每次迭代時，不僅要使目標函數(shù)值有所下降，而且要使迭代點都落在可行域內(nèi)（個別算法除外）。求解帶有約束的極值問題常用方法是：將約束問題化為一個或一系列的無約束極值問題；將非線性規(guī)劃化為近似的線性規(guī)劃；將復雜問題變?yōu)檩^簡單問題等等。5.3.1凸規(guī)劃問題約束問題的情況較為復雜，先討論其中的一種較為特殊的情況，即凸規(guī)劃問題。一般來說，非線性規(guī)劃的局部最優(yōu)解和全局最優(yōu)解是不同的，但是，對凸規(guī)劃問題，局部最優(yōu)解就是全局最優(yōu)解。定義6?1設(shè)f（X）為定義在非空凸集S匸En上的實值函數(shù)，如果對于任意的兩點X（1）gS，X（2）eS和任意實數(shù)九w（0,1），恒有f（X（1）+（1—九）X（2））<Xf（X（1））+（1—九）f（X（2））則稱/（x）為S上的凸函數(shù)。定理6.4設(shè)S是n維歐氏空間En上的一個開凸集，f（X）是定義在S上的具有二階連續(xù)導數(shù)的函數(shù)，那么，f（X）在S上為凸函數(shù)的充要條件是：對所有XeS，海賽矩陣V2f（X）都是半正定的；如果對所有的XeS，V2f（X）都是正定的，則f（X）在S上為嚴格凸函數(shù)。定義6.2非線性規(guī)劃問題：minf（X），XeEns.t.g（X）＜0,i=1,2,…,mih（X）=0,j=12…,p中，如果f（X）和g（X）（i=1,2,…,m）為x的凸函數(shù)，h（X）（j=1,2,…,p）為Xij的線性函數(shù)，則稱此問題為一凸規(guī)劃問題。凸規(guī)劃具有兩個重要性質(zhì)：1．凸規(guī)劃的可行集是凸集證：設(shè)凸規(guī)劃的可行集為S,即g（X）＜0,i二1,2,…,m;h（X）=0,j二1,2,…,p;XeE}i j n其中g(shù)（X）（i=1,2,…,m）為X的凸函數(shù)，h（X）（j=1,2,…,p）為X的線性函數(shù)。i j對于任意的X（1）eS，X（2）eS和任意實數(shù)九e（0,1），利用g（X）（i二1,2,…,m）i的凸性，對X=XX（i）+（1—九）X（2），有g(shù)i但g（X（1））＜0,i（X）=gGX（1）+（1—X）X（2））＜Xg（X（1））+gi但g（X（1））＜0,iig（X（2））＜0i所以g（X）＜0i同理h（X）=0j因此，X=XX（1）+（1—x）X（2）eS，故S為凸集。2．凸規(guī)劃的局部最小解就是它的全局最小解證：用反證法。設(shè)X*是凸規(guī)劃的一個局部最小解，X是它的全局最小解，但X豐X*。因為X*eS,XeS，所以VX￡(0,1),X=XX*+(1—九)XeS由f(X)為凸函數(shù)得，f(X)=f6X*+(l—X)X)<Xf(X*)+(l—X)f(X)因為X是一個全局最小解，所以f(X)<Xf(X*)+(1—X)f(X)<Xf(X*)+(1—X)f(X*)=f(X*)此式對一切Xe(o,1)都成立。當九T1時，則XTX*，即在X*的鄰域內(nèi)還有比f(X*)小的值，與X*為局部極小解的假設(shè)矛盾。因此，凸規(guī)劃的局部最小解就是它的全局最小解。［例題6.6］驗證下述非線性規(guī)劃為凸規(guī)劃，并求出最優(yōu)解。minf(X)=x2+x2-4x+4min121s.t.g(X)=—x2+x—1>0212g(X)=x>031g(X)=x>042解：第1，3，4三個約束條件為線性函數(shù)，因此也是凸函數(shù)第2個約束條件應(yīng)寫成g(X)=x2—x+1<0212Qg(X)2 Qg(X)[2 =2x， 2 =—1Qx 1 Qx12Q2g(X)2Q2g(X)0Q2g(X)0Qx2 Qx2 QxQx1212因此海賽矩陣為V因此海賽矩陣為V2g2(X)=0〔，半正定，g(X)為凸函數(shù)同理，V2f(x)=［：2，正定，f(X)也為凸函數(shù)。02所以，該非線性規(guī)劃為凸規(guī)劃。用圖解法得X26_4_X=(0.58,1.34|)824-2X26_4_X=(0.58,1.34|)824-2X*=(0.58,1.34萬為其唯一極小點，f(X*)=3.85.3.2其它類型的約束非線性規(guī)劃問題考慮只含不等式約束條件下求極小值問題的數(shù)學模型：minf(X),XgEns.t.g(X)>0,i=1,2,…,mi或?qū)懗蒻inf(X)XgX其中可行域X={XIXgEn,g(X)>0,i=1,2, ,m}。i定義6.3對于上述問題，設(shè)Xgx,若有g(shù)(X)=0(1<i<m)，則稱不等式約束ig(X)>0為點X處的起作用約束；若有g(shù)(X)>0(1<i<m)，則稱不等式約束iig(x)>0為點X處的不起作用約束。i定義6.4對于上述非線性規(guī)劃問題，如果可行點X處，各起作用約束的梯度向量線性無關(guān)，則稱X是約束條件的一個正則點。庫恩－塔克條件是非線性規(guī)劃領(lǐng)域中的重要理論成果之一，是確定某點為局部最優(yōu)解的一階必要條件，只要是最優(yōu)點就必滿足這個條件。但一般來說它不是充分條件，即滿足這個條件的點不一定是最優(yōu)點。但對于凸規(guī)劃，庫恩塔克條件既是必要條件，也是充分條件。對于只含有不等式約束的非線性規(guī)劃問題，有定理如下：定理6.5設(shè)X*是非線性規(guī)劃問題minf(X)X就%={XIXeEn,g(X)>0,i=1,2,…,m}i的極小點，若X*起作用約束的梯度Vg(x*)線性無關(guān)(即X*是一個正則點)，則i,Y*，…,Y*}，使下式成立1 2 mVf(X*)-￡Y*-Vg(X*)=0iii=1<Y*-Vg(X*)=0,i=1,2，…,miiY*>0,i=1,2，…,mi對同時含有等式與不等式約束的問題minf(x)s.t.g(X)>0 (i=1,2，…，m),ih(X)=0,(j=1,2，…,l)為了利用以上定理，將h(X)=0，用jh(X)>0-h(X)>0來代替。這樣即可得到同時含有等式與不等式約束條件的庫恩塔克條件如下：設(shè)X*為上述問題的極小點，若X*起作用約束的梯度Vg(X*)和Vh(X*)線性無關(guān),ij則Br*=C*,y*，…,Y*}和r*=6*,X*,???,九〕，使下式成立TOC\o"1-5"\h\z1 2 m 1 2 mVf(X*)-遲丫*-Vg(X*)-遲X*-Vh(X*)=0

i i j ji=1 j=1<Y*-Vg(X*)=0,i=1,2，…,miiY*>0,i=1,2，…,mi

［例題6.7］求下列非線性規(guī)劃問題的K-T點:minf(X)=2x2+2xx［例題6.7］求下列非線性規(guī)劃問題的K-T點:minf(X)=2x2+2xx+X2一10x一10x112212Ix2+x2<5s.t.\ 1 213x+x<612解:將上述問題的約束條件改寫為g（X）>0的形式:i(X)=一x2一x2+5>0(X)=一3x―x+6>012設(shè)K-T點為Xy%x2>，有(X*)=4x+2x一10122x+2x一1012Vg1(X*)=一2x1一2x2Vg2(X*)=一3x+2x一10+2丫x+3丫=0121122x+2x一10+2丫x+Y=012122由定理得丫V5-x2一x2)=0由定理得Y(6一3x一x)=0212丫>01丫>02求解上述方程組，即可求出Y，Y，x,x，則可得到滿足K-T條件的點。上述方程組是1212非線性方程組，求解時一般都要利用松緊條件（即上述方程組中的第3，4個方程），其實質(zhì)是分析X*點處，哪些是不起作用約束，以便得到丫=0，這樣分情況討論求解較為容易：i（1） 假設(shè)兩個約束均是X*點處的不起作用約束，即有Y=0，丫=012則有解得4x+2x一10=則有解得122x+2x一10=012但將該點代入約束條件，不滿足g(X)>0，因此該點不是可行點。i(2)若g」X)>0是起作用約束，g2(X)>0是不起作用約束，則有有廣0，則