1、無約束非線性規劃的算法與研究摘要本文旨在對非線性規劃的算法和應用進行研究。非線性規劃是20世紀50年代才開始形成的一門新興學科。1951年庫恩和塔克發表的關于最優性條件(后來稱為庫恩塔克條件，又稱為K-T條件)的論文是非線性規劃正式誕生的一個重要標志。非線性規劃在管理、工程、科研、軍事、經濟等方面都有廣泛的應用，并且為最優設計提供了有力的工具。在第一章我們主要介紹了非線性規劃的基礎知如非線性規劃的數學模型，凸函數和凹函數，極值問題以及下降迭代算法等。在第二章我們主要對約束條件的線性規劃進行了具體介紹。在無約束非線性規劃中主要討論了一維搜索法和多變量函數極值的下降方法。第三章介紹了求解非線性規劃

2、的計算機軟件并通過一些基本的例子，從而進一步加深對非線性規劃進行理解。關鍵詞：非線性規劃；約束非線性規劃；最優解無約束非線性規劃的算法與研究第一章 緒論1.1非線性規劃綜述非線性規劃是具有非線性目標函數或約束條件的數學規劃，是運籌學的一個重要分支1。非線性規劃屬于最優化方法的一種，是線性規劃的延伸。早在17世紀，Newton和Leibniz發明微積分的時代，已經提出函數的極值問題，后來又出現了Lagrange乘子法，Cauchy的最速下降法。但直到20世紀30年代，最優化的理論和方法才得以迅速發展，并不斷完善，逐步成為一門系統的學科2。1939年，Kantorovich和Hitchcock等人

3、在生產組織管理和制定交通運輸方案方面首先研究和應用了線性規劃。1947年，Dantzig提出了求解線性規劃的單純形法，為線性規劃的理論和算法奠定了基礎，單純形法被譽為“20世紀最偉大的創造之一”。1951年，由Kuhn和Tucker完成了非線性規劃的基礎性工作 3。19591963年，由三位數學家共同研究成功求解無約束問題的DFP變尺度法(該算法是由英國數學家WCDavidon提出，由法國數學家RFletcher和美國數學家MJD.Powell加以簡化)，該算法的研究成功是無約束優化算法的一個大飛躍，引起了一系列的理論工作，并陸續出現了多種新的算法4。1965年，德國數學家CG Broyden

4、提出了求解非線性方程組的擬牛頓算法，并且該算法還包含了DFP算法。1970年，四位數學家以不同角度對變尺度算法進行了深入研究，提出了BFGS公式 (CG Broyden，R Fletcher，DGoldfarb，DE Shanno) 。實踐表明該算法較之DFP算法和擬Newton法具有更好的數值穩定性。1970年，無約束優化方法的研究出現了引入注目的成果，英國數學家LCW Dixon和美籍華人HYHuang提出了關于“二階收斂算法的統一研究”的研究成果，提出了一個令三個自由參數的公式族Huang族和擬牛頓公式，它可包容前面所介紹的所有無約束優化算法。20世紀70年代，最優化無論在理論和算法上，

5、還是在應用的深度和廣度上都有了進一步的發展。隨著電子計算機的飛速發展，最優化的應用能力越來越強，從而成為一門十分活躍的學科5。近代最優化方法的形成和發展過程中最重要的事件有：1、 以蘇聯康托羅維奇和美國丹齊克為代表的線性規劃； 2、 以美國庫恩和塔克爾為代表的非線性規劃； 3、 以美國貝爾曼為代表的動態規劃； 4、 以蘇聯龐特里亞金為代表的極大值原理等。 這些方法后來都形成體系，成為近代很活躍的學科，對促進運籌學、管理科學、控制論和系統工程等學科的發展起了重要作用 非線性規劃在經營管理、工程設計、科學研究、軍事指揮等方面普遍地存在著最優化問題。例如：如何在現有人力、物力、財力條件下合理安排產品

6、生產，以取得最高的利潤；如何設計某種產品，在滿足規格、性能要求的前提下，達到最低的成本；如何確定一個自動控制系統的某些參數，使系統的工作狀態最佳；如何分配一個動力系統中各電站的負荷，在保證一定指標要求的前提下，使總耗費最小；如何安排庫存儲量，既能保證供應，又使儲存費用最低；如何組織貨源，既能滿足顧客需要，又使資金周轉最快等。對于靜態的最優化問題，當目標函數或約束條件出現未知量的非線性函數，且不便于線性化，或勉強線性化后會招致較大誤差時，就可應用非線性規劃的方法去處理。1.2非線性規劃的基礎知識對于一個實際問題，在把它歸結成非線性規劃問題時，一般要注意如下幾點： （1）確定供選方案：首先要收集同

