優(yōu)化設(shè)計的數(shù)學基礎(chǔ)

1、第二章優(yōu)化設(shè)計的數(shù)學基礎(chǔ)優(yōu)化設(shè)計中絕大多數(shù)是多變量有約束的非線性規(guī)劃問題，即是求解多變量非線性函數(shù)的極值問題。由此可見，優(yōu)化設(shè)計是建立在多元函數(shù)的極值理論基礎(chǔ)上的，對于無約束優(yōu)化問題為數(shù)學上的無條件極值問題，而對于約束優(yōu)化問題則為數(shù)學上的條件極值問題。本章主要敘述與此相關(guān)的數(shù)學基礎(chǔ)知識。第一節(jié)函數(shù)的方向?qū)?shù)與梯度一、函數(shù)的方向?qū)?shù)一個二元函數(shù)F（x1,x2）在點Xo（xx0處的偏導數(shù)，即函數(shù)沿坐標軸方向的變化率定義為：dF（X。）=5-一+5，戈；）方,只）8必一。AX°.lim尸-尸劉）i"-llrn1一Ox250Ax2而沿空間任一方向S的變化率即方向?qū)?shù)為：dF（xQ）

2、尸（工；+必十樂）-/（4只）dS"0p3F（X。）戶（"+Ax”只+5）-FCx?，K一二1LimdSp-lim-聞）一尸«，只1g口沁尸（只十3戶：+工）-2時十幽,也但“II汽rUIII乂戶p戶/AX2pdF（XQ）q5F（Xe）八=;COS4+-COS仇%dx2.方向?qū)?shù)與偏導數(shù)之間的數(shù)量關(guān)系為依此類推可知n維函數(shù)F（x1,x2，xn）在空間一點X°x1°,x0；",x0幅S方向的方向?qū)?shù)為圖2-1二維空間中的方向圖2-2三維空間中的方向、函數(shù)的梯度函數(shù)F（X）在某點X的方向?qū)?shù)表明函數(shù)沿某一方向S的變化率般函數(shù)在某一確定點沿

3、不同方向的變化率是不同的。為求得函數(shù)在某點X的方向?qū)?shù)為最大的方向，引入梯度的概念。dF(X)dS3F(X)a5cosa+dF(X)dxz令:VF(X)=3F(X)6戶(X)*Sx2仍以二元函數(shù)F（x1,x2）為例進行討論，將函數(shù)沿方向S的方向?qū)?shù)寫成如下形式稱為F（x1,x2）在點X處的梯度gradF（X）,而同時設(shè)S為單位向量S=1Pos9產(chǎn)cos區(qū)于是方向?qū)?shù)可寫為：哼答=MxW,S=收尸（X）|網(wǎng)CO*F（X%S）（7»此式表明，函數(shù)F（X）沿S方向的方向?qū)?shù)等于向量wFX）在S方向上的投影。且當cosTF（X）,S）=1,即向量F（X）與S的方向相向時，向量F（X）在S方向

4、上的投影最大，其值為,F（X1這表明梯度F（X）是函數(shù)F（X）在點X處方向?qū)?shù)最大的方向，也就是導數(shù)變化率最大的方向。上述梯度的定義和運算可以推廣到n維函數(shù)中去，即對于n元函數(shù)F（x1,x2，xn）,其梯度定義為F（X）=L犯，a2,，J由此可見，梯度是一個向量，梯度方向是函數(shù)具有最大變化率的方向。即梯度節(jié)F（X）方向是函數(shù)F（X）的最速上升方向，而負梯度-F（X）方向則為函數(shù)F（X）的最速下降方向。JC例2-1求元函數(shù)F（X）=-x12x2在X0=11,1"點沿S1=12=311二二23心必.的萬向?qū)?shù)。6冗x1FXxix2I,將X0=11,1T代入可得2x2119一F(X)=I,

5、因此ILI-4aF(X0)3尸(X0)ox£。的十過區(qū)2.仇建1dx222cosJTIt7E1,./F-COS1,666444dF(XG)=CO3-COS-】465其變化率也不同。S2方向的變化率。這說明同一函數(shù)在不同方向上的方向?qū)?shù)不同，函數(shù)F（X）由X0由發(fā)，沿&方向的變化率大于沿所以，函數(shù)F（X）沿&方向增長得較快。第二節(jié)凸集、凸函數(shù)與凸規(guī)劃如果函數(shù)在整個可行域中有兩個或兩個以上的極值點，則稱每一個極值點為局部極值點。在整個可行域中，函數(shù)值最小的點為全域極值點。為求得全域極值點，以獲得最好的可行設(shè)計方案，就需要進一步討論局部最小點和全域最小點的關(guān)系，因而涉及到凸

