(整理)第2章最優(yōu)化問題數(shù)學(xué)基礎(chǔ)

1、精品文檔精品文檔第二章最優(yōu)化問題數(shù)學(xué)基礎(chǔ)為了便于學(xué)習(xí)最優(yōu)化方法，本章將對與優(yōu)化方法密切相關(guān)的數(shù)學(xué)知識(shí)作一簡要介紹，而有些數(shù)學(xué)知識(shí)將在講解各種算法時(shí)，隨之介紹.§2.1二次型與正定矩陣、二次型與實(shí)對稱矩陣二次型理論在最優(yōu)化設(shè)計(jì)中應(yīng)用十分廣泛.應(yīng)用矩陣的乘法運(yùn)算，二次型與實(shí)對稱矩陣緊密地聯(lián)系在一起了，從而二次型的基本問題又可轉(zhuǎn)化成實(shí)對稱矩陣問題.二次型理論問題起源于化二次曲線和二次曲面的方程為標(biāo)準(zhǔn)形式的問題.推廣到n維空間中，二次超曲面的一般方程為f（Xi，X2,，Xn） =anXi2 +a12XX2 +一 + amXiXn用矩陣表示可簡記為a2n X2Xn,2an1XnX1an2XnX

2、2annXnn n=工工 aij XiX j 'y jmn nf （Xi, X2,，Xn ） =£ Z aj X Xj =Xi, X2,，Xn Ay j 3XT AX ,X22其中矩陣A的元素aij =aji (i 'J)正是二次型的XiXj項(xiàng)的系數(shù)的一半，a"是二次型的Xi項(xiàng) 的系數(shù).因此，二次型和它的矩陣A是相互唯一決定的，且 A = AT .二、正定矩陣定義2.i如果二次型n nf （Xi, X2,，Xn） =£ £ ajXiXj =XTAX對于任何一組不全為零的數(shù)i i j dX1> X2>, Xn 恒有MB，Xn）=

3、XTAX,o,非零向量X其值總為正.類似可以給出定義，若二次型f（X1，X2,，Xn） =XTAX 對于所有f（X1,X2,，Xn）=XTAX 之 0 則 A則稱"Xi,%,，)正定, 簡言之，一個(gè)對稱矩陣且二次型矩陣 A也稱為正定.A如果是正定的，則二次型為半正定矩陣；若 XTAX <0 ,則A為半負(fù)定矩陣；若二次型 X T AX既不是半正定又不是半 負(fù)定，就稱矩陣A為不定的.矩陣A為正定的充要條件是它的行列式 | A |的順序主子式全部大于零，即a11a12IIIan-a11a12.a21a22IIIa2nan >0,"III，>0a21a22IIII

4、IIHIan1an2IIIann由此可見，正定矩陣必然是非奇異的.4 2 1A= 2 3 0例2.1判斷矩陣1 0 2 .是否正定.44 >0,210 =13 >02§2.2 方向?qū)?shù)與梯度一、方向?qū)?shù)所謂方向?qū)?shù)的概念是作為偏導(dǎo)數(shù)的一個(gè)推廣而引入的，它主要研究函數(shù)沿任一給定方向的變化率.n1定義2.2設(shè)f ： R t R在點(diǎn)X。處可微，P是固定不變的非零向量，e是方向P上的單位向量，則稱極限開(X。)f(X0 te) f(X。)二 limcPJ0+t(2.1)開(X0)為函數(shù)f(X)在點(diǎn)X0處沿P方向的方向?qū)?shù)，式中 P 是它的記號(hào).定義2.3設(shè)f： RnT R1是連續(xù)

5、函數(shù)，X0三Rn, P- Rn且P#0,若存在6>0, 當(dāng)tw(0,6)時(shí)都有f(X0+tP)<f(X°),則稱P為f在點(diǎn)X0處的下降方向.若 f(X0+tP)Af(X0),則稱P為f在點(diǎn)X0處的上升方向.由以上兩個(gè)定義可立刻得到如下的結(jié)論：fX2：.0fX2.0若 P ，則f(X)從X0出發(fā)在X0附近沿P方向是下降；若 P ，則f(X) 從X0出發(fā)在X0附近沿P方向是上升.g：0事實(shí)上，若印 ，則當(dāng)t>0充分小時(shí)，根據(jù)式(2.1)必有f(X° te) -f(X0) 0t,即f(X)<f(X°),其中X =X0 +te是從X0出發(fā)在P方向上

6、的點(diǎn)，說明f(X)是下降的.同理可以說明，若1(0)0P ,則f(X)是上升的.二、梯度定義2.4以f(X)的n個(gè)偏導(dǎo)數(shù)為分量的向量稱為f(X)在X處的梯度，記為"(X)新(X)引X)cf(X)l:X2二 xn梯度也可以稱為函數(shù) f(X)關(guān)于向量X的一階導(dǎo)數(shù).以下幾個(gè)特殊類型函數(shù)的梯度公式是常用的：(1)若 f(X) =c (常數(shù))(2) V(bTX)=b.證設(shè) b =b，b2,，bn,則 Vf (X)=O ,即 Vc = O；X = xi, x21，xn ，則是V(bTX)的第j個(gè)分量是二 T(b X)Xj所以 V(bTX) =b .(3)RXTX)=2X .(4)若A是對稱矩陣，

