非線性規(guī)劃的理論與算法

1、第五章非線性規(guī)劃：理論和算法5.5約束優(yōu)化我們現(xiàn)在繼續(xù)討論更一般的有約束的線性優(yōu)化問(wèn)題。特別的，我們考慮一個(gè)具有非線性目標(biāo)函數(shù)和(或者)非線性約束的優(yōu)化問(wèn)題。我們可以將這種問(wèn)題表示為下面的一般形式：minxf(x)gi(x)0,i(5.10)gi(x)0,i在本節(jié)的末尾，我們假設(shè)f和gi,i全部是連續(xù)可微的。拉格朗日函數(shù)是研究有約束的優(yōu)化問(wèn)題的一個(gè)重要工具。為了定義這個(gè)函數(shù)，我們結(jié)合每個(gè)約束的乘子i稱作拉格朗日乘子。對(duì)于問(wèn)題(5.10)拉格朗日函數(shù)如下定義：L(x,):f(x)igi(x)(5.11)本質(zhì)上，我們考慮的是目標(biāo)函數(shù)違反了可行約束時(shí)的懲罰函數(shù)。選擇合適的i,最小化無(wú)約束函數(shù)Lx,等

2、價(jià)于求解約束問(wèn)題(5.10)。這就是我們對(duì)拉格朗日函數(shù)感興趣的最根本的原因。與這個(gè)問(wèn)題相關(guān)的最重要問(wèn)題之一是求解最優(yōu)問(wèn)題的充要條件。總之，這些條件稱為最優(yōu)性條件，也是本節(jié)的目的。在給出問(wèn)題(5.10)最優(yōu)性條件之前，我們先討論一個(gè)叫做正則性的條件，由下面的定義給出：定義5.1：設(shè)向量x滿足gi(x)0,i和gi(x)0,i。設(shè)J是使得gi(x)0等號(hào)成立的指標(biāo)集。x是問(wèn)題(5.10)約束條件的正則點(diǎn)，如果梯度向量gi(x)(iJ)相互線性無(wú)關(guān)。在上述定義中與J對(duì)應(yīng)的約束，即滿足gMx)0的約束稱為在x點(diǎn)處的有效約束。我們討論第一章提到的兩個(gè)優(yōu)化的概念，局部和全局?；仡?5.10)的全局最優(yōu)解向

3、量x,它是可行的而且滿足f(x)f(x)對(duì)于所有的x都成立。相比之下，局部最優(yōu)解x*是可行的而且滿足f(x*)f(x)對(duì)于x:|xx*|(0)成立。因此局部解一定是它鄰域的可行點(diǎn)中最優(yōu)的。下面我們考慮的最優(yōu)性條件僅僅判別局部解，則可能是全局最優(yōu)解，也可能不是。幸運(yùn)的是，這里存在一類局部最優(yōu)解和全局解一致的問(wèn)題一一凸優(yōu)化問(wèn)題。附錄A中討論的就是基于凸集的凸優(yōu)化問(wèn)題。定理5.1(一階必要條件)設(shè)x是問(wèn)題(5.10)的局部最小值，假設(shè)x是這個(gè)問(wèn)題的約束的正則點(diǎn)。則存在i,i使得：f(x)igi(x)0(5.12)i0,i(5.13)，*、Cigi(x)0,i(5.14)注意，(5.12)左邊表達(dá)的意

4、思是拉格朗日函數(shù)Lx,對(duì)每個(gè)變量x的梯度。一階條件在局部最小值，局部最大值及鞍點(diǎn)處滿足。當(dāng)目標(biāo)函數(shù)和約束函數(shù)是二次連續(xù)可微的時(shí)候，可以用函數(shù)的曲率排除最大值和鞍點(diǎn)。根據(jù)定理5.1,我們考慮拉格朗日函數(shù)Lx,和這個(gè)函數(shù)對(duì)每個(gè)變量x的海森矩陣，來(lái)計(jì)算目標(biāo)函數(shù)和約束函數(shù)在當(dāng)前點(diǎn)處的曲率。定理5.2(二階必要條件)假設(shè)函數(shù)f和gi(i)都是二次連續(xù)可微的。假設(shè)*.一、一.一一.x是問(wèn)題(5.10)局部取小值而且是這個(gè)問(wèn)題的約束正則點(diǎn)。則存在i,i滿足(5.12)(5.14)及下面的條件：2-*、2,*、f(x)igi(x)(5.15)在x處有效約束的切線子空間處是半正定的。、.、一.*定理后半部分可以

