關(guān)于非線性約束最優(yōu)化方法-乘子法

1、非線性約束最優(yōu)化方法乘子法1.1研究背景最優(yōu)化理論與方法是一門(mén)應(yīng)用性相當(dāng)廣泛的學(xué)科，它的最優(yōu)性主 要表現(xiàn)在討論決策問(wèn)題的最佳選擇性，討論計(jì)算方法的理論性質(zhì)，構(gòu) 造尋求最佳解的計(jì)算方法，以及實(shí)際計(jì)算能力。伴隨著計(jì)算數(shù)學(xué)理論 的發(fā)展、優(yōu)化計(jì)算方法的進(jìn)步以及計(jì)算機(jī)性能的迅速提高，規(guī)模越來(lái) 越大的優(yōu)化問(wèn)題得到解決。因?yàn)樽顑?yōu)化問(wèn)題廣泛見(jiàn)于經(jīng)濟(jì)計(jì)劃、工程 設(shè)計(jì)、生產(chǎn)管理、交通運(yùn)輸、國(guó)防等重要領(lǐng)域，它已受到政府部門(mén)、 科研機(jī)構(gòu)和產(chǎn)業(yè)部門(mén)的高度重視。然而，隨著人們對(duì)模型精度和最優(yōu) 性的要求所得到的優(yōu)化命題往往具有方程數(shù)多、變量維數(shù)高、非線性 性強(qiáng)等特點(diǎn)，使得相關(guān)變量的存儲(chǔ)、計(jì)算及命題的求解都相當(dāng)困難， 從而導(dǎo)

2、致大規(guī)模非線性優(yōu)化很難實(shí)現(xiàn)。因此，尋求高效、可靠的大規(guī) 模非線性優(yōu)化算法成為近年來(lái)研究的熱點(diǎn)。本文討論的問(wèn)題屬于非線性約束規(guī)劃的范疇，討論了其中的非線 性等式約束最優(yōu)化問(wèn)題方面的一些問(wèn)題。1. 2非線性約束規(guī)劃問(wèn)題的研究方法非線性約束規(guī)劃問(wèn)題的一般形式為min /(x),兀 w r",(npl) st c,(兀)= 0, iw e = 1，2,，c.(x) 5 0,i w i = i + 1,1 + 2,.,z + m其中，/(x),c,.(x)是連續(xù)可微的.在求解線性約束優(yōu)化問(wèn)題時(shí)，可以利用約束問(wèn)題本身的性質(zhì), 但是對(duì)于非線性約束規(guī)劃問(wèn)題，由于約束的非線性使得求解這類(lèi)問(wèn)題 比較復(fù)雜

3、、困難。因此，我們將約束問(wèn)題轉(zhuǎn)化為一系列無(wú)約束優(yōu)化問(wèn) 題，通過(guò)求解一系列無(wú)約束優(yōu)化問(wèn)題，來(lái)得到約束優(yōu)化問(wèn)題的最優(yōu)解。 我們用到的幾類(lèi)主要的方法有:罰函數(shù)法、乘子法以及變尺度法。傳統(tǒng)上我們所提出的非線性約束最優(yōu)化方法一般都遵循下列三 個(gè)基本思路之一1借助反復(fù)的線性逼近把線性方法擴(kuò)展到非線性優(yōu)化問(wèn)題中來(lái)2采用罰函數(shù)把約束非線性問(wèn)題變換到一系列無(wú)約束問(wèn)題3采用可變?nèi)莶罘ㄒ员阃瑫r(shí)容納可行的和不可行的x矢量其中源于思路2的乘子罰函數(shù)法具有適合于等式及不等式約束 不要求初始點(diǎn)為嚴(yán)格內(nèi)點(diǎn)，甚至不要求其為可行點(diǎn)對(duì)自由度的大小無(wú) 任何要求等特點(diǎn)。1.3乘子法罰函數(shù)法的主要缺點(diǎn)在于需要懲罰因子趨于無(wú)窮大，才能得到

4、約 束問(wèn)題的極小點(diǎn)，這會(huì)使罰函數(shù)的hesse矩陣變得病態(tài)，給無(wú)約束問(wèn) 題的數(shù)值求解帶來(lái)很大問(wèn)題，為克服這一缺點(diǎn)，hestenes和powell 于1964年各自獨(dú)立地提出乘子法。所謂乘子法是：由問(wèn)題的lagrange 函數(shù)出發(fā)，考慮它的精確懲罰，從而將約束優(yōu)化問(wèn)題化為單個(gè)函數(shù)的 無(wú)約束優(yōu)化問(wèn)題，它同精確罰函數(shù)法一樣，具有較好的收斂速度和數(shù) 值穩(wěn)定性，且避免了尋求精確罰函數(shù)法中關(guān)于罰參數(shù)閾值的困難，它 們一直是求解約束優(yōu)化問(wèn)題的主要而有效的算法?？紤]如下非線性等式約束優(yōu)化問(wèn)題：(nep)min f (x)s. t. q(x) = °, i 二 1,2, ，！.設(shè)兀 為問(wèn)題(nep)的最