7、問題有關的資料和數據，在全面熟悉問題的基礎上，確認什么是問題的可供選擇的方案，并用一組變量來表示它們。 （2）提出追求目標：經過資料分析，根據實際需要和可能，提出要追求極小化或極大化的目標。并且，運用各種科學和技術原理，把它表示成數學關系式。 （3）給出價值標準：在提出要追求的目標之后，要確立所考慮目標的“好”或“壞”的價值標準，并用某種數量形式來描述它。 （4）尋求限制條件：由于所追求的目標一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示。非線性規劃問題的數學模型非線性規劃是具有非線性目標函數或約束條件的數學規劃

8、。它的數學模型常表示成以下形式： （1.1）其中自變量是維歐氏空間中的向量；是目標函數和是約束條件。也可以將非線性規劃的數學模型寫成以下形式 （1.2）對于求目標函數的最大值問題，我們可以轉換成求其負函數的最小值問題，從而轉換成非線性規劃的標準形式。極值問題1、局部極值和全局極值設是n維歐氏空間En中某一區域D的函數，這一區域D叫做可行域。對于，如果存在，對D且|X-X*|<，都有f(X*),則稱X*為在D上的局部極小點，f(X*)為局部極小值。對于X*D，如果存在>0，對XD且|X-X*|<，都有f(X*)<f(X),則稱X*為在D上的嚴格局部極小點，f(X*)為嚴格

9、局部極小值。如果對于一切XD，都有f(X*)，則稱X*為f(X)在D上的全局極小點，f(X*)為全局極小值。如果對于一切XD，都有f(X*)<f(X)，則稱X*為f(X)在D上的嚴格全局極小點，f(X*)為嚴格全局極小值。2、極值點存在的判定首先引入梯度和海賽(Hessian)矩陣的定義。設n元函數f(X)的一階偏導數存在，則稱fX=(fXx1,fXx2,fXxn)T為函數f(X)的梯度函數。設n元函數f(X)的二階偏導數存在，稱由f(X)的所有二階偏導數構成的矩陣HX=2fXx122fXx1x22fXx1xn2fXx2x12fXx222fXx2xn2fXxnx12fXxnx22fXxn

10、2為函數f(X)的海賽(Hessian)矩陣。它是對稱矩陣。由線性代數知道，二次型ZTHZ為正定的充要條件是它的矩陣H的左上角各階主子式都大于零；而它為負定的充要條件是它的矩陣H的左上角各階主子式依次正負相間。二次型為正定、負定或不定時，對稱矩陣H分別為成為正定的、負定的或不定的。定理1.1:（一階必要條件）設f(X)是n維歐氏空間En中某一區域D的函數f(X)的一階連續偏導數存在。若X*為f(X)的局部極小點，則 fX*=(fX*x1,fX*x2,fX*xn)T=0定理1.2:（二階必要條件）設f(X)是n維歐氏空間En中某一區域D的函數，f(X)的二階連續偏導數存在。若X*為f(X)的局部

