無約束非線性規(guī)劃的算法與研究摘要本文旨在對非線性規(guī)劃的算法和應(yīng)用進行研究。非線性規(guī)劃是20世紀50年代才開始形成的一門新興學(xué)科。1931年庫恩和塔克發(fā)表的關(guān)于最優(yōu)性條件（后來稱為庫恩一塔克條件，乂稱為K-T條件）的論文是非線性規(guī)劃正式誕生的一個重要標志。非線性規(guī)劃在管理、工程、科研、軍事、經(jīng)濟等方面都有廣泛的應(yīng)用，并且為最優(yōu)設(shè)計提供了有力的工具。在第一章我們主要介紹了非線性規(guī)劃的基礎(chǔ)知如非線性規(guī)劃的數(shù)學(xué)模型，凸函數(shù)和凹函數(shù)，極值問題以及下降迭代算法等。在第二章我們主要對約束條件的線性規(guī)劃進行了具體介紹。在無約束非線性規(guī)劃中主要討論了一維搜索法和多變量函數(shù)極值的下降方法。第三章介紹了求解非線性規(guī)劃的計算機軟件并通過一些基本的例子，從而進一步加深對非線性規(guī)劃進行理解。關(guān)鍵詞：非線性規(guī)劃；約束非線性規(guī)劃；最優(yōu)解無約束非線性規(guī)劃的算法與研究第一章緒論1非線性規(guī)劃綜述非線性規(guī)劃是具有非線性LI標函數(shù)或約束條件的數(shù)學(xué)規(guī)劃，是運籌學(xué)的一個重要分支用。非線性規(guī)劃屬于最優(yōu)化方法的一種，是線性規(guī)劃的延伸。早在17世紀，Newton和Leibniz發(fā)明微積分的時代，已經(jīng)提出函數(shù)的極值問題，后來乂出現(xiàn)了Lagrange乘子法，Cauchy的最速下降法。但直到20世紀30年代，最優(yōu)化的理論和方法才得以迅速發(fā)展，并不斷完善，逐步成為一門系統(tǒng)的學(xué)科巨。1939年，Kantorovich和Hitchcock等人在生產(chǎn)組織管理和制定交通運輸方案方面首先研究和應(yīng)用了線性規(guī)劃。1947年，Dantzig提出了求解線性規(guī)劃的單純形法，為線性規(guī)劃的理論和算法奠定了基礎(chǔ)，單純形法被譽為“2世紀最偉大的創(chuàng)造之一”。1951年，由Kuhn和Tucker完成了非線性規(guī)劃的基礎(chǔ)性工作⑶。1959-1963年，山三位數(shù)學(xué)家共同研究成功求解無約束問題的DFP變尺度法(該算法是由英國數(shù)學(xué)家W.C.Davidon提出，由法國數(shù)學(xué)家R.Fletcher和美國數(shù)學(xué)家M.J.D.Powel1加以簡化)，該算法的研究成功是無約束優(yōu)化算法的一個大飛躍，引起了一系列的理論工作，并陸續(xù)出現(xiàn)了多種新的算法⑷。1965年，德國數(shù)學(xué)家C.GBroyden提出了求解非線性方程組的擬牛頓算法，并且該算法還包含了DFP算法。1970年，四位數(shù)學(xué)家以不同角度對變尺度算法進行了深入研究，提出了BFGS公式(C.GBroyden,RFletcher,D.Goldfarb,D.EShanno)。實踐表明該算法較之DFP算法和擬Newton法具有更好的數(shù)值穩(wěn)定性。1970年，無約束優(yōu)化方法的研究出現(xiàn)了引入注目的成果，英國數(shù)學(xué)家L.C.WDixon和美籍華人H.Y.Huang提出了關(guān)于“二階收斂算法的統(tǒng)一研究”的研究成果，提出了一個令三個自由參數(shù)的公式族?Huang族和擬牛頓公式，它可包容前面所介紹的所有無約束優(yōu)化算法。20世紀70年代，最優(yōu)化無論在理論和算法上，還是在應(yīng)用的深度和廣度上都有了進一步的發(fā)展。隨著電子計算機的飛速發(fā)展，最優(yōu)化的應(yīng)用能力越來越強，從而成為一門十分活躍的學(xué)科⑸。近代最優(yōu)化方法的形成和發(fā)展過程中最重要的事件有：1、以蘇聯(lián)康托羅維奇和美國丹齊克為代表的線性規(guī)劃：2、以美國庫恩和塔克爾為代表的非線性規(guī)劃；3、以美國貝爾曼為代表的動態(tài)規(guī)劃：4、以蘇聯(lián)龐特里亞金為代表的極大值原理等。這些方法后來都形成體系，成為近代很活躍的學(xué)科，對促進運籌學(xué)、管理科學(xué)、控制論和系統(tǒng)工程等學(xué)科的發(fā)展起了重要作用非線性規(guī)劃在經(jīng)營管理、上程設(shè)計、科學(xué)研究、軍事指揮等方面普遍地存在著最優(yōu)化問題。例如：如何在現(xiàn)有人力、物力、財力條件下合理安排產(chǎn)品生產(chǎn)，以取得最高的利潤；如何設(shè)計某種產(chǎn)品，在滿足規(guī)格、性能要求的前提下，達到最低的成本；如何確定一個自動控制系統(tǒng)的某些參數(shù)，使系統(tǒng)的工作狀態(tài)最佳；如何分配一個動力系統(tǒng)中各電站的負荷，在保證一定指標要求的前提下，使總耗費最??；如何安排庫存儲量，既能保證供應(yīng)，乂使儲存費用最低；如何組織貨源，既能滿足顧客需要，乂使資金周轉(zhuǎn)最快等。對于靜態(tài)的最優(yōu)化問題，當□標函數(shù)或約束條件出現(xiàn)未知量的非線性函數(shù)，且不便于線性化，或勉強線性化后會招致較大誤差時，就可應(yīng)用非線性規(guī)劃的方法去處理。1.2非線性規(guī)劃的基礎(chǔ)知識對于一個實際問題，在把它歸結(jié)成非線性規(guī)劃問題時，一般要注意如下兒點：（1）確定供選方案：首先要收集同問題有關(guān)的資料和數(shù)據(jù)，在全面熟悉問題的基礎(chǔ)上，確認什么是問題的可供選擇的方案，并用一組變量來表示它們。（2）提出追求H標：經(jīng)過資料分析，根據(jù)實際需要和可能，提出要追求極小化或極大化的目標。并且，運用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式。（3）給出價值標準：在提出要追求的目標之后，要確立所考慮目標的“好”或“壞”的價值標準，并用某種數(shù)量形式來描述它。（4）尋求限制條件：由于所追求的目標一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示。1.2.1非線性規(guī)劃問題的數(shù)學(xué)模型非線性規(guī)劃是具有非線性LI標函數(shù)或約束條件的數(shù)學(xué)規(guī)劃。它的數(shù)學(xué)模型常表示成以下形式：min/(X)</*(X)=0J=12…，加(1.1)gj(X)N0,j=l,2,..?,f其中自變量X=(xi9x29...9xn)r是〃維歐氏空間中的向量；/(X)是目標函數(shù)/zf.(x)=0和gj(x)no是約束條件。也可以將非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式minf(X)(1.2)對于求LI標函數(shù)的最大值問題，我們可以轉(zhuǎn)換成求其負函數(shù)的最小值問題，從而轉(zhuǎn)換成非線性規(guī)劃的標準形式。1.2.2極值問題1、局部極值和全局極值設(shè)/(X)是力維歐氏空間夕中某一區(qū)域0的函數(shù)，這一區(qū)域0叫做可行域。對于X*eL,如果存在>6,對xFv/且HX-X*//<r,都有f(x*)w/(X),則稱x*為/(X)在。上的局部極小點，fcr*J為局部極小值。對于X*e：0,如果存在e>6,對XWD且X-X*〈&，都有f(X*)<f(X),則稱尤*為/0)在0上的嚴格局部極小點，ftXV為嚴格局部極小值。如果對于一切〉VJ都有f(X*)W/(X),則稱X*^/XV在D上的全局極小點，f(X")為全局極小值。如果對于一切力V/,都有f(X*)<f(X)，則稱X*為f如在0上的嚴格全局極小點，f(X")為嚴格全局極小值。2、極值點存在的判定首先引入梯度和海賽(Hessian)矩陣的定義。設(shè)力元函數(shù)f如的一階偏導(dǎo)數(shù)存在，則稱