7、則Q n(Z bxi) =bj, j =1, 2,，n.-：Xj i 1V(XTAX) =2AX三、梯度與方向?qū)?shù)之間的關(guān)系定理2.1設(shè)f： Rn T R1在點(diǎn)X0處可微，則弩(X0)TecP,其中e是P方向上的單位向量.證明在相應(yīng)的數(shù)學(xué)分析中可找到(故略去)由這個(gè)定理容易得到下列結(jié)論：處的下降方向;處的上升方向.(1)若*(X0)Tp<0,則p的方向是函數(shù)f(X)在點(diǎn)X(2)若Vf(X0)Tp0,則P的方向是函數(shù)f(X)在點(diǎn)X方向?qū)?shù)的正負(fù)決定了函數(shù)值的升降，而升降的快慢就由它的絕對值大小決定.絕對 值越大，升降的速度就越快，即=Vf (X0)TeVf(X0)| 118s(Vf(X&#

8、176;), e)0Vf(X0)|上式中的等號(hào)當(dāng)且僅當(dāng) e的方向與"f (X0)的方向相同時(shí)才成立.由此可得如下重要結(jié)論(如圖2.1所示)：(1)梯度方向是函數(shù)值的最速上升方向；(2)函數(shù)在與其梯度正交的方向上變化率為零；(3)函數(shù)在與其梯度成銳角的方向上是上升的，而在與其梯度成鈍角的方向上是下降的；(4)梯度反方向是函數(shù)值的最速下降方向.對于一個(gè)最優(yōu)化問題，為了盡快得到最優(yōu)解，在每一步迭代過程中所選取的搜索方向P總是希望它等于或者是靠近于目標(biāo)函數(shù)的負(fù)梯度(即一17f (X)的方向，這樣才能使函數(shù)值下降的最快.22/例2.21式求目標(biāo)函數(shù)f(X)=X1+X2+1在點(diǎn)X。,3處的最速一

9、F降方向，并求沿這個(gè)方上再方"徹向移動(dòng)一個(gè)單位長后新點(diǎn)的目標(biāo)函數(shù)值. 解因?yàn)?.:x月-3一12XXX1X22 2-這個(gè)方向上的單位向量是f (XQ- L)0If故新點(diǎn)是對應(yīng)目標(biāo)函數(shù)值為Xi - Xo e -_ 2- 2f(Xi)=021=5陽-01Hlf (X)關(guān)于X的二階導(dǎo)數(shù)是什么？定義2.5設(shè)階偏導(dǎo)數(shù)§2.3海色矩陣及泰勒展式一、海色(Hesse)矩陣前面說過，梯度17f (X)是f (X)關(guān)于x的一階導(dǎo)數(shù)，現(xiàn)在要問f ： RnT R1, X。三Rn,如果f在點(diǎn)X。處對于自變量 X的各分量的二都存在，則稱函數(shù)：2f(X°)：:Xi(i, j =1,2,|M,

10、n)f在點(diǎn)X。處二階可導(dǎo)，并且稱矩陣Fc2f(Xo)V2f(Xo)=-2,X1.2 .二 f ( X o)：X2 ： X1-2 一二 f(X。).：X1：X2.2 .二 f ( X。)-2-X232f(Xo)1CX1CXn一 2 .G f ( X。)：X2：Xn_2 _二 f(X。)明出, 2 _二 f(X。)XnM, 2 _二 f(X。)-2Xn是f在點(diǎn)X。處的Hesse矩陣.在數(shù)學(xué)分析中已經(jīng)知道，當(dāng)產(chǎn)ff在點(diǎn)X。處的所有二階偏導(dǎo)數(shù)為連續(xù)時(shí)有;：2f比；：Xj ；：Xj fXi因此，在這種情況下 Hesse矩陣是對稱的.，i, j =1, 2,，n.43222Hesse矩陣.例 2.3 求目

11、標(biāo)函數(shù) f(X)=X1 +2x2 +3x3 - x1 x2 +4x2x3 x1x3 的梯度和解因?yàn)閒 3二4Xi .Xi,：f2=6X22-2x1x2 x3,_=X2 f ：X3=6x3x； +4x3,-4x2 - 2x1x3,4x13 2xiX2-x2所以又因?yàn)閒 (X) = 6x； -x12 +4x3 6x3 +4x2 -2X1X3所以- 2 f f T2X1?f-2X22=12x -2x2)=12 X2 ,12f(X)二- 2 rf f11%;2f>2X3：游3；：2f12x12 -2x22Xi 2x3-2x112x24-2-X3-2x346-2xi= 62xi ,n 、,_ n

12、, 二例2.4設(shè)a = R ,X u R力匚R,求線性函數(shù)f (X) =aTX b在任意點(diǎn)X處的梯度和解設(shè)a=a1，a2；Hesse矩陣.,anT, X =x1, X2,，XnT 則n“為2,，Xn)=£ aixi +b開.xi= ai, i =1, 2,，n ,(2.2)'、f (X) = ai,a2T - ,an - a由式（2.2）進(jìn)而知；：2f c二0,xi ； Xji, j =1, 2,，n,數(shù) f(X)=.V2f（X） =O（ nMn 階零矩陣）.例2.5設(shè)AW Rn"是對稱矩陣，bRn, LR1,求1 TT-X AX b X c2 在任意點(diǎn)處的梯度和

13、Hesse矩陣.解 設(shè) A = (aij)nM, b=bl,b2,，bnT, X=X1,X2,，XnT,則1n nnf(x1, xn)=££ ajxixj+Z bixi + c.2 y j4id將它對各變量xi (i =1，2,，n)求偏導(dǎo)數(shù)，得 (X)Cxif(X)=：/ (X)"一Vf (X) = AX +bn工 aijXj +bjanZ anjXj +bnjn£ aijXjjn£ anjXjjbia:bn 一在上式中顯然-：Xin=Z aijXj +bi, ji =1,2,，n,再對它們求偏導(dǎo)數(shù)得?f=ai, j =1, 2,，n,aii