11、極小點，則fX*=0，HX*0。定理1.3:（二階充分條件）設f(X)是n維歐氏空間En中某一區域D的函數，f C2(D)。若fX*=0，HX*>0，則X*為f(X)的局部極小點。、 凸函數和凹函數1、凸凹函數的定義設f(X)是n維歐氏空間En中某一凸集D上的函數，若對于任何實數(0<<1)以及D中的任意兩點X(1)和X(2)，恒有f(X(1)+(1-) X(2) f(X(1) +(1-)f(X(2)則稱f(X)為定義在D上的凸函數。如果f(X(1)+(1-) X(2)<f(X(1) +(1-)f(X(2)則稱f(X)為定義在D上的嚴格凸函數。將上面兩式的不等號反向，即

12、可得凹函數和嚴格凹函數的定義。顯然，如果f(X)為凸函數（嚴格凸函數），則-f(X)一定是凹函數（嚴格凹函數）。2.凸函數的性質設f1,f2,fn都是D上的凸函數，1,2, n0,則f =i=1mifi也是D上的凸函數。設f(X)是定義在凸集D上的凸函數，則對任一實數，集合S=X|XD, f(X) 是凸集。3.函數凸性的判定定理1.4:（一階條件）設f(X)是n維歐氏空間En中某一開凸集D的函數，f(X)的一階連續偏導數存在。則f(X)為D上的凸函數的充要條件是，對任意兩個不同的點X(1)和X(2)，恒有f (X(2) f (X(1) +fX1T(X(2)-X(1)定理1.5:（二階條件）設f

13、(X)是n維歐氏空間En中某一開凸集D的函數，f(X)的二階連續偏導數存在。則f(X)為D上的凸函數的充要條件是：f(X)的海賽(Hessian)矩陣H(X)在D上處處半正定。4.凸函數的極值定理1.6:若f(X)是定義在凸集D上的凸函數，則它的任一極小點就是它在D上最小點（全局極小點），而且它的極小點形成一個凸集。定理1.7:設f(X)是定義在凸集D上的可微凸函數，若存在點X*D，使得對于所有的XD有 fX*T(X-X*) 0則X*是f(X)在D上的最小點（全局極小點）。當X*是D得內點時，式子 fX*T(X-X*) 0對于任意X-X*都成立，這就意味著可將式子 fX*T(X-X*) 0改為

14、 fX*=0。凸規劃對一個非線性規劃問題，如果：1、目標是求凸函數的最小值。2、每個等式約束函數都是一個線性函數。3、每個小于或等于的約束函數都是凸函數。4、每個大于或等于約束函數都是凹函數。則稱該非線性規劃問題是凸規劃問題。定理1.8：凸規劃問題的可行域是凸集。定理1.9：凸規劃問題局部最優解就是總體最優解。下降迭代算法迭代法的基本思想是：為了求函數f (X)的最優解，首先給定一個初始估計X(0)，然后按某種算法找出比X(0)更好的解X(1)，再按照此種規劃找出比X(1)更好的解X(2),。即可得到一個解的序列X(k)。若這個序列有極限X*，即limk|X(k)-X*|=0，則稱它收斂于X*

15、。若由某算法所產生的解的序列X(k)使目標函數f(X(k)逐漸減少，就稱這算法為下降算法。我們把X(k+1)=X(k)+kPk 叫做基本迭代模式。Pk稱為搜索方向，k稱為步長或步長因子。所以下降迭代算法的步驟可總結如下： （1）選定某一初始點X(0)，并令k=0;（2）確定搜索方向Pk；（3）從X(k)出發，沿方向Pk求步長k，以產生下一個迭代點X(k+1)；（4）檢查得到的新點X(k+1)是否為極小點或近似極小點。若是，則停止迭代。否則，令k=k+1，轉回（2）繼續進行迭代。第二章 約束條件的非線性規劃3.1約束非線性規劃的數學模型帶有約束條件的極值問題稱為約束極值問題，也叫規劃問題。其一般

16、形式為 min f(X) hiX=0,i=1,2,mgjX0,j=1,2,l （3.1）或 min f(X) gjX0,j=1,2,l （3.2）3.2最優性問題最優性的基本概念定義3.1 設X0是非線性規劃問題的一個可行解，它使某個 gjX0(1jl),具有下面兩種情況：（1） 如果 gjX0>0，則稱約束條件 gjX0(1jl)是X0點的無效約束（或不起作用約束）。（2） 如果使 gjX0=0，則稱約束條件 gjX0(1jl)是X0點的有效約束（或起作用約束）。如果 gjX0(1jl) 是X0點的無效約束，則說明X0位于可行域的內部，不在邊界上，即當X0有微小變化時，此約束條件不會有

17、什么影響。而對于有效約束則說明X0位于可行域的邊界上，即當X0有微小變化時，此約束條件起著限制作用。定義3.2 設X0是非線性規劃問題的一個可行解，即可行域R內的一點，d是過此點的某一個方向，如果：（1）存在實數0>0，使對任意0, 0均有X0+d R，則稱此方向d是X0點的一個可行方向； (2) 存在實數0>0，使對任意0, 0均有f(X0+d )<f(X0)，則稱此方向d是X0點的一個下降方向； (3) 方向d既是X0點的可行方向，又是下降方向，則稱它是X0點可行下降方向。最優性的條件定理3.1 （Kuhn-Tucker）如果X*是問題（3.2）的極小點，且與點X*的有效

18、約束的梯度線性無關，則必存在向量*=(1*,2,*l*)T使下述條件成立： fX*-j=1lj*gjX*=0j* gjX*=0 (j=1,2,l)j*0 (j=1,2,l) （3.3）此條件稱為庫恩-塔克（Kuhn-Tucker）條件，簡稱為K-T條件。滿足K-T條件的點稱為K-T點14。類似地，如果X*是問題（3.1）的極小點，且與點X*的所有有效約束的梯度hiX*(i=1,2,m)和gjX*(j=1,2,l)線性無關，則必存在向量*=(1*,2,*m*)T和*=(1*,2,*l*)T使下面的K-T條件成立： fX*-i=1mi*hiX*-j=1lj*gjX*=0j* gjX*=0 (j=1

19、,2,l)j*0 (j=1,2,l) （3.4）將滿足K-T條件的點也稱為K-T點。其中1*,2,*m*和1*,2,*l*稱為廣義Lagrange乘子。3.3二次規劃若某非線性規劃的目標函數為自變量X的二次函數，約束條件又全是線性的，就稱這種規劃為二次規劃。二次規劃的數學模型可表述為： minfX=j=1ncjxj+12j=1nk=1ncjkxjxk （3.5）cjk=ckj , k=1,2,n （3.6）k=1naijxj+bi0 , i=1,2,m （3.7）xj0 , j=1,2,n （3.8）（3.6）式右端的第二項為二次型。如果該二次型正定（或半正定），則目標函數為嚴格凸函數（或凸函

20、數）；此外，二次規劃的可行域為凸集，因而，上述規劃屬于凸規劃。前面已指出，凸規劃的局部極值即為全局極值。對于這種問題來說，庫恩-塔克條件不但是極值點存在的必要條件，而且也是充分條件。二次規劃的求解：將K-T條件中的第一個條件應用于二次規劃（3.6）（3.8），y代替K-T條件中的，即可得到： -k=1ncjkxk+i=1maijyn+i+yj=cj（j=1,2,n） (3.9)在式（3.8）中引入松弛變量xn+1，式（3.8）即變為（假定bi0）： i=1naijxj-xn+i+bi=0 （i=1,2,m） (3.10)再將K-T條件中的第二個條件應用于上述二次規劃，并考慮到式（3.10），就

21、得到 xjyj=0 （j=1,2,n+m） (3.11)此外，還有 xj0，yj0 （j=1,2,n+m） (3.12) 聯立求解式（3.9）和（3.10），如果得到的解也滿足式（3.11）和式（3.12），則這個解就是原二次規劃問題的解。但是，在式（3.9）中，cj可能為正，也可能為負，為了便于求解，先引入人工變量zj（zj0，其前面的符號可以取正或負，以便得出可行解）。這樣，式（3.9）就變成 i=1maijyn+i+yj-k=1ncjk+sgn（cj）zj=cj（j=1,2,n） (3.13)其中：sgn（cj）為符號函數：sgncj=1，當cj0時sgncj=-1,當cj<0時這

22、樣一來，可得到初始基本可行解如下：zj=sgncj (j=1,2,n)xn+1=bi (i=1,2,m)xj=0 (j=1,2,n)yj=0 (j=1,2,n+m)但是，只有當zj=0時，才能夠得到原來問題的解，故必須對上述問題進行修正，從而得到如下的線性規劃問題： minZ=j=1nzj i=1maijyn+i+yj-k=1ncjkxk+sgn（cj）zj=cj（j=1,2,n）j=1naijxj-xn+i+bi=0 i=1,2,m xj0 , j=1,2,n+m yj0 , j=1,2,n+m zj0 , j=1,2,n (3.14)該線性規劃問題還應滿足式（3.10）。也就是說，不能使x

23、j和yj（對每一個j）同時為基變量。解線性規劃問題（3.14），若得到最優解（x1*,x2,*xn+m*,y1*,y2*,yn+m*, z1=0,z2=0,zn=0）,則（x1*,x2,*xn*）就是原二次規劃問題的最優解。3.4約束非線性規劃的求解方法可行方向法考慮非線性規劃問題（3.2），假設Xk是該問題的可行解，但不是最優解。為了進一步尋找最優解，在它的可行下降方向中選取其一個方向dk,并確定最佳步長k使得 Xk+1=Xk+kdkfXk+1<f(Xk) （3.15）反復進行這一過程，直到得到滿足精度要求的可行解為止，這種方法稱為可行方向法。 可行方向法的主要特點是：因為迭代過程中所采用的搜索方向總為可行方向，所以產生的迭代點列Xk始終在可行域R內，且目標函數值不斷的單調下降。可行方向法實際上是一類方法，最典型的是Zoutendijk可行方向法。定理3.2 設X*是問題（3.2）的一個局部極小點，函數f(