6、集、凸函數(shù)及凸規(guī)劃問題。一、凸集設(shè)D為n維歐氏空間內(nèi)的一個集合，如果D內(nèi)任意兩點X1和X2的連線整個都包圍在D內(nèi)，即對于任意實數(shù)支（0三支w1）,點«X1+（1-）X2仁D,則稱這種集合為凸集，如圖2-3a所示，否則為非凸集，如圖2-3b、c所示。凸集滿足以下性質(zhì)：若D是一個凸集，人是一個實數(shù)，則集合KD仍為凸集；若D與F均為凸集，則其和（或并）還是凸集；任何一組凸集的積（或交）還是凸集。圖2-3凸集a）與非凸集b）、c）、凸函數(shù)設(shè)D為En中的一凸集，F(xiàn)（X）為定義在D上的一個函數(shù)，若對于任意實數(shù)0（0£"w1）和D內(nèi)任意兩點X1和X2,恒有FQY1+（I-幻牙工

7、）/（*）+（Ia）F（X）則F（X）為D上的凸函數(shù)；若式中不等號反向，則為凹函數(shù)。凸函數(shù)的幾何意義如圖2-4所示。若F（X）在區(qū)間a,b內(nèi)為凸函數(shù)，則曲線上任意兩點A、B間（與X1和X2相對應(yīng)）所連成直線上的點K'總不會落在這兩點間曲線的下方，即大于相應(yīng)點K的函數(shù)值。因而，若F（X）為凸函數(shù)，則一為凸函數(shù)，又可視為凹函數(shù)。凸函數(shù)的性質(zhì)：圖2-4凸函數(shù)的幾何含義F（X）為凹函數(shù)；線性函數(shù)既可視1）設(shè)取F（X）為定義在凸集D的凸函數(shù)，則對于任意正實數(shù)九,函數(shù)九F（X）在D上也是凸函數(shù);2）設(shè)F1（X）、F2（X）為定義在凸集D上的凸函數(shù)，則函數(shù)F（X）=F1（X）+F2（X）在D上也是凸

8、函數(shù)：3）若函數(shù)F（X）在n維歐氏空間En一階可微，則對于任意X1,X2亡EnX1#X2,F（X）為凸函數(shù)的充分必要條件為（其證明可參見教材p.26）FX2-FX1FX1TX2-X1圖2-5一維凸函數(shù)圖2-5所示為一維函數(shù)情況，其凸函數(shù)的幾何意義在于函數(shù)曲線永遠在切線的上面。若F（X）是凸集D上的凸函數(shù)，并且在D內(nèi)有極小點，則極小點是唯一的。最優(yōu)化方法中很多結(jié)論都是以函數(shù)具有凸性為前提的。三、凸規(guī)劃對于約束優(yōu)化問題mi口產(chǎn)A"st.gv（X）WO.u=U2,m式中，若F（X）、gu（X）、u=1,2,，n均為凸函數(shù)，則稱此問題為凸規(guī)戈fj。凸規(guī)劃的性質(zhì)：1）可行域Xgu（X）w0,u

9、=1,2,，M為凸集。2）凸規(guī)劃問題的任何局部最優(yōu)解都是全局最優(yōu)解。/(A)3）若F（X何微，則X”為凸規(guī)劃問題的最優(yōu)解的充分必要條件是：對于X亡D,都滿足（X-X-0（該式表明在X沖的鄰域內(nèi)的所有點的目標函數(shù)值均大于X沖處的值）但在實際應(yīng)用中，要證明一個線性規(guī)劃問題是否為凸規(guī)劃，一般比較困難，有時甚至比求解一個優(yōu)化問題還要麻煩得多，尤其對一些工程問題，由于其數(shù)學模型的性態(tài)都比較復雜，更難以實現(xiàn)。因此，在優(yōu)化設(shè)計的求解時，就不必花精力進行求證，而通常是從幾個初始點生發(fā)，看它是否能收斂于同一點上，否則從求得的幾個方案中，選取相對較好的方案，作為最優(yōu)設(shè)計的結(jié)果，也就是從局部最優(yōu)解的比較中來選取全局