為函數(shù)fd?的梯度函數(shù)。設(shè)力元函數(shù)^▼的二階偏導(dǎo)數(shù)存在，稱山f(X)的所有二階偏導(dǎo)數(shù)構(gòu)成的矩陣a-Xz)d2Mdxfdxjdx2滬心dxjdxndx''dxj■dxjdXr■■■■■■a'AzO*a-7(z0dXfJd%為函數(shù)/7X?的海賽(Hessian)矩陣。它是對稱矩陣。山線性代數(shù)知道，二次型懣為正定的充要條件是它的矩陣〃的左上角各階主子式都大于零；而它為負定的充要條件是它的矩陣〃的左上角各階主子式依次正負相間。二次型為正定、負定或不定時，對稱矩陣〃分別為成為正定的、負定的或不定的。定理11：(一階必要條件)設(shè)f如是刀維歐氏空間夕中某一區(qū)域。的函數(shù)也*)f，初，定理1.2:(二階必要條件)設(shè)f①是n維歐氏空間F中某一區(qū)域。的函數(shù),f如的一階連續(xù)偏導(dǎo)數(shù)存在。若X左為f(x)的局部極小點，則迎廣)\的二階連續(xù)偏導(dǎo)數(shù)存在。若〃為f如的局部極小點，則〃&*)二SM廠)$6O定理1.3:(二階充分條件)設(shè)f如是力維歐氏空間F中某一區(qū)域。的函數(shù)，ie8(D)。若勺(才*)二Bxf>S則尤*為如的局部極小點。、1-2.3凸函數(shù)和凹函數(shù)1、凸凹函數(shù)的定義設(shè)f也*)f，初，定理1.2:(二階必要條件)設(shè)f①是n維歐氏空間F中某一區(qū)域。的函數(shù),a(0<a〈〃以及。中的任意兩點尤⑵和X仞，恒有f(aX(i"(l-a)X2))Waf(Xi))十(1-a)f(X2))則稱f如為定義在0上的凸函數(shù)。如果f{aX（i）+（l-a）X2））<af（Xi））+（1-a）fiX⑵）則稱f如為定義在0上的嚴格凸函數(shù)。將上面兩式的不等號反向，即可得凹函數(shù)和嚴格凹函數(shù)的定義。顯然，如果為凸函數(shù)（嚴格凸函數(shù)），則-/YV一定是凹函數(shù)（嚴格凹函數(shù)）。凸函數(shù)的性質(zhì)設(shè)，△都是D上的凸函數(shù)，SS則f》f是。上的凸函數(shù)。設(shè)f如是定義在凸集。上的凸函數(shù)，則對任一實數(shù)0,集合=VD,f（X）W刃是凸集。函數(shù)凸性的判定定理1?4:（一階條件））設(shè)是刀維歐氏空間夕中某一開凸集0的函數(shù)，f如的一階連續(xù)偏導(dǎo)數(shù)存在。則f如為0上的凸函數(shù)的充要條件是，對任意兩個不同的點X⑵和〃匕恒有f（x⑵）nfJ一wJ定理1.5:（二階條件）設(shè)f如是門維歐氏空間夕中某一開凸集0的函數(shù)，f①的二階連續(xù)偏導(dǎo)數(shù)存在。則f①為0上的凸函數(shù)的充要條件是：/ZV的海賽（Hessian^陣〃如在0上處處半正定。凸函數(shù)的極值定理1.6:若/ZV是定義在凸集0上的凸函數(shù)，則它的任一極小點就是它在刀上最小點（全局極小點），而且它的極小點形成一個凸集。定理1?7:設(shè)f仞是定義在凸集0上的可微凸函數(shù)，若存在點尤欷e乙使得對于所有的尤&殖-X*）鼻側(cè)廠是f如在。上的最小點（全局極小點）。當X*是。得內(nèi)點時，式子磔廠兒尤-廠JMC對于任意尤-廣都成立，這就意味著可將式子-XV$c改為勺（廠）二屋1.2.4凸規(guī)劃對一個非線性規(guī)劃問題，如果：1、目標是求凸函數(shù)的最小值。2、每個等式約束函數(shù)都是一個線性函數(shù)。3、每個小于或等于的約束函數(shù)都是凸函數(shù)。4、每個大于或等于約束函數(shù)都是凹函數(shù)。則稱該非線性規(guī)劃問題是凸規(guī)劃問題。定理1?8：凸規(guī)劃問題的可行域是凸集。定理1?9：凸規(guī)劃問題局部最優(yōu)解就是總體最優(yōu)解。1.2.5下降迭代算法迭代法的基本思想是：為了求函數(shù)的最優(yōu)解，首先給定一個初始估計然后按某種算法找出比X仞更好的解尤⑵，再按照此種規(guī)劃找出比X?更好的解X仞，…。即可得到一個解的序列｛X〃｝。若這個序列有極限即Jjrn!/Y(k)-V*//k_8—‘丸，則稱它收斂于廠。若山某算法所產(chǎn)生的解的序列｛*〃｝使忖標函數(shù)心〉)逐漸減少，就稱這算法為下降算法。我們把x(k+i)-x(k"kfFU做基本迭代模式。嚴稱為搜索方向，，仃稱為步長或步長因子。所以下降迭代算法的步驟可總結(jié)如下：選定某一初始點尤仞，并令&=0；確定搜索方向嚴；從/俐出發(fā)，沿方向嚴求步長J仃，以產(chǎn)生下一個迭代點X(k'檢查得到的新點X(k!)是否為極小點或近似極小點。若是，則停止迭代。否則，令2k+l,轉(zhuǎn)回(2)繼續(xù)進行迭代。第二章約束條件的非線性規(guī)劃3.1約束非線性規(guī)劃的數(shù)學(xué)模型帶有約束條件的極值問題稱為約束極值問題，也叫規(guī)劃問題。其一般形式為222'姒的。J（3.1））minf（X）I呼力$o,j=1,2,???，1（3.2）3.2最優(yōu)性問題3.21最優(yōu)性的基本概念定義3.1設(shè)”是非線性規(guī)劃問題的一個可行解，它使某個的（處NglWjW力，具有下面兩種情況：（1）如果gJ（W）>G則稱約束條件胡力WjW刀是〃點的無效約束（或不起作用約束）。（2）如果使陽（0）二、則稱約束條件胡力三gWjW■力是點的有效約束（或起作用約束）。如果殆（力鼻MlWjWI）是”點的無效約束，則說明”位于可行域的內(nèi)部，不在邊界上，即當”有微小變化時，此約束條件不會有什么影響。而對于有效約束則說明”位于可行域的邊界上，即當”有微小變化時，此約束條件起著限制作用。定義3.2設(shè)”是非線性規(guī)劃問題的一個可行解，即可行域斤內(nèi)的一點，〃是過此點的某一個方向，如果：（1）存在實數(shù)DG使對任意以G[0,心均有M八三日，則稱此方向〃是F點的一個可行方向；（2）存在實數(shù)一■>6,使對任意以&[0,人刀均有/'必如以a則稱此方向〃是〃點的一個下降方向;方向孑既是F點的可行方向，乂是下降方向，則稱它是”點可行下降方向。3.2.2最優(yōu)性的條件定理3.1(Kuhn-Tucker)如果是問題(3.2)的極小點，且與點尤*的有效約束的梯度線性無關(guān)，則必存在向量廠*=(ryJ：?Y使下述條件成立：總?cè)擞?)-歲切(廠)二0j/(護)=0(j=1,2,???，1)'門鼻0(j二1,2,...,1)(3.3)此條件稱為庫恩-塔克(Kuhn-Tucker)條件，簡稱為K-T條件。滿足K-T條件的點稱為K-T點嚴。類似地，如果工*?是問題(3.1)的極小點，且與點X*?的所有有效約束的梯度弘CY訂(i二1,2，…,勿和切(才(j二1,2,…,D線性無關(guān)，則必存在向量A*=r.iL入2二/I:廣和Y*=(rL丫2二r〃使下面的K-T條件成立：總?cè)藦S)一工：二川*%Cr*)-Jy*切(廠)二6j/廠)=0(j=1,2,...,1)丫1鼻。(j=1,2,...,1)(3.4)將滿足K-T條件的點也稱為K-T點。其中A,4昇.，以：和yy2ry:稱為廣義Lagrange乘子。3.3二次規(guī)劃若某非線性規(guī)劃的□標函數(shù)為自變量*的二次函數(shù)，約束條件乂全是線性的，就稱這種規(guī)劃為二次規(guī)劃。二次規(guī)劃的數(shù)學(xué)模型可表述為：minfix)=E：=+:二聲,=盧以為必5=Qy/(k=1,2t…,n):12,…，m)勺20,j二L2*?匕n(3.6)式右端的笫二項為二次型。如果該二次型正定(或半正定)，則口標函數(shù)為嚴格凸函數(shù)(或凸函數(shù))；此外，二次規(guī)劃的可行域為凸集，因而，上述規(guī)劃屬于凸規(guī)劃。前面已指出，凸規(guī)劃的局部極值即為全局極值。對于這種問題來說庫恩-塔克條件不但是極值點存在的必要條件，而且也是充分條件。二次規(guī)劃的求解：將K-T條件中的第一個條件應(yīng)用于二次規(guī)劃(3.6)——(3.8),y代替K-T條件中的Y,即可得到：二gjkxRi二jajjVjj+i+yj二Cj(J-1,2,…,n)(3.9)在式(3.8)中引入松弛變量xn.i,式(3.8)即變?yōu)?假定％步0)：二flijXj-xn+心=0(2-1,2…?,m}(3.10)再將K-T條件中的第二個條件應(yīng)用于上述二次規(guī)劃，并考慮到式(3.10)，就得到XjVj=O(j=l,2,??->n+m}(3.11)此外，還有

