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

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

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

3、量x,它是可行的而且滿足f(x)f(x)對于所有的x都成立。相比之下，局部最優(yōu)解x*是可行的而且滿足f(x*)f(x)對于x:|xx*|(0)成立。因此局部解一定是它鄰域的可行點中最優(yōu)的。下面我們考慮的最優(yōu)性條件僅僅判別局部解，則可能是全局最優(yōu)解，也可能不是。幸運的是，這里存在一類局部最優(yōu)解和全局解一致的問題一一凸優(yōu)化問題。附錄A中討論的就是基于凸集的凸優(yōu)化問題。定理5.1(一階必要條件)設(shè)x是問題(5.10)的局部最小值，假設(shè)x是這個問題的約束的正則點。則存在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,對每個變量x的梯度。一階條件在局部最小值，局部最大值及鞍點處滿足。當(dāng)目標(biāo)函數(shù)和約束函數(shù)是二次連續(xù)可微的時候，可以用函數(shù)的曲率排除最大值和鞍點。根據(jù)定理5.1,我們考慮拉格朗日函數(shù)Lx,和這個函數(shù)對每個變量x的海森矩陣，來計算目標(biāo)函數(shù)和約束函數(shù)在當(dāng)前點處的曲率。定理5.2(二階必要條件)假設(shè)函數(shù)f和gi(i)都是二次連續(xù)可微的。假設(shè)*.一、一.一一.x是問題(5.10)局部取小值而且是這個問題的約束正則點。則存在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)的零空間。則定理的最后一個條件等價于下面的條件：T*9_*9*N(x)f(x)igi(x)N(x)(5.16)是半正定的。二階必要條件并非常常保證給出的解的局部最優(yōu)性。局部最優(yōu)性的充分條件更加嚴(yán)格和復(fù)雜，因為要考慮到退化的可能性。定理5.3(二階充分條件)假設(shè)函數(shù)f和gi都是連續(xù)二次可微的。同時假、1*設(shè)x是問題(5.10)可行點而且是這個問題的約束正則點。設(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是問題(5.10)的局部最小值。定理5.1、5.2和5.3中列出的條件稱作Karush-Kuhn-Tucker(KKT)條件，以它們的發(fā)明者命名的。一些求解約束優(yōu)化問題的方法表達(dá)成一系列簡單的可以用一般迭代步驟求出解的簡單優(yōu)化問題。這些“簡單”的問題可以是無約束的，此時可以應(yīng)用我們前面章節(jié)介紹的方法求解。我們在5.5.1中考慮這些策略。在其他情況下，這些簡單的問題是二次規(guī)劃且可以應(yīng)用第七章中的方法求解。這個策略的典型例子是5.5.2中討論的連續(xù)二次規(guī)劃問題。5.5.1廣義簡約

7、梯度法在本節(jié)中，我們介紹一種求解有約束的非線性規(guī)劃的方法。這種方法建立在前文討論的無約束優(yōu)化法之最速下降法的基礎(chǔ)上的。這種方法的思想是利用約束減少變量的個數(shù)，然后用最速下降法去求解簡化的無約束的問題。線性等式約束首先我們討論一個約束是線性方程組的例子。minf(x)x；x2x；x4g1(x)x1x24x34x440g2(x)x1x22x32x420在其他變量給定情況下，很容易求解只有兩個變量的約束方程。給定Xi,4，令為3*8刈8和x3Xi3應(yīng)3。把這些變量代入目標(biāo)函數(shù)，然后得到下面簡化的形式：22minf(x1,x4)x13為8x48x13x43x4這個簡化形式是無約束的，因此可以利用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)在考慮用一個線性方程去逼近一個擁有非線性約束問題的可能性，而線性問題就可以像上面的例子那樣解決。要了解如何工作的，考慮下面的例子，它和前面提到的例子類似，但是它的約束是非線性的。.一、22minf(x)x1x2x3x42g1(x)x1x24x34x4402g2(x)Xix22x32x420在當(dāng)前點X我們用Taylor級數(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廣義簡約梯度法(GRG)的思想

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

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

14、們得到結(jié)果如下表5.7.k(班丁點由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一*,一一、把這個結(jié)果同最優(yōu)解x(0.500,4.825,1.534,0.610)匕較，其目標(biāo)值是1.612。k觀察表5.7,注意到當(dāng)k1或k2時，函數(shù)f(x)的值有時比最小值小，這是怎么回事呢？原因是通過GRG方法計算獲得的點xk通常不滿足約束條件。它們只對這些約束條件的線性逼近可行?，F(xiàn)在我們討論如何在一個不可行的點使用GRG方法：第一階段問題是構(gòu)建一個滿足約束條件的點。第一階段的目標(biāo)函數(shù)是違反約束的絕對值總和。而第一階段問題的約束都是不違反約束的。假設(shè)我們在點x01,1,0,1開始計算

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

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

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

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

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

21、可以像近似的線性約束一樣計算?？梢缘玫饺缦碌亩畏匠桃?guī)劃問題：其中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)前估計的拉格朗日乘數(shù)。例如我們在第七章討論的這個問題可以用解決二次方程規(guī)劃問題的一種特殊算法來解,內(nèi)點方法。二次規(guī)劃的最優(yōu)解是用來確定搜索方向。那么線性搜索或信賴域程序是為了確定下一個迭代。也許思考序列二次規(guī)劃的最好方式是將其作為求解有約束條件問題的牛頓法的優(yōu)化版的擴(kuò)展。回想一下，牛頓方法的優(yōu)化版使用目標(biāo)函數(shù)的二次逼近，定義這個逼近

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