10、的最優(yōu)解第三節(jié)無約束優(yōu)化問題的極值條件優(yōu)化問題的幾何表達只能形象地給由最優(yōu)解的有關(guān)概念，而最優(yōu)解數(shù)值的求得，還得靠必要的定量計算來達到。這種運算的理論依據(jù)是函數(shù)的極值理論，因而有必要對其有關(guān)概念作必要的回顧和介紹。多元目標函數(shù)的表達形式往往十分復雜，為了便于討論，需用簡單的函數(shù)作局部逼近，使其簡化。用泰勒展開式求目標函數(shù)在某點鄰近的近似表達式，則是常用的方法。一、多元函數(shù)的泰勒展開式一元函數(shù)F（X）在Xk點的泰勒展開式為尸（工）二尸（/）+尸（）（元一，）+尸”（/）（工一，）2+3而多元函數(shù)F（X）在Xk點的泰勒展開式為F(X)二產(chǎn)(M)+之咒(X")al5Ap一：:FXk2FXk

11、,_,式中，F(xiàn)為函數(shù)在Xk點處對Xi的偏導數(shù)；F為函數(shù)在XjXjXjXk點處對Xi、Xj的二階偏導數(shù)；Xi、Xj分別表示變量X的第i和j個分量；n為變量的個數(shù)。若用向量矩陣表示，可寫為:XJ-I區(qū)-片）=dF(Xk)dF(Xk)ar(x*)巧一工:X2X2Xn-xp(=Mx)r(X-XfJ=V1產(chǎn)(X*X*-X，)£誓爭（t；）ry=i3才嚴盯叩一吃外7”£f|嚴尸(X*)小F(X*)dxy'8x18x2，dx28xdxl，:dxndx*dxndx2''dx.dxIN3F(X*)*dx2dxHd2F(Xk)ax；/一事X22=(X-xkyxx-x*)

12、因此，多元函數(shù)F（X）在Xk點的泰勒展開式可用向量矩陣形式表達為F(X)=F(Xk)+VTF(X*XJf-)+-(X-X*)1V2F(Xk)(X-Xk)2,其中,VF(X*)=即(X：)麗(X，)dxx'Sx28巴X')dxMfI為F（X在Xk點的一階偏導數(shù)的列向量，稱為梯度;V2F(Xk)=Gk；'dxydx2d2F(Xk)dJF(X：)dx2dxydxd2FXk)d2FXk)貴/(*')'dxdxnf(x。3x.9x.JJrd2F(Xk)=HX)以曾用dxdxnII同，dxl為F（X在Xk點的二階偏導數(shù)矩陣，由于函數(shù)的二次連續(xù)性，它是一個nXh階的對

13、稱方陣，統(tǒng)稱為函數(shù)F（X）在點Xk的海色（Hessian）矩陣。在優(yōu)化設(shè)計中，目標函數(shù)取到自變量（設(shè)計變量）的二次函數(shù)表達式已足夠準確（這稱為目標函數(shù)的平方近似表達式），因為數(shù)學上己證明：對于非標準球面或橢球拋物面的一般非線性目標函數(shù)（即高次函數(shù)），在其極值點附近的等值線簇仍為同心橢圓簇，即目標函數(shù)在極值點附近是二次函數(shù)。止匕外，二次函數(shù)的某些特征還為一些高效尋優(yōu)方法的建立提供了理論依據(jù)，因此要重視二次函數(shù)。這樣，對多元函數(shù)的泰勒展開式只取前三項就可以，記為如下形式：二、無約束優(yōu)化問題的極值條件從高等數(shù)學可知，一元函數(shù)存在極值點的必要和充分條件是：函一一一一_Fx_,一一一.，數(shù)的一階導數(shù)上力

14、=F'（x）=0（即找到駐點）和二階導數(shù)x2Fx9=F''（x）#0。當F''（x）0時為極大；F''（x）0時為極小。x類似地，對于n元函數(shù)F（X）=5（242出）的無約束極值問題minF（XXeRrt點X”為一個局部極值點的充分必要條件是：一一FX1）一階導數(shù)向用7F（X）=0,即=0i=1,2，n;x,2）二階導數(shù)矩陣,即海色矩陣v2F（X*）為正定或負定，即10d2F(Xk)d2F(Xk)d2F(Xdxfax、?小尸(*)d2FXk)d2FXk)已尸(X)"萬孤，8%呢=N(X)s5(k)d2FXk)3/(X*).一_二