X仝6,Vj事G(〉=1,2,,n+m)(3.12)聯(lián)立求解式(3.9)和(3.10),如果得到的解也滿足式(3.11)和式(3.12),則這個解就是原二次規(guī)劃問題的解。但是，在式(3.9)中，?？赡転檎?，也可能為負，為了便于求解，先引入人工變量旬(右仝6,其前面的符號可以取正或負，以便得出可行解)。這樣，式(3.9)就變成乙(二fiijVn+i+yj一乙點二］Cjk+sgn(CC)zg(j-1,2,?,n)(3.13)其中：sgn(Cj)為符號函數(shù)：sgn(cj)=七當。P加寸■sgn(勺)二一1,當Cj〈01寸這樣一來，可得到初始基本可行解如下：Zj=sgn(Cj)(j=1,2，…,n)Xn豐1=bi(i=1,2，…,ill)□二0(j=1,2，…,n)Yj=0(j=1,2…,n+m)但是，只有當習(xí)=0時，才能夠得到原來問題的解，故必須對上述問題進行修正，從而得到如下的線性規(guī)劃問題：minG(力七-乙’二iajyn+iiyn5二3ksgn(cj)zj=cj(JminG(力七-乙’二iajyn+iiyn5二3ksgn(cj)zj=cj(J二A2:n)^2OVTJ?/-/刃方刀刀〃(X：,x2r:召：鼬y:,y2,?.《Gz、zi=O,彳=0,?=0)，則(才；，比匚J；)就是原二次規(guī)劃問題的最優(yōu)解。3.4約束非線性規(guī)劃的求解方法3.4.1可行方向法考慮非線性規(guī)劃問題(3.2),假設(shè)H是該問題的可行解，但不是最優(yōu)解。為了進一步尋找最優(yōu)解，在它的可行下降方向中選取其一個方向/并確定最佳步長人&使得FH十人址.A/+7)<f(jf)(3.15)反復(fù)進行這一過程，直到得到滿足精度要求的可行解為止，這種方法稱為可行方向法?？尚蟹较蚍ǖ闹饕攸c是：因為迭代過程中所采用的搜索方向總為可行方向，所以產(chǎn)生的迭代點列｛F｝始終在可行域斤內(nèi)，且LI標函數(shù)值不斷的單調(diào)下降?？尚蟹较蚍▽嶋H上是一類方法，最典型的是Zoutend