5、改寫為含有效約束的雅閣比矩陣的形式。設(shè)A(x)表示x處有效約束的雅閣比矩陣，設(shè)N(x)表示基于A(x)的零空間。則定理的最后一個(gè)條件等價(jià)于下面的條件：T*9_*9*N(x)f(x)igi(x)N(x)(5.16)是半正定的。二階必要條件并非常常保證給出的解的局部最優(yōu)性。局部最優(yōu)性的充分條件更加嚴(yán)格和復(fù)雜，因?yàn)橐紤]到退化的可能性。定理5.3(二階充分條件)假設(shè)函數(shù)f和gi都是連續(xù)二次可微的。同時(shí)假、1*設(shè)x是問(wèn)題(5.10)可行點(diǎn)而且是這個(gè)問(wèn)題的約束正則點(diǎn)。設(shè)A(x)表示x處有效約束的雅閣比矩陣，設(shè)N(x)表示基于A(x)的零空間。如果存在i,i滿足(5.12)一(5.14)及下面的條件:，*

6、、八一Cgi(x)0,1暗本i0(5.17)和T*2*2*N(x)f(x)igi(x)N(x)(5.18)是正定的，則x是問(wèn)題(5.10)的局部最小值。定理5.1、5.2和5.3中列出的條件稱作Karush-Kuhn-Tucker(KKT)條件，以它們的發(fā)明者命名的。一些求解約束優(yōu)化問(wèn)題的方法表達(dá)成一系列簡(jiǎn)單的可以用一般迭代步驟求出解的簡(jiǎn)單優(yōu)化問(wèn)題。這些“簡(jiǎn)單”的問(wèn)題可以是無(wú)約束的，此時(shí)可以應(yīng)用我們前面章節(jié)介紹的方法求解。我們?cè)?.5.1中考慮這些策略。在其他情況下，這些簡(jiǎn)單的問(wèn)題是二次規(guī)劃且可以應(yīng)用第七章中的方法求解。這個(gè)策略的典型例子是5.5.2中討論的連續(xù)二次規(guī)劃問(wèn)題。5.5.1廣義簡(jiǎn)約

7、梯度法在本節(jié)中，我們介紹一種求解有約束的非線性規(guī)劃的方法。這種方法建立在前文討論的無(wú)約束優(yōu)化法之最速下降法的基礎(chǔ)上的。這種方法的思想是利用約束減少變量的個(gè)數(shù)，然后用最速下降法去求解簡(jiǎn)化的無(wú)約束的問(wèn)題。線性等式約束首先我們討論一個(gè)約束是線性方程組的例子。minf(x)x；x2x；x4g1(x)x1x24x34x440g2(x)x1x22x32x420在其他變量給定情況下，很容易求解只有兩個(gè)變量的約束方程。給定Xi,4，令為3*8刈8和x3Xi3應(yīng)3。把這些變量代入目標(biāo)函數(shù)，然后得到下面簡(jiǎn)化的形式：22minf(x1,x4)x13為8x48x13x43x4這個(gè)簡(jiǎn)化形式是無(wú)約束的，因此可以利用5.4