15、為正定或負定，且當H（X”為正定時X為極小點；當H（X'）為負定時X為極大點。（其證明可參見教材p.2022）判斷矩陣A正定或負定的方法是檢驗其各階順序主子式，若各階順序主子式均大于0,如下：則A為正定矩陣；若各階順序主子式行列式值正負號交替由現(xiàn)，則為負定矩陣。若不滿足正負定矩陣條件則為不定矩陣，則不可采用上述方法計算極值。例2-2求函數(shù)F（x1,x2）=x,+x2-4x1-4x2+7的極值。dF(X)2x-4=0解：根據(jù)極值的必要條件求駐點dF(X)得到駐點X，24T再根據(jù)極值的充分條件，判斷此點是否為極值點。由于11d2F(Xv)徽產(chǎn)(X')dxt8x2d2F(X)01Hg

16、=其各階主子式均大于0,即H(X“)為正定，故X"=2,41T為極小點，極小值為FX=13第四節(jié)約束優(yōu)化問題的極值條件求解約束優(yōu)化問題stg.(X)WO(“=L2,，加)=0(k12田)求解上述問題的實質(zhì)是在所有的約束條件所形成的可行域內(nèi)，求得目標函數(shù)的極值點，即約束最優(yōu)點。由于約束最優(yōu)點不僅與目標函數(shù)本身的性質(zhì)有關(guān)，還與約束函數(shù)的性質(zhì)有關(guān)，因此約束條件下的優(yōu)化問題比無約束條件下的優(yōu)化問題更為復雜。庫恩-塔克(Kuhn-Tucker)條件(簡稱K-T條件)是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，通常借助庫恩-塔克條件來判斷和檢驗約束優(yōu)化問題中某個可行點是否為約束極值點，即將K-T條件

17、作為確定一般非線性規(guī)劃問題中某點是否為極值點的必要條件，對于凸規(guī)劃問題，K-T條件同時也是一個充分條件。但是如何判別所找到的極值點是全域最優(yōu)點還是局部極值點，至今還沒有一個統(tǒng)一而有效的判別方法。K-T條件可闡述為：若X坤是一個局部極小點,則該點的目標函數(shù)梯度7F(X“)可表示52F(X*)dx2dx1122>0,=4>0成諸約束面梯度VgJX*）和whv（X”）的線性組合的負值，即2*）=/£兒"T）十£入隊.）、|1【Ij式中，q為設(shè)計點處的不等式約束面數(shù)；j為設(shè)計點處的等式約束面數(shù)；%（u=1,2，q）、？、v（v=1,2，j）為非負值的乘子，也稱

18、為拉格朗日乘子。式中，在點X沖處不起作用的約束條件gu（X）對應(yīng)的義一定為零，只有當某一約束gjX）在點X”為起作用約束時，九u才可以不為零。如果是約束最優(yōu)解，則必然滿足上式。對凸規(guī)劃問題而言，K-T條件不僅是確定約束極值點的必要條件，同時也是充分條件。凸規(guī)劃問題有唯一的K-T點，但它所對應(yīng)的拉格朗日乘子不一定是唯一的。K-T條件的幾何意義在于：如果X”是一個局部極小點，則該點的目標函數(shù)梯度嚇（X）應(yīng)落在該點諸約束面（所有起作用的約束條件）梯度VgjX“）和hjX“）在設(shè)計空間所組成的錐角范圍內(nèi)。如圖2-6所示，圖2-6a中設(shè)計點X*不是約束極值點，圖2-6b的設(shè)計點X*是約束極值點。（其求證

19、可參見教材p.32）圖2-6K-T條件的幾何意義a）設(shè)計點xM1不是約束極值點；b）設(shè)計點XJt1是約束極值點13現(xiàn)在通過圖2-7所示的二維問題說明上述幾何意義。圖2-7表示汰）b）圖2-7約束極值點存在的條件a）設(shè)計點xk不是約束極值點；b）設(shè)計點X"是約束極值點在設(shè)計點X卜處有兩個約束，且目標函數(shù)及約束條件均為凸函數(shù)的情況。圖2-7a中，Xk點處目標函數(shù)的負梯度為-F（Xk）,兩約束函數(shù)的梯度分別為ggXXk）、ggXXk）,止匕時-VF（Xk）位于vgjXk）和Vg2（Xk組成的錐角之外，這樣在Xk點附近的可行域內(nèi)存在目標函數(shù)比F（Xk更小的設(shè)計點，故點X卜不能成為約束極值點。圖2-7b中