14、ai2a"2a2ia22a2 nv2f (X);=A Ji A A A A Aanian 2ann .ij，- Xi ： Xj以上例子說明，n元函數(shù)求導(dǎo)與一元函數(shù)的求導(dǎo)在形式上是一致的,即線性函數(shù)的一階導(dǎo)數(shù)為常向量，其二階導(dǎo)數(shù)為零矩陣； 而二次函數(shù)的一階導(dǎo)數(shù)為線性向量函數(shù)，二階導(dǎo)數(shù)為常矩陣.最后介紹在今后的計(jì)算中要用到的向量函數(shù)的導(dǎo)數(shù).定義2.6設(shè) H: R= Rm, X°WRn ,記 H(X)刁，(X), MX),，hm(X)T ,如果hi(X) (i =1, 2,，m)在點(diǎn)X0處對于自變量X =Xi, X2,，Xn的各分量的偏導(dǎo)數(shù)：hi(Xo)Xj 矩陣(j =i,2,

15、，n)都存在，則稱向量函數(shù) H(X)在點(diǎn)Xo處是一階可導(dǎo)的，并且稱"hi(Xo)-h(Xo)m,n H (X0 ) =：Xi:hUXo)III力m(Xo)：:XiX2FhUXo)：X2IH:hm(Xo)；：X2IIIIIIIIIIII力i(Xo) 1二 Xn力2(Xo)區(qū)HIWlm(Xo):X是H (X)在點(diǎn)X。處的一階導(dǎo)數(shù)或 Jacobi矩陣，簡記為'H(Xo)八 mnH(Xo)ni .由于n兀函數(shù)f： R t R的梯度是向量函數(shù)物)=產(chǎn),3CX,cx2CXn -所以17f (X)的一階導(dǎo)數(shù)或Jacobi矩陣為JL幽0迤力的I法/酪&終jiHl III III I-

16、h身修-22XXi川.(臾)_ 一赤戈1、'nn"(X)”:產(chǎn) f(X)-：Xi %-f (X)-III f(X):Xn ：羌f(X)川HIHIIII£什(宮)智ff(XQ)旅2§Xn三對 f fXX),IIIfX)：v22漢2 1烝&%Xn J/據(jù)此，從上式得知，函數(shù)梯度的Jacobi矩陣即為此函數(shù)的 Hesse矩陣.下面給出今后要用到的幾個(gè)公式：(1) $C = O ,其中c是分量全為常數(shù)的n維向量，。是nMn階零矩陣.(2) X=I,其中X是n維向量，I是nMn階單位矩陣.(3) WAX) = A，其中A是mMn階矩陣.(4)設(shè)中= f(X&

17、#176;+tp),其中 f: RnT R1,中：R1t R1,則TT 2中(t) =Vf(X°+tP) P,邛(t) = PV f(X0+tP)P二、泰勒展開式多元函數(shù)的泰勒展開在最優(yōu)化方法中十分重要，許多方法及其收斂性的證明是從它出發(fā)的，這里給出泰勒展開定理及其證明.n 1定理2.2設(shè)f： R t R具有二階連續(xù)偏導(dǎo)數(shù)，則f (X P) -f(X) f(X)TP -PT 2f(X)P2,(2.3)其中X =X +中，而0<1 .證設(shè)平代)=£力+正)，于是9(0) = f(X), *(1)=f(X+P).對中(t)按一元函數(shù)在t=0點(diǎn)展開，得到1 ：(t)/0)：

18、'(0)t ："(才)t22,其中0 mH <1 .令t =1 ,于是1 (1) = (0)'(0)一"2.(2.4)_ T.T 2 一又因?yàn)榻?)=f(X) P,=P V f(X +8P)P，代入式(2.4)中，所以_- T_1_T_ 2 -. _ _f (X P) = f (X) T f (X)T P PTV 2 f (X 1P)P 2.式(2.3)還可以寫成f (X P) = f(X) t f(X)TP -PTV 2f (X)P o(| P|2) 2.§2.4極小點(diǎn)的判定條件函數(shù)f (X)在局部極小點(diǎn)應(yīng)滿足什么條件？反之，滿足什么條件的