5、優(yōu)解，且它的lagrange函數(shù)為l(x, 2) = f(x) - x c(x)其中c(x)=(c(x)，c2(x),，c/(x) , 2 =(人，入，,&)t是與x相對(duì) 應(yīng)的lagrange的乘了向量。在一般正規(guī)假設(shè)條件(fritz john必要 條件)下，(譏才)是l(x9a)的穩(wěn)定點(diǎn)，即vxl(x) = 0o因此, 若能找到才，則厶幺才)的極小值是才,那么求解問(wèn)題(nep)轉(zhuǎn)化 成求解一個(gè)無(wú)約束極小化問(wèn)題。然而l(x,a)的極小值往往不存在。為了避免出現(xiàn)厶(兀刃的極小值不存在的問(wèn)題，我們構(gòu)造增廣 lagrange 函數(shù)如,力)=心“心)+扣(譏由于vx£(/,*) =

6、0,則vv(xz,cr) = vx£(x*, z) + ov c(x* )c(x*) = ovc(x*)c(x*) = 0 這樣x*是的一個(gè)穩(wěn)定點(diǎn)。由此可知，當(dāng)a = x時(shí)，適當(dāng)?shù)倪x取ct可以使0(x,/tq)的無(wú) 約束極小點(diǎn)就是問(wèn)題(nep)的最優(yōu)解。1.4乘子法的相關(guān)定理和引理引理設(shè)w是沁畀階矩陣，°為兀階向量，若對(duì)一切滿足 d0,atd = 0 ,均有dtwd>0 ,則存在a > 0 ,使當(dāng)(y>a時(shí)，矩陣 w +aaat 正定.證明考慮集合(4. 20)只需證明，vrfe k,當(dāng)時(shí)，有/(w+6i/)d>0.事實(shí) 上， vzo ,貝lj d=

7、 e k ,貝lj zt(w +(jaat)z>0 與 zdt (w aaat )d > 0 等價(jià).令k, = dd1wd<0,de k,若 k = 0 ,貝0 vrfe k,有 dtwd>0 ,因此 vcr>0 ,有 dj (w+(raar)d>djwd>0 因 此假設(shè) kt 0 , 當(dāng)w k/k 時(shí)，有 dtwd >09 因止匕 0<7>o, dt (yv + aaat )d > dtwd > 0.下而考慮de k由于k是有界閉集，則函數(shù)/wd與s%)2在k 上取到極小值，不妨設(shè)(da)twd與(atd(2)2分別為函

8、數(shù)的極小值，并 且曲j。；否則由定理?xiàng)l件,有(di2)twd>0與dwk矛盾因此>0,當(dāng)(7 n(j時(shí)，有dt(w +(yaat)rf = dtwd +(y(atd)2 > (j(l)rwrf(,)+<r(arrf尸 >0, 因此，vjg k, (4. 20)式成立.*定理1設(shè)兀 是問(wèn)題(nep)的最優(yōu)解，且滿足二階充分條件，其 相應(yīng)的lagrange乘子為才，則當(dāng)充分大時(shí)，x 為無(wú)約束優(yōu) 化問(wèn)題min=0(兀久 q)x的最優(yōu)解，且滿足二階充分條件。證 只要證明對(duì)于充分大的ct,使得= 0并且 v>(/,x,ct)為對(duì)稱(chēng)正定矩陣，則命題成立。由于x *是最優(yōu)

9、解所以q(x) = 0m = l,2，jv(/,z,<r)=w*)-zax*)i=lv(xz,(t)= v7(/)-2/l；v2cz(/) +(jbrb = va2l(/,z) + c«rb i=其中b = (vqcf),.,vc/(t)為hxl階的矩陣，有一階必要條 件知va.(/,/,ct) = o再有二階充分條件可知，若對(duì)任意的ywm(f) = y|by = o,且兀0, 有/v/l(x/)y >0成立.因此，存在a >0,使得v：厶(門(mén)才"bwb為對(duì)稱(chēng)正定矩陣事實(shí)上，只需要證明v/£(xx) +(y*brb在 = yern y =1上是正

10、定的即可.對(duì)任意的yeq,/(vx2l(x,x) + brb)y = ytvx2l(x,x)y + a by 2» /vx2l(xx)y故只需證存在/ 0使得vx2l(x,x) + cr*brb在q_ = ygq|/v,2£(/,z)；0 上正定.對(duì)任意的y w q_ ,(vx2l(/, x) + ct*brb) y + inf 叭|by其中(7為va2l(/,x)的最小特征值。下面只需證明密“by02若即by =°,則存在幾wq_,使得lim|by,| = o.因?yàn)?是有界序列，故有收斂了列，不妨設(shè)幾t.wq_,因此有 ypjux；才)y 5 0.又由于h=|b

11、limjj|=liml|byj|=okt8at8故ye m(x),這與ytvx2l(xx')y0矛盾，從而有2inf b)r >0，這就證明了對(duì)于充分大的 (t ,矩陣vv2l(/,/) + obrb是對(duì)稱(chēng)正定的。定理2對(duì)給定的入(i "2小和(70,設(shè)x*是無(wú)約束優(yōu)化問(wèn)題min=0(兀入6的最優(yōu)解，且滿足二階充分條件如果xc.(x ) = 0(/= 1,2,.,/),則t也是問(wèn)題(nep)的最優(yōu)解，且滿足 二階充分條件.1.5乘子罰函數(shù)法乘子罰函數(shù)法是解決非線性等式約束優(yōu)化問(wèn)題的一種重要方法，它具有不要求初始點(diǎn)為嚴(yán)格內(nèi)點(diǎn)，不要求其為可行點(diǎn)，對(duì)自由度的大 小無(wú)任何要求的

12、特點(diǎn),它利用lagrange乘子求近似解的方法逼近原 問(wèn)題最優(yōu)解，而不需要無(wú)窮大的罰因了，因此對(duì)它的研究有重要的理 論和實(shí)用價(jià)值最早的乘子罰函數(shù)法是由henstenes (1969)針對(duì)等 式約束問(wèn)題導(dǎo)出的，其形式為：增廣lagrange函數(shù)的另一種等價(jià)形式是在1969年rfl powell提出的, 其特征是對(duì)c;(x)進(jìn)行平移，即用代替c;(x), 0i是參數(shù)，由此 powell (1969)得到罰函數(shù):zy加2卩(兀入(t)= /(%)-才c(x)+ 牙工 £ (%) 一 0)2 i=i當(dāng)構(gòu)造岀函數(shù)0(xq)后，可以通過(guò)求解一個(gè)無(wú)約束問(wèn)題得到約束 問(wèn)題的最優(yōu)解但事實(shí)上，做到這一點(diǎn)

13、很困難.因?yàn)?(兀,6中的才未 知，在得到t之前，我們是無(wú)法知道它的為了克服上述困難的我們 用參數(shù)2代替；t,得到增廣lagrange函數(shù)也就是我們所說(shuō)的乘了罰 函數(shù)0(兀，入(t)= /(x)+ ac(x)+ c2(x)9考慮其相應(yīng)的無(wú)約束問(wèn)題min 0(兀入(7),其最優(yōu)解為x = x(a,ct).由前面定理1我們知道，只要當(dāng)7充分大(不一定趨于8),就 有l(wèi)im 元(入 er) = x .2t/t因此，要想求得只需要不斷的調(diào)整參數(shù)2使之逐漸接近最優(yōu)乘子；t.下面考慮如何調(diào)整參數(shù)使它逐漸接近才在給定於)s后，求解無(wú)約束問(wèn)題min 0(兀,2 ，q),其最優(yōu)解為兀.由無(wú)約束問(wèn)題的一階必要條件

14、有vj(x(k),於)qk)= vf(x(fc) + 爐)vc(兀)+ q c(兀)vc(x )=0, 當(dāng)q充分大吋，由卿元(入6 = t可知嚴(yán)=兀v/(兀)-v/(x ),vc(x(') - vc(x),因此有v/(*j + 2 +cr/lc(xu)vc(x") = 0而在t處，由約束問(wèn)題的一階條件有v/dj + ztvcg) = 0,所以有才q爐)+qc(x)，這樣得到乘子迭代公式2(d =z(k)+akc(xw).最后就是算法的終止準(zhǔn)則條件若嚴(yán)是無(wú)約束問(wèn)題的局部解，并且滿足c(嚴(yán))= 0,則有v/(f) +爐)vc(兀) = 0,因此,兀是約束問(wèn)題的k-t點(diǎn),爐)為相應(yīng)的乘子.有定理2知兀 是約束問(wèn)題(nep)的最優(yōu)解，停止計(jì)算因此其終止準(zhǔn)則為|c( )| < £其中£是指定的精度要求.1.6結(jié)論從原問(wèn)題的l