8、.1節(jié)的最速下降法求解。例1：用最速下降法求minf(x)=f=(?-2)2+(y-4)2Matlab程序：M文件:functionR,n=steel(x0,y0,eps)symsx;symsy;f=(x-2)A4+exp(x-2)+(x-2*y)A2;v=x,y;j=jacobian(f,v);T=subs(j(1),x,x0),subs(j(2),y,y0);temp=sqrt(T(1)A2+(T(2)A2);x1=x0;y1=y0;n=0;symskk;while(temp>eps)d=-T;f1=x1+kk*d(1);f2=y1+kk*d(2);fT=subs(j(1),x,f1

9、),subs(j(2),y,f2);fun=sqrt(fT(1)A2+(fT(2)A2);Mini=Gold(fun,0,1,0.00001);x0=x1+Mini*d(1);y0=y1+Mini*d(2);T=subs(j(1),x,x0),subs(j(2),y,y0);temp=sqrt(T(1)A2+(T(2)A2);x1=x0;y1=y0;n=n+1;endR=x0,y0調(diào)用黃金分割法：M文件：functionMini=Gold(f,a0,b0,eps)symsx;formatlong;symskk;u=a0+0.382*(b0-a0);v=a0+0.618*(b0-a0);k=0;

10、a=a0;b=b0;array(k+1,1)=a;array(k+1,2)=b;while(b-a)/(b0-a0)>=eps)Fu=subs(f,kk,u);Fv=subs(f,kk,v);if(Fu<=Fv)b=v;v=u;u=a+0.382*(b-a);k=k+1;elseif(Fu>Fv)a=u;u=v;v=a+0.618*(b-a);k=k+1;endarray(k+1,1)=a;array(k+1,2)=b;endMini=(a+b)/2;輸入：R,n=steel(0,1,0.0001)R=1.999994136676423.99999120501463n=1非線

11、性等式約束現(xiàn)在考慮用一個(gè)線性方程去逼近一個(gè)擁有非線性約束問(wèn)題的可能性，而線性問(wèn)題就可以像上面的例子那樣解決。要了解如何工作的，考慮下面的例子，它和前面提到的例子類似，但是它的約束是非線性的。.一、22minf(x)x1x2x3x42g1(x)x1x24x34x4402g2(x)Xix22x32x420在當(dāng)前點(diǎn)X我們用Taylor級(jí)數(shù)逼近約束方程：g(x)g(x)g(x)xx于是：xixi_x2x2gi(x)(xix24x34x44)(2xi,1,4,4)_x3x3x4x4八一，一22xixix24x34x4(xi4)0和g2(x)xiX22x3又4乂4(x：2)0廣義簡(jiǎn)約梯度法(GRG)的思想

12、是求解一系列子問(wèn)題，每個(gè)子問(wèn)題可以利用約束的線性逼近。在算法的每一步迭代中，利用先前獲得的點(diǎn)重新計(jì)算線性化約束的點(diǎn)。一般來(lái)說(shuō)，即線性化的一個(gè)性質(zhì)是在使約束是線性逼近的，但每一步迭代獲得值也是逐步逼近最優(yōu)點(diǎn)的。最優(yōu)點(diǎn)，線性化的問(wèn)題和原問(wèn)題有相同的解。使用GRG的第一步是選擇一個(gè)初值。假設(shè)我們開(kāi)始設(shè)x00,8,3,0,而這個(gè)值恰好逼近公式，我們構(gòu)造的首個(gè)逼近問(wèn)題如下：minf(x)x2x2x2x4gi(x)x24x34x440g2(x)kx22&20程序思路與例i相似，具體參考例i程序。5.5約束優(yōu)化現(xiàn)在我們這個(gè)逼近問(wèn)題的等式約束，用其他變量表示其中的兩個(gè)變量。不妨選擇x2和x3,即得:I

13、-x22x14x48和x3-2x432把這些表達(dá)式代入目標(biāo)函數(shù)，獲得簡(jiǎn)化的問(wèn)題：22Iminf(xi,x4)%(2xi4x48)xi2x43x42求解這個(gè)無(wú)約束的最小化問(wèn)題，得到xi0.375x40.96875W代入上面表達(dá)式,得：x24.875x3i.25。因此GRG方法的第一步迭代產(chǎn)生了一個(gè)新點(diǎn)1X1(0.375,4.875,1.25,0.96875)繼續(xù)這個(gè)求解過(guò)程，在新點(diǎn)上我們重新線性化約束函數(shù)，利用獲得的線性方程組，把其中兩個(gè)變量用其他變量表示，然后代入目標(biāo)函數(shù)，就可以得到新的簡(jiǎn)化問(wèn)題，求解這個(gè)新的簡(jiǎn)化問(wèn)題得到新的點(diǎn)X2,依此類推。利用停止準(zhǔn)則|xk1Xk|T其中T=0.0025。我

14、們得到結(jié)果如下表5.7.k(班丁點(diǎn)由EW-F0(0.000,-8,000,3.000.0.000)L0003.7291(-0.375,-4.875,1,250,0.069)-2,2030.5722(-0.423,*5.131,1,619,0,620)-L7110.3533(-0.458,-4.792.L537t0,609)-LG100.0224i-0.478,-4.802,1,534,0,610)-L6110.0155(-0.488,-4.013.l,534t0X10)4,612(1.0086(-0.494,-4,018,1,534,0,610)-1,6120.004f(4),497,-4,8

15、21.L534,(LC10)-L612(1,0028(-0,498,4網(wǎng)L534,0.610)-1,612一*,一一、把這個(gè)結(jié)果同最優(yōu)解x(0.500,4.825,1.534,0.610)匕較，其目標(biāo)值是1.612。k觀察表5.7,注意到當(dāng)k1或k2時(shí)，函數(shù)f(x)的值有時(shí)比最小值小，這是怎么回事呢？原因是通過(guò)GRG方法計(jì)算獲得的點(diǎn)xk通常不滿足約束條件。它們只對(duì)這些約束條件的線性逼近可行。現(xiàn)在我們討論如何在一個(gè)不可行的點(diǎn)使用GRG方法：第一階段問(wèn)題是構(gòu)建一個(gè)滿足約束條件的點(diǎn)。第一階段的目標(biāo)函數(shù)是違反約束的絕對(duì)值總和。而第一階段問(wèn)題的約束都是不違反約束的。假設(shè)我們?cè)邳c(diǎn)x01,1,0,1開(kāi)始計(jì)算

16、，這個(gè)點(diǎn)不滿足第一個(gè)約束，但滿足第二個(gè)約束，所以第一階段問(wèn)題是：2min為x24x34x442x1x22x32x420一旦通過(guò)解決第一階段問(wèn)題獲得一個(gè)適宜的解，那么上面闡述的方法就可以用來(lái)求最優(yōu)解。線性不等式約束最后，我們討論GRG是怎樣像解決等式問(wèn)題那樣解決有不等式約束的問(wèn)題。在每次迭代中，只有嚴(yán)格滿足不等式約束的量才能進(jìn)入線性方程組，以消除變量(這些不等式約束通常被認(rèn)為是有效的)。這個(gè)過(guò)程是復(fù)雜的，由于為了得到好的結(jié)果，在當(dāng)前點(diǎn)的每一個(gè)不等式約束都有被舍棄的可能。我們?cè)谙旅娴睦又姓f(shuō)明了這一點(diǎn)。1252minf(Xi,X2)(Xi)(X2-)22Xx20x10x20x22圖5.5廣義簡(jiǎn)約梯

17、度算法的過(guò)程這個(gè)問(wèn)題的可行集合顯示在圖5.5中。圖中的可行箭頭表示由每個(gè)約束指向的可行的超平面。假設(shè)我們從x°(1,0)開(kāi)始。這一點(diǎn)滿足所有約束條件。從圖5.5可以看出：xix20,為0,x22三個(gè)約束條件是無(wú)效的，而約束x20是有效的。我們必須決定x2是否應(yīng)該留在它的下界還是允許它離開(kāi)邊界。f(x°)2xi01,2x051,5。這表明如果我們沿方向d0f(x°)1,5移動(dòng)，f減少的最多，即減少x1增大x2因?yàn)檫@個(gè)方向朝向可行區(qū)域內(nèi)部，我們決定從邊界釋放x2。新的點(diǎn)變成x1x00d0o其中00。這個(gè)約束引入了0的一個(gè)上限，也就是00.8333。接下來(lái)我們通過(guò)線性搜

18、索來(lái)確定0在這個(gè)范圍之內(nèi)的最優(yōu)值。結(jié)果是00.8333,從而x10.8333,0.8333;參見(jiàn)圖5.5?，F(xiàn)在，我們重復(fù)這個(gè)過(guò)程：約束x1x20開(kāi)始起作用，其他約束失效。因?yàn)榛顒?dòng)約束不是一個(gè)簡(jiǎn)單的上下限約束，我們引入一個(gè)剩余變量x3,然后將其中之一用其余變量表示。代入x1x2x3,我們得到如下化簡(jiǎn)的優(yōu)化問(wèn)題minfx2,x315X2一220x22X30在(X2,X3)10.8333,0簡(jiǎn)約梯度為f(x2,x3)2x22x312x25,2x22x312.667,0.667因此f在2.667,0.667方向降幅最大，也就是要增大x2并減小x3。但是x3已經(jīng)到達(dá)其下界，我們無(wú)法再減小它。因此我們保持