19、是局部極小點(diǎn)？這是我們關(guān)心的基本問題.下面針對多元函數(shù)的情形給出各類極小點(diǎn)的定義.定義2.7對于任意給定的實(shí)數(shù)0 >0,滿足不等式|X -Xo |<6 的X的集合稱為點(diǎn) X0的鄰域，記為N(X0, 6)=X| |X -Xo 卜 6,6 >0n1*定義2.8設(shè)f ： D - R R ,若存在點(diǎn)X WD和數(shù)每A0,VXWN(X，a) I D *、都有f (X ) « f (X ),則稱X為f (X)的局部極小點(diǎn)(非嚴(yán)格).n1*定義2.9設(shè)f： D± R t R，若存在點(diǎn)X w D和數(shù)每A0, VX w N(X，勾 D *、但X #X，都有f (X ) <

20、; f (X ),則稱X為f (X)的嚴(yán)格局部極小點(diǎn).n 1*定義 2.10 設(shè) f： D£R T R ,若存在點(diǎn) X WD, VXWD 都有 f(X )E f(X), 則稱X*為f (X)在D上的全局極小點(diǎn)(非嚴(yán)格).定義2.11設(shè)f： D = Rn T R1 ,若存在點(diǎn) X* w D , VX W D但X = X* ,都有 *、f(X )<f(X),則稱X為f(X)在D上的嚴(yán)格全局極小點(diǎn).由以上定義看到，X*是局部極小點(diǎn)，是指在以X*為中心的一個(gè)鄰域中f(X)在點(diǎn)X*處 取得最小的值；而X*是全局極小點(diǎn)，是指在定義域 D中f(X)在點(diǎn)X*處取得最小的值.全 局極小點(diǎn)可能在某

21、個(gè)局部極小點(diǎn)處取得，也可能在D的邊界上取得.實(shí)際問題通常是求全局極小點(diǎn)，但是直到目前為止， 最優(yōu)化中絕大多數(shù)方法都是求局部極小點(diǎn)的，解決這一矛盾的一種方法是先求出所有的局部極小點(diǎn)，再求全局極小點(diǎn).定理2.3設(shè)f： D三RnT R1具有連續(xù)的一階偏導(dǎo)數(shù).若 X*是f(X)的局部極小點(diǎn) 并且是D的內(nèi)點(diǎn)，則f(X )=O.(2.5)證 設(shè)e是任意單位向量，因?yàn)閄*是f(X)的局部極小點(diǎn)，所以存在6>0,當(dāng)1t|<6 或X +teu N(X , 6)時(shí)總有 _ * . . _ *f(X +te) 2 f (X ).(2.6)*引入輔助一元函數(shù)中=f (X +，此時(shí)，由式(2.6)得中之中.

22、又因X是D的 內(nèi)點(diǎn)，所以與它對應(yīng)的t =0是中的局部極小點(diǎn).又根據(jù)一元函數(shù)極小點(diǎn)的必要條件，得* T*到中=0 ,即Wf (X ) e = 0 .再由單位向量e的任意性得Vf (X ) = O .*T這里條件(2.5)僅僅是必要的，而不是充分的.例如f (x1, x2)=x1x2在點(diǎn)X -0, 0 T*T處的梯度是Vf =0，0,但X =0, 0是雙曲面的鞍點(diǎn)，而不是極小點(diǎn)(如圖2.2所示).n1*定義2.12設(shè)D U R t R，X是d的內(nèi)*、點(diǎn).若Vf (X ) =O ,則稱X*為f (X)的駐點(diǎn).n1定理2.4設(shè)f： D三R t R具有連續(xù)二階偏導(dǎo)*、數(shù)，X*是D的一個(gè)內(nèi)點(diǎn).若Vf(X)

23、=°,并且-2*、7 f(X )是正定的，則X *是f (X )的嚴(yán)格局部極小點(diǎn).2*證 因?yàn)?f (X )是正定矩陣，則必存在 九> 0 ,使得對于所有的P w Rn都有PTk 2f(X*)P 一 |P|2圖2.2(參看高等代數(shù)二次型理論).現(xiàn)在將f(X)在點(diǎn)X*處按泰勒公式展開，并注意到Vf(X ) =O,于是可得_*1*TO_*f(X)-f(X)=2(X-X 12f(X )(X-X) o(l1X-X 12)-|X -X*|2 o(|X -X* |2).當(dāng)X充分接近 X* (但X ¥X* )時(shí)，上式左端的符號(hào)取決于右端第一項(xiàng)，因此 _ _ *一般說來，這個(gè)定理僅具

24、有理論意義.它的正定性就更難判定了.定理2.5若多元函數(shù)在其極小點(diǎn)處的 等值面近似地呈現(xiàn)為同心橢球面簇.證 設(shè)X *是多元函數(shù)的極小點(diǎn)，并設(shè) *因?yàn)閷τ趶?fù)雜的目標(biāo)函數(shù)，Hesse矩陣不易求得,Hesse矩陣是正定的，則它在這個(gè)極小點(diǎn)附近的f (X)='是充分靠近極小點(diǎn) X*的一個(gè)等值面,即|X-X H充分小.把f(X)在X*點(diǎn)展成泰勒公式，即 * t*f (X) = f (X ) Y f (X ) (X - X )f(X)>f(X ).1* T . 0 -*9+ (X -X )TV2f (X )(X - X ) +o(|X -X |2).2*、右端第二項(xiàng)因X*是極小點(diǎn)有7f (X