19、x3在它的下界處，即我們沿方向d12.667,0到達(dá)新的點(diǎn)(x2,x3)2(x2,x3)11d1。沿這個(gè)方向的線性搜索給出10.25,(x2,x3)21.5,0。接下來(lái)仍然是該約束有效，所以我們?nèi)匀辉赬2和X3的空間中。在(x2,x3)21.5,0處的梯度f(wàn)(x2,x3)0,2與當(dāng)前解X2的邊界線垂直，且指向可行區(qū)域的外部，因而f不可能進(jìn)一步減小。于是我們找到了最優(yōu)解。對(duì)應(yīng)于最初的變量空間，這個(gè)最優(yōu)解就是為1.5和x21.5。這就是一些廣泛使用的非線性規(guī)劃求解方法，例如Excel的SOLVER,GINO,CONOPT,GRG2以及一些其他的方法用來(lái)求解非線性規(guī)劃問(wèn)題的方法。具體求解時(shí)只需附加一

20、些額外細(xì)節(jié)，例如線性搜索時(shí)的Newton-Raphson方向等。同線性規(guī)劃相比，能夠在一個(gè)合理的計(jì)算時(shí)間內(nèi)解決的問(wèn)題通常規(guī)模比較小，并且求得的結(jié)果也可能不是特別精確。另外，可行集合或目標(biāo)函數(shù)潛在的非凸性會(huì)導(dǎo)致求解結(jié)果是局部最優(yōu)的而遠(yuǎn)非全局解。因此在解釋非線性規(guī)劃的結(jié)果時(shí)需要更加小心。5.5.2序列二次規(guī)劃考慮一般的非線性最優(yōu)化問(wèn)題(5.20)minxf(x)gi(x)0,igi(x)Qi為了解決這個(gè)問(wèn)題，有人試圖利用可得到的較好的算法解決更有條理、更簡(jiǎn)單的二次規(guī)、k劃(參見(jiàn)第七章)。這是連續(xù)二次方程背后的思想。在當(dāng)前可行點(diǎn)x,問(wèn)題(5.20)是由一個(gè)二次規(guī)劃來(lái)近似的：拉格朗日函數(shù)的近似二次方程

21、可以像近似的線性約束一樣計(jì)算?？梢缘玫饺缦碌亩畏匠桃?guī)劃問(wèn)題：其中BkkTminf(x)x_/k、Tgi(x)xkTgi(x)x:L(xk,k),是拉格朗日函數(shù)1k-xx2k、gi(x)k、gi(x)(5.11)TBkxxk0,i0,i(5.21)的海森矩陣，k為當(dāng)前估計(jì)的拉格朗日乘數(shù)。例如我們?cè)诘谄哒掠懻摰倪@個(gè)問(wèn)題可以用解決二次方程規(guī)劃問(wèn)題的一種特殊算法來(lái)解,內(nèi)點(diǎn)方法。二次規(guī)劃的最優(yōu)解是用來(lái)確定搜索方向。那么線性搜索或信賴域程序是為了確定下一個(gè)迭代。也許思考序列二次規(guī)劃的最好方式是將其作為求解有約束條件問(wèn)題的牛頓法的優(yōu)化版的擴(kuò)展?；叵胍幌拢ｎD方法的優(yōu)化版使用目標(biāo)函數(shù)的二次逼近，定義這個(gè)逼近

22、的最小值作為下一次迭代值，這很像我們描述的SQP方法。的確，對(duì)于一個(gè)無(wú)約束問(wèn)題，二次規(guī)劃與牛頓法是相同的。對(duì)于約束問(wèn)題，在解決SQP時(shí)的二次規(guī)劃問(wèn)題的最優(yōu)性條件相當(dāng)于在當(dāng)前迭代下牛頓法直接指向的原來(lái)問(wèn)題的最優(yōu)化條件。序列二次規(guī)劃迭代直到該問(wèn)題收斂。就像牛頓法一樣，二次規(guī)劃方法是非常強(qiáng)大，尤其是當(dāng)運(yùn)用線性搜索或信賴域方法來(lái)處理非線性和非凸性。我們推薦讀者翻閱BoggsandTolle14和NocedalandWright55來(lái)進(jìn)一步了解二次規(guī)劃方法。5.6非光滑優(yōu)化：次梯度方法在這一部分，我們考慮無(wú)約束非線性規(guī)劃的形式minfx當(dāng)x>,x2,xn并且f是一個(gè)不可微的凸函數(shù)。由于在此情況下沒(méi)有定義梯度，所以無(wú)法獲得基于梯度的最優(yōu)條件。然而，梯度的概念可被推廣如下。f在x*點(diǎn)的次梯度是向量s*s*,s2,sn使*一s(xx)f(x)f(x)對(duì)任意x都成立。當(dāng)函數(shù)f是可微的，次梯度和梯度是相同的；當(dāng)函數(shù)f在x點(diǎn)處不可微，通常在x處有