25、 )=O而消失.如果略去第 4項(xiàng)，那么1f(X) ： f (X ) -(X -X 嚴(yán) 2 f (X )(X -X )2,又因?yàn)閒 (X) = 丫，所以f (X*) +1(X X*)TV2f (X*)(X X*)之¥,2(2.7)(X -X*)TV2f(X*)(X X*)之2(>f(X*) =c (c為常數(shù)).2*按假設(shè)V f(X )正定，由二次型理論知式(2.7)是以X*為中心的橢球面方程.§2.5錐、凸集、凸錐在本節(jié)中，給出n維Euclid空間Rn中的錐、凸集和凸錐的定義，以及與其相關(guān)的一些 概念和性質(zhì).一、定義與簡單性質(zhì)定義2.13集合C uRn .若VX三C及任

26、意的數(shù)0>0,均有九X乏C ,則稱C為錐.定義2.14 設(shè)X1，X2,，Xl是Rn中的i個(gè)已知點(diǎn).若對于某點(diǎn) xwRn存在常數(shù) ll' 'i =1 x = " 'iXi九 1,他,九之0且i 使得 i ，則稱X是X1, X2, ,Xl的凸組合,若 lc "'i = 14, ，2,薪>0且i,則稱X是X1, X2， ，Xl的嚴(yán)格凸組合.定義2.15集合CuRn .若卡X1 WC和/X2W C，以及任意的數(shù)人W 0 ,們，均有 X1 （1-）X2 C,則稱C為凸集.定義2.16設(shè)aWRn且a#0, bw R1 ,則集合X | aTX

27、>b, X e Rn稱為Rn中的 半空間.特別地，規(guī)定空集是凸集.容易驗(yàn)證，空間 Rn、半空間、超平面、直線、點(diǎn)、球都是 凸集.定理2.6任意一組凸集的交仍然是凸集.C = C證設(shè) i i,其中1是弓的下標(biāo)集，Ci都是凸集.任取X1，X2=C,則對于任意"I都是X1, X21i .任取W且兀+乂=1 ,因Ci是凸集，有 ，乂 . , V p 1X1 ' '2X2 ,: Ci CA1X1+A2X2 -Ci.于是歸，即C是凸集.若集合C為錐，C又為凸集，則稱 C為凸錐.若C為凸集，也為閉集，則稱 C為閉凸 集.若C為凸錐，也為閉集，則稱 C為閉凸錐.由數(shù)學(xué)歸納法不難

28、證明如下的定理2.7和2.8.定理2.7 集合C為凸集的充分必要條件是"產(chǎn)C ,及任意數(shù)、之0 kki - 1 二.上i Xi C（1=1,2，k，k “）,以 ，有 y,定理2.8集合C為凸錐的充分必要條件是藜Xi三C ,及任意數(shù)Zi -0（i =1, 2,，k, k >2）,均有 k v iXi C定義2.17有限個(gè)半空間的交X 1Ax ±b稱為多面集，其中 A為mMn矩陣，b為 m維向量.例2.6集合S =X x1+2x2 M4,x1 - x2 M1, x1, x2 叫為多面集，其幾何表示如圖2.3畫斜線部分.在多面集的表達(dá)式中，若b = 0,則多面集 X 1A

29、x <0也是凸錐，稱為多面錐.在有關(guān)凸集的理論及應(yīng)用中，極點(diǎn)和極方向的概念 有著重要作用.定義2.18設(shè)C為非空凸集，X w C ,若x不 能表示成C中兩個(gè)不同點(diǎn)的凸組合；換言之，若假設(shè) X=ZXi 十(1九)X2,九w(0,1), Xi, X2WC,必推得 X =X1 =X2,則稱X是凸集C的極點(diǎn).按此定義，圖2.4 (a)中多邊形的頂點(diǎn)X1，X2，X3, 是極點(diǎn).圖2.4(b)中圓周上的點(diǎn)均為極點(diǎn).由圖2.4可以看出，在給定的兩個(gè)凸集中，任何一點(diǎn) 都能表示成極點(diǎn)的凸組合.定義2.19設(shè)C為Rn中的閉凸集，P為非零向量， 如果對C 中的每一個(gè)X , 都有射線 X +7P?l>0C

30、 ,則稱向量p為C的方向.又設(shè)P 和H是C的兩個(gè)方向，若對任何正數(shù)九，有R # KP2 ,則稱p和p2是兩個(gè)不同的方向.若C的方向P不能表示圖2.3X4和X5是極點(diǎn)，而 X6和X7不成該集合的兩個(gè)不同方向的正的線性組合，則稱P為C的極方向.例2.7如圖2.5所示，對于集合C = X1 涇X2 至 xj凡是與向量0,1T夾角小于或等于 45二的向量，都是它的方向.1,1T和-1,1T是C的兩個(gè)極方向.C的其它方向都能表示成這兩個(gè)極方向的正線性組合.例2.8設(shè)C =X AX也X *為非空集合，p是非零向量.證明P為C的方向的充要條件是 P20且AP =0證 按照定義2.19, P為C的方向的充要條

31、件是對每一個(gè)X 十九P九至0仁C根據(jù)集合C的定義，由式(2.8)可得A(X + KP) = b ,圖2.5X w C ,有(2.(8)(2.(9)X +KP 2 0 .(2.10)由于AX = b, X之0及九可取任意非負(fù)數(shù)，因此由式(2.9)和式(2.10)知AP = 0對于有界多面集，它的每一個(gè)點(diǎn)可用極點(diǎn)的凸組合來表示，反之，由極點(diǎn)的凸組合表 示的點(diǎn)一定屬于這個(gè)多面集.對此可簡要說明如下：設(shè)有多面集C=X AX W,如圖2.6(a)所示.若X乏C ,則X = X1 (1-)Y=X1 (1 -')X4 (1 -)X3=X1 (1 -'尸X4 ( )(1 -)X3,其中兒,(1

32、Q2,(1 -Q(12)均為非負(fù)數(shù),且兒+(1_.)2+(1K)(1 2)=1,即X為極點(diǎn)X1 , X3和X4的凸組合.反之，設(shè)55X 八 iXi V i =10, y，兒i 蘭0,5AX 八iAXi <b則 一，即X wC.,只用極點(diǎn)來表示是如果多面集是無界的，那么對于該多面集中的任一點(diǎn)(極點(diǎn)除外)不行的，還需要用極方向.如圖2.6(b)所示，這時(shí)有X = X1 (1 - )X3 - JP1其中九是(。中某個(gè)數(shù)，N是某一個(gè)非負(fù)數(shù).圖2.6概括起來，有下列定理：定理 2.9 設(shè) C =X AX =b，X -0為非空多面集，則有C有界.若C無界，則存在有限個(gè)極方向(1)極點(diǎn)集非空，且存在有

33、限個(gè)極點(diǎn)X1, X2,，Xk-(2)極方向集合為空集的充要條件是P，F(xiàn)2,，P.(3) X w C的充要條件是klX =、，jX j 一二, j Pjj 1j 1其中k.二.兀 j= 1j 1% >0(j =1,21，k)方 >0(j =12，l)關(guān)于上述定理的證明參見參考文獻(xiàn)6.二、凸集分離定理凸集分離定理是凸分析中最重要的定理之一，它在最優(yōu)化理論和模型當(dāng)中具有重要的應(yīng)用.所謂集合的分離是指對于兩個(gè)集合 Ci和C2存在一個(gè)超平面 H,使得Ci在H的一邊， 而C2在H的另一邊.如果超平面方程為 PTX 5 ,那么對位于 H某一邊的點(diǎn)必有 PTX之口，而對位于H另一邊的必有 PTX

34、<« .定義2.20設(shè)Ci和C2是Rn中的兩個(gè)非空集合，H=X|P X=叼是超平面，若 對于每一個(gè)X三Ci都有PTX之口，對于每一個(gè)X三C2都有PTX(或情況恰好相反)， 則稱超平面H分離集合Ci和C2.定理2.10若C為閉凸集，X0 5 C，則存在a w Rn , a#0 ,以及數(shù)a運(yùn)R1 ,對yX e C , 有a X >a > a X0,并且存在Xi三C，使得a Xi =a定理2.11設(shè)C為凸集，Xo乏C ,則存在aw Rna#。，使得vx WC ,有aTX 之 aTX0定理2.12設(shè)C為閉凸集，則C可表為所有包含 C的半空間的交，即C = 1 X |aTX

35、_ ： 其中L = «Rn卡XaTX 至0( nC, a*0上述定理的證明過程參見參考文獻(xiàn)6.文6 凸函數(shù)一、各類凸函數(shù)定義及性質(zhì)設(shè)函數(shù)f(X)定義在凸集C上，其中X =X1,X2，Xn .定義2.21若存在常數(shù)a >0，使得VX1, X2-C,以及 找w(0,1),若有 f ( X1(1 - )X2) _ f (X1) (1 - )f (X2) -(1 - ) | X1 - X2 |2則稱f(X)為一致凸函數(shù)；若有f (1X1 +(1 -X)X2)<Xf (X1) + (1-1)f(X2),則稱f(X)為嚴(yán)格凸函數(shù)；若有f(KX1 +(1-九)X2)W f(X1) +

36、(1-九)f(X2)則稱f(X)為凸函數(shù).定義2.22設(shè)f(X)為可微函數(shù).若VX1, X2WC,當(dāng)'、 f(X2)T(X1 -X2) - 0都有f(X”f(X2)則稱f(X)為偽凸函數(shù).定義 2.23 對VX1, X2",且 f(X1)#f(X2),以及 a0,1),若f (人X1 +(1-K)X2)(maX f(X) f(X2),則稱f(X)為嚴(yán)格擬凸函數(shù)；定義2.24對VXn X2C,以及410,1),若f (九X1 +(1-K)X2) WmaX f(X) f(X2),則稱f(X)為擬凸函數(shù)；定義 2.25 對 VX1, X2C,且 X-X2,以及 V/(0,1),若f

37、( X1 (1- )X2) ； max f(X) f(X2),則稱f(X)為強(qiáng)擬凸函數(shù).定理2.13若f(X)為一致凸函數(shù)，則 f(X)為嚴(yán)格凸函數(shù).證：設(shè)f (X)為一致凸函數(shù)，則 ”,X2 e C , X1 # X2 ,及 W 9G ,有 2f( X1 (1 - -)X2) < f(X1) (1 - - ) f(X2) -： (1 - ) | X1 - X2 |<kf(Xl)+(1-k)f(X2), 即”*)為嚴(yán)格凸函數(shù).定理2.14若f(X)為嚴(yán)格凸函數(shù)，則 f(X)為凸函數(shù).定理2.15設(shè)f(X)為可微函數(shù).若f(X)為凸函數(shù)，則f(X)為偽凸函數(shù).定理2.16設(shè)f(X)為

38、偽凸函數(shù)，則f(X)為嚴(yán)格擬凸函數(shù).定理2.17設(shè)f(X)為下半連續(xù)的嚴(yán)格擬凸函數(shù)，則f(X)為擬凸函數(shù).定理2.18若f(X)為嚴(yán)格凸函數(shù)，則 f(X)為強(qiáng)擬凸函數(shù).定理2.19設(shè)f(X)為強(qiáng)擬凸函數(shù)，則 f(X)為嚴(yán)格擬凸函數(shù).下半連續(xù)的定義及定理 2.14一定理2.19的證明過程參見參考文獻(xiàn)6.上述幾種凸函數(shù) 有圖2.7所示的關(guān)系.一致凸嚴(yán)格凸一*凸偽凸嚴(yán)格想西加I凸.強(qiáng)搜凸-<* >表示當(dāng)H乃 為可徽;(*)表示當(dāng)/ 為下半連綾鋌數(shù)圖2.7凸函數(shù)與凸集之間有如下關(guān)系： n1定理2.20設(shè)f： CG R T R ,其中C為非空凸集.若f是凸函數(shù)，則對于任意實(shí)數(shù)P,水平集Dp=

39、X|f(X)EP, XW6是凸集.證若DP是空集，則DP是凸集.以下設(shè)DP非空，任取Xi，X2 * DP ,則 f(XJ MP, f(X2)EP .設(shè)%, %10,1)且%+%=1,由 f 是凸函數(shù)知f1X +ot2X2)Wa1f(X1)+o(2f(X2)Mo(1P +a2P = P ,即。二1 +c(2X2三Dp所以DP是凸集.判定一個(gè)函數(shù)是否為凸函數(shù)，一般說來是比較困難，但當(dāng)函數(shù)可微時(shí)， 有如下幾個(gè)定理可供使用. n1定理2.21設(shè)f： CG R T R是可微函數(shù)，其中 C為凸集.則(1) f為凸函數(shù)的充要條件是 VXi, X2 w C ,都有f(X2).f(X1)+Vf(X1)T(X2

40、X1)；(2.11)(2) f為嚴(yán)格凸函數(shù)的充要條件是 VXi, X2 W C ,且Xi ¥ X2 ,都有f(X2)- f(X1)+Vf(X1)T(X2 Xi)證 (1)先證必要性 .已知f是C上的凸函數(shù)，要證式(2.11).由凸函數(shù)定義知， 對滿足% +% =1的任意數(shù)%, % w (0,1)都有f(%X1+%X2) W%f(X1)+%f(X2),令4,則% =1 t .代入上式中，經(jīng)移項(xiàng)可得f(X1 t(X2-X1)-f(X1).： - f (X2) - T (X1)t.(2.12)令tT 0,由f的可微性，利用一階泰勒展式、方向?qū)?shù)定義及式(2.12),可得Vf(Xi)T(X2

41、 Xi) 4f(X2) f(Xi).這就證明了式(2.11).再證充分性.任取一對數(shù) %，口2 W (0，1)且% +。2 =1.考慮點(diǎn)X =QiXi +5X2, 根據(jù)充分性假設(shè)，應(yīng)有f(Xi)>f(X)+Vf (X)T(Xi-X)f (X2) - f (X) f (X)T(X2 -X)兩式分別乘以1ai和口2后相加，得到>f (Xi)+.= 2f (X2) _ f (X) If (X)T(二 iXi H/S2X2 -X)=f (： iXi )2X2)由凸函數(shù)定義知，f是C上的凸函數(shù).(2)充分性可依照(D的充分性證得，下證必要性.因?yàn)閲?yán)格凸函數(shù)本身是凸函數(shù)，所以VXi, X2 W

42、 C ,且Xi =X2 ,都有f(X2)- f(Xi) Vf(Xi)T(X2-Xi)(2.(12)(2.(13)以下證明式中只能取“ >”號(hào).假設(shè)存在Xi, X2 W C ,且Xi #X2 ,使得 f(X2) = f(Xi)+Vf(Xi)T(X2-Xi).取X3 =(Xi *X2)/2 ,由f的嚴(yán)格凸性，有 i i f(X3) <-f(Xi) - f(X2)22.把式(2.i2)代入式(2.i3)中，經(jīng)整理得f(X3):二 f (Xi)l f(Xi)T(X3 -Xi)根據(jù)本定理(i)部分結(jié)論得知，此式與f是凸函數(shù)相矛盾.ni定理2.22設(shè)f： C三R t R是二次可微函數(shù)，C為非空

43、開凸集，則 f為C上凸函2數(shù)的充要條件是 Hesse矩陣7 f (X)在C上任意點(diǎn)均半正定.證明略.n i定理2.23設(shè)f： C三R t R是二次可微函數(shù)，C為非空凸集.若 Hesse矩陣在C 上任意點(diǎn)均正定，則 f在C上為嚴(yán)格凸函數(shù).證明略，需要注意，該定理的逆命題不真.422例如f(x)=x在R上為嚴(yán)格凸函數(shù)，但是它的Hesse矩陣"f(x)=i2x在點(diǎn)x = 0處是半正定的.二、凸規(guī)劃定義2.26設(shè)f ： C三Rn t N ,其中c是非空凸集，f是凸函數(shù)，則形式為 miCf(X) 的問題稱為凸規(guī)劃問題.更進(jìn)一步，設(shè)C =X |gi(X)之0, i =i,2,，l; hj(X)

44、= 0, j =i,2,，m; XW Rn,若_g，_g2,，_gl都是Rn上的凸函數(shù)，幾，h2,，hm都是Rn上的線性函數(shù)，則容易驗(yàn)證 C是凸集.事實(shí)上，因?yàn)橐?，一g2,，一gi都是凸函數(shù)，根據(jù)定理2.20集合 Ci =X | -gi(X) w0, X三Rn,i f2,，1也都是凸集.此外，超平面 Pj =X | hj (X) =o, X 匚 R , j =1, 2, ，m ,也都是凸集.顯然，C 是 Ci，5,，G, P1, P2,，pm的交集，根據(jù)定理 2.6, C是凸集.于是，在這種情況下凸規(guī)劃問題又可表示成如下形式:min f(X),Igi(X)之0, i =1,2,H|,l, s

45、. t.Q(X)=0, j =1, 2 H|,m.如下定理指明凸規(guī)劃的一個(gè)重要性質(zhì).定理2.24設(shè)X是凸規(guī)劃問題的局部極小點(diǎn)，(1)若f是凸函數(shù)，則X*是凸規(guī)劃問題全局極小點(diǎn)；(2)若f是嚴(yán)格凸函數(shù)，則 X*是凸規(guī)劃問題的唯一全局極小點(diǎn).*.證(1)使用反證法.假設(shè)X不是全局極小點(diǎn)，則必存在Z W C使得f (Z) < f (X ).對 *于Z與X*的任意凸組合X=%Z+a2X，其中%, 0(2 U (0,。且%十口2 =1,根據(jù)f的凸性，有* *f(X) = f (： 1Z ： 2X ) < 二 1f (Z) ： 2f (X )* * *:二：1f (X )七2 f (X ) =

46、 f (X )* .由此看到，當(dāng)叫 A0充分小時(shí)，X充分接近X ,注意到此時(shí)也有f(X)< f(X ),而這*.與X是局部極小點(diǎn)相矛盾.因此 X必是全局極小點(diǎn)._*.(2)假設(shè)X不是唯一全局極小點(diǎn).必存在X w c但XX*使得f (X ) = f (X ).考11*-由 f 的嚴(yán)格凸性， 有X X X c慮中點(diǎn) 22.11 *f(X) = f(2X2X )1.1.*.*.此式與X為全局極小點(diǎn)相矛/(X) 5f(X) = f(X)盾.這就證明了唯一性.定義2.27形式為1 TTf (X) = X AX b X c(2.14)2的函數(shù)稱為n元二次函數(shù),這里的A是對稱矩陣，即 若A為正定，則稱

47、(其中&1弘a"bla=a21a22a2 n,b =b2aaman2ann_1 1bn 一,aj = a ji2.14)為正定二次函數(shù).注意到 V2f(X) = A,由定理2.23知,正定二次函數(shù)是嚴(yán)格凸函數(shù)，在最優(yōu)化算法構(gòu)造中它起著特殊的作用.定義2.28形式為1 min f (X) XtAX bTX c, 2(2.15),QX 至 P,s.t./HX =d的問題稱為二次規(guī)劃問題，其中Q是m父n矩陣，H是l Mn矩陣.若A為半正定或正定，則稱(2.15)為二次凸規(guī)劃問題.本書不作專門討論. 解.§2.7約束問題的最優(yōu)性條件所謂最優(yōu)性條件就是最優(yōu)化問題的目標(biāo)函數(shù)與約

48、束函數(shù)在最優(yōu)點(diǎn)處滿足的充要條件.這種條件對于最優(yōu)化算法的終止判定和最優(yōu)化理論推證都是至關(guān)重要的.最優(yōu)性必要條件是指在最優(yōu)點(diǎn)處滿足哪些條件； 充分條件是指滿足哪些條件的點(diǎn)是最優(yōu)點(diǎn). 本節(jié)僅講述最 基本的結(jié)論.一、約束最優(yōu)解對約束優(yōu)化問題的求解，其目的是在由約束條件所規(guī)定的可行域D內(nèi)，尋求一個(gè)目標(biāo)*函數(shù)值最小的點(diǎn) X*及其函數(shù)值f(X ).這樣的解(X , f(X D稱為約束最優(yōu)解.約束最優(yōu)點(diǎn)除了可能落在可行域 D內(nèi)的情況外，更常常是在約束邊界上或等式約束曲面上，因此它的定義及它的一階必要條件與無約束優(yōu)化問題不同.(一)約束優(yōu)化問題的類型約束優(yōu)化問題根據(jù)約束條件類型的不同分為三種，其數(shù)學(xué)模型如下：

49、(1)不等式約束優(yōu)化問題(IP型)min f (X),(2.16)s.t. gi(X)>0),i=1,2J|J.(2)等式約束優(yōu)化問題(EP型)min f(X),s.t. hj(X) = 0, j =1,2,11,m.(3) 一般約束優(yōu)化問題(GP型)min f(X),lgi(X)>0,i =1,2,川,l,s.t.hj(X) = 0,j=1,2JH,m.(二)約束優(yōu)化問題的局部解與全局解按一般約束優(yōu)化問題，其可行域?yàn)镈 =X |gi(X)>0, i=1,2,，l; hj(X) = 0, j=1,2,，m* .若對某可行點(diǎn) X存在6 A 0,當(dāng)X與它鄰域的點(diǎn) X之距離|X -

50、X |K名時(shí)，總有*.f(X ) < f(X)則稱X為該約束優(yōu)化問題的一個(gè)局部最優(yōu)解.下面以一個(gè)簡單例子說明.設(shè)有min f(X) = (x1 7)2 x2,s. t.&X)=X2+2 之0, 白(X) =(x1 -2)2 -x2 -9 = 0.該問題的幾何圖形如圖 2.8所示.從圖上的目標(biāo)函數(shù)等值線和不等式約束與等式約束的函數(shù)曲*T *T*線可寫出它的兩個(gè)局部最優(yōu)解X1 =-1,0，X2 =5, 0 .這是因?yàn)樵赬1點(diǎn)鄰域的任一滿*足約束的點(diǎn)X ,都有f (X) > f (X1 )；同理，X2亦然.圖2.8對某些約束優(yōu)化問題，局部解可能有多個(gè).在所有的局部最優(yōu)解中，目標(biāo)函

51、數(shù)值最小 的那個(gè)解稱為全局最優(yōu)解. *在上例中，由于f (X1 ) =4 f (X2) =16,所以全局最優(yōu)解為(X1, f (X1) .由此可知，約束優(yōu)化問題全局解一定是局部解，而局部解不一定是全局解.這與無約束優(yōu)化問題是相同的.二、約束優(yōu)化問題局部解的一階必要條件對于約束，現(xiàn)在進(jìn)一步闡明起作用約束與不起作用約束的概念.一般的約束優(yōu)化問題，其約束包含不等式約束 gi(X)*0, i=1,2L/ 和等式約束 hj(X) =0, j =1,2,，m ,在可行點(diǎn)Xk處，如果有g(shù)i(Xk) =0 ,則該約束gi(X)稱可行 點(diǎn)Xk的起作用約束；而如果有 gi(Xk)A°,則該約束gi(X)

52、稱可行點(diǎn)Xk的不起作用約 束.對于等式約束hj(X) =° ,顯然在任意可行點(diǎn)處的等式約束都是起作用約束.在某個(gè)可行點(diǎn) Xk處，起作用約束在 Xk的鄰域內(nèi)起到限制可行域范圍的作用，而不起 作用約束在Xk處的鄰域內(nèi)就不產(chǎn)生影響.因此，應(yīng)把注意力集中在起作用約束上.(一)IP型約束問題的一階必要條件圖2.9所示為具有三個(gè)不等式約束的二維最優(yōu)化問題.圖2.9圖2.9 (a)是最優(yōu)點(diǎn)X在可行域內(nèi)部的一種情況.在此種情形下，X點(diǎn)的全部約束*函數(shù)值gi(X )均大于零(i =1, 2, 3),所以這組約束條件對其最優(yōu)點(diǎn)X*都不起作用.換句、一、一 " 一一 ，一* 、 ， 一一 ， &

53、quot;.一 、_, * _ _ *話說，如果除掉全部約束，其最優(yōu)點(diǎn)也仍是同一個(gè)X點(diǎn).因此這種約束優(yōu)化問題與無約束優(yōu)化問題是等價(jià)的.圖 2.9 (b)所示的約束最優(yōu)點(diǎn) X*在g1(X)的邊界曲線與目標(biāo)函數(shù)等值 *線的切點(diǎn)處.此時(shí)，g1(X ) =0 g2(X )>0，g3(X )>0 ,所以g1(X)是起作用約束， 而其余的兩個(gè)是不起作用約束.既然約束最優(yōu)點(diǎn)X*是目標(biāo)函數(shù)等值線與g1(X) 邊界的切點(diǎn)，則在 X*點(diǎn)處目標(biāo)函數(shù)的 *梯度vf(X )與約束函數(shù)梯度矢量7g1(X )必共線，而且方向一致.若取非負(fù)乘子心之0, *則在X處存在如下關(guān)系_ * 一 *Vf(X )-W(X )=0.另一種情況如圖2.9 (c)所示.當(dāng)前迭代點(diǎn) Xk在兩約束交點(diǎn)上，