最優(yōu)化理論與算法(第一章)

1、最優(yōu)化理論與算法（數(shù)學(xué)專業(yè)研究生）第一章引論§ 1.1引言一、歷史與現(xiàn)狀最優(yōu)化理論最早可追溯到古老的極值問(wèn)題，但成為一門獨(dú)立的學(xué)科則是在20世紀(jì)四十年代末至五十年代初。其奠基性工作包括Fritz John最優(yōu)性條件（1948）, Kuhn-Tucker最優(yōu)性條件（1951）,和Karush最優(yōu)性條件（1939）。近幾十年來(lái)最優(yōu)化理論與算法發(fā)展十分迅速，應(yīng)用也越來(lái)越廣泛?，F(xiàn) 在已形成一個(gè)相當(dāng)龐大的研究領(lǐng)域。關(guān)于最優(yōu)化理論與方法，狹義的主要指非線性規(guī)劃的相關(guān)內(nèi)容，而廣義的則涵蓋：線性規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃、幾何規(guī)劃、多目標(biāo)規(guī)劃、隨機(jī)規(guī) 劃甚至還包括變分、最優(yōu)控制等動(dòng)態(tài)優(yōu)化內(nèi)

2、容。本課程所涉及的內(nèi)容屬于前者。二、最優(yōu)化問(wèn)題的一般形式1、無(wú)約束最優(yōu)化問(wèn)題min f （x）（ 1.1）x. Rn2、約束最優(yōu)化問(wèn)題m in f （x）C（x） =0, i E（ 1.2）s.t.Ci （x） Z0, i E I這里E和I均為指標(biāo)集。§ 1.2數(shù)學(xué)基礎(chǔ)一、 范數(shù)1. 向量范數(shù)|x| = max Xj（ 1閃范數(shù)）（1.3）n|xL =無(wú)Xi（ 11 范數(shù)）（1.4）i ztn 1x2=（VXi2）2（ I2范數(shù)）（1.5）i z±X pXip)pi J（打范數(shù)）(1.6 )1x A = (x Ax )2( A 正定)（橢球氾數(shù)）(1.7 )事實(shí)上1范數(shù)、2

3、 范數(shù)與 :范數(shù)分別是p 范數(shù)當(dāng)p = 1、2和p）：:時(shí)情形。n12. 矩陣范數(shù)定義1.1方陣A的范數(shù)是指與 A相關(guān)聯(lián)并記做 A的一個(gè)非負(fù)數(shù)，它具有下列性質(zhì)： 對(duì)于A = 0都有 A 0，而A=0時(shí)A=0 ； 對(duì)于任意k乏R，都有kA = k岡； A B乞A B ; AB , A B ；若還進(jìn)一步滿足： |ax|a|x|p則稱之為與向量范數(shù)IJ相協(xié)調(diào)（相容）的方陣范數(shù)。若令A(yù) =maxl!A單（這里|x|是某一向量范數(shù)）（1.8）可證這樣定義的范數(shù)是與向量范數(shù)二相協(xié)調(diào)的，通常稱之為由向量范數(shù)誘導(dǎo)的方陣范數(shù)。特別地,對(duì)方陣A =（aj ）n n，有：n|A=max送aij （列和的最大者）（1

4、.9）j i仝n| A=max送aij （行和的最大者）（1.10）i j壬A 2 =（ 'aTa）2 （ ' ata表示AT A的特征值的最大者）（1.11）稱為譜范數(shù)（注：方陣A的特征值的模的最大者稱為A的譜半徑，記為 J（A）。對(duì)于由向量誘導(dǎo)的方陣范數(shù)，總有：AxI =1 （ I為單位陣）對(duì)于方陣范數(shù)，除了上述由向量范數(shù)誘導(dǎo)的范數(shù)之外，還有常用的Frobenius范數(shù)，簡(jiǎn)稱F-范數(shù)：nn11A F =（工:二a/）2二tr（ AT A）2（1.12）ij _1及加權(quán)Frobenius范數(shù)和加權(quán)l(xiāng)2范數(shù)：Am,f = MAMf(1.13)Am,2二MAM2(1.14)其中M

5、為對(duì)稱正定矩陣。3. 范數(shù)的等價(jià)性定義1.2設(shè)二與一是Rn上的兩個(gè)范數(shù)，若存在叫2 7，使得J x|：,|x J x ：，* Rn（行5）則稱范數(shù) 二與If是等價(jià)的。容易證明：x2乞x!乞訂X 2(1佝x| J |x 2 n X :(1.17)x| J |xn x ；;(行8)XFX2-!(1.19)l n X 2 乞 X 人 1 x 220)其中1是A的最大特征值，而'n是A的最小特征值。由此可見(jiàn)，Rn中的常用向量范數(shù)均等價(jià)，事 實(shí)上還可證明：Rn中所有向量范數(shù)均等價(jià) 。4. 關(guān)于范數(shù)的幾個(gè)重要不等式。 Cauchy-Schwarz 不等式(1.21)xTy勻（當(dāng)且僅當(dāng)x和y線性相關(guān)

6、時(shí)，等式成立） 設(shè)A是正定矩陣，則xTA <|XU|y|A (當(dāng)且僅當(dāng)X與y線性相關(guān)時(shí)，等式成立)(1.22)由(x, y) =xTAy是一種內(nèi)積，以及一般內(nèi)積的Cauchy-Schwarz不等式即得。 設(shè)A是n n正定矩陣，則 XTy|蘭|x|A|y|A丄(僅當(dāng)X與A-y線性相關(guān)時(shí)，等式成立)(1.23)乂川從劃蘭|虬卜嘰十口比丄(仙)其中的不等號(hào)由可得。 You ng不等式：假定p與q都是大于1的實(shí)數(shù)，且滿足丄+丄=1y/x,y R十，有p qp qx yxy，(1.25)p q當(dāng)且僅當(dāng)xp =yq時(shí)，等式成立。其證明由算術(shù)一幾何不等式直接給出，事實(shí)上11p qxy =(xp)p(y

7、q)q豈 丄(算術(shù)_幾何不等式)p q H?lder不等式n"p yq 十 xii ±)p(送 yii 1q)q(1.26)其中p與q都是大于1的實(shí)數(shù)，且滿足1 11，其證明利用You ng不等式可得。5# Minkowski不等式(1.27)x y p x 卩 Ty p，( p -1)后面將利用凸函數(shù)理論予以證明。二、矩陣求逆與廣義逆1. Von-Neumann 弓 I理定理1.3 (Von-Neuma nn引理)設(shè)E Rn n , I Rn n是單位陣，|£是滿足I =1的相容矩陣范數(shù)。如果E ：:1，則(I -E)非奇異，且oO1k(IE ,K _0a111

8、-11A (A-b)I若A非奇異，a'(A-B) : 1 ,則B非奇異，且bQO1i k1B 一八(I -A B) A -,Sk(I-E證明：因?yàn)閨 E <1，故 Sk = 1 +E +E? +Ek定義了一個(gè) Cauchy序列，因而收斂。由k _07#可得故有k -0=lim Skk_ j：:=(I-E)進(jìn)一步有再令知-E)十送|Ek蘭E =1 -AB ,E 二 I -aJbk +lim Sk(l E) = lim (I E ) = Ik 二J；,：#由上面結(jié)論可得,Q01111 k(I -E) =(A B)八(I - A B)k =0所以有B A = x' (IAB)k

9、 Ak z0進(jìn)一步有bik俎qo八A(A-B)k =S#注：這個(gè)定理表明，若b充分接近一個(gè)可逆矩陣 a，則b也可逆，且逆矩陣可由a的逆矩陣來(lái)表示。上述定理還可以寫成下面形式:定理1.4設(shè)A, B R曲，A可逆，| A*蘭0(。若| A b|蘭B，且胡<1，則B可逆，且B，<1 -：沖#證明：只需注意到|a4(B _A)|蘭A| B _a| WaP <1，再由上述 Von-Neumann引理即得。#2.廣義逆定義1.5設(shè)A Cm n，若A Cn m滿足:AA A = A, A AA = A , (AA )* = AA ,(A A)* 二 A A(1.28)則稱A是A的廣義逆。其

10、中 A*是A的共軛轉(zhuǎn)置。廣義逆的求法設(shè)ACm沁，秩（A）=r，若A直交分解為A=QRP，其中Q , P分別為m x m, nn酉矩陣,R EC m>n , R =，其中R,是r r非奇異的上三角矩陣。則A的廣義逆為:A” =P*R Q 其中 R =R；若A的奇異值分解為A二UDV *，其中0是A的非零奇異值,(1.29)均為酉矩陣，的廣義逆為:Cm n，而A” =VD U *，其中D(1.30)若A的最大秩分解為A =BC，貝U A的廣義逆為:-1A"二C (CC ) (B B)-1*B .(1.31)矩陣的Rayleigh商定義1.6 A是n n Hermite矩陣,u Cn

11、，則稱#(1.32)u AuR.(u)u u為矩陣A的Rayleigh商定理1.7設(shè)A是n n Hermite矩陣，則 Rayleigh商具有下列性質(zhì):1）齊次性:RCu）= R,(u)(二仁乞0 )#2）極性：#u Au3)極小殘量性質(zhì)對(duì)任意u三C n = min u Au = min * u|b 2u -0 u u這里 ,，n分別對(duì)應(yīng)于矩陣 a的最大與最小特征值。這表明Rayleigh商具有有界性:< R .(u9#|(AR 扎(u)l)u| W|(APl)u|，于卩 W R。證明：1)由定義直接可得。2) 由A是Hermite矩陣，故存在酉矩陣 T，使T* AT 一； =n又令 u

12、 =Ty，且 |u|2 =1，故 I y|2 =1u Au = y T ATy* 2=y Ay =入 y12+扎yn當(dāng)取y =(1,o,0)時(shí)達(dá)到最大值'1，當(dāng)取y =(0, 0,0,1)時(shí)，達(dá)到最小值3) 令 s(u)二 Au - R (u)u， (u = 0)，貝y Au = s(u) - R (u)u，可直接驗(yàn)證s(u), R,(u)u ,0 ,由于(s(u ), u ) = (Au R ,(u )u , u) =u Au R,(u)u u =0注意到R ,(u)u是與u共線的，故s(u)與R ,(u)u正交。即R ,(u)u與s(u)是Au的正交分解。因而R ,(u)u是Au在

13、L S 上的直交投影，因而具有極小殘量性質(zhì)。2四、矩陣的秩一校正當(dāng)矩陣A變到A - uvT時(shí)，即在A上加了一個(gè)秩為1的矩陣，稱為秩一校正。下面討論如何求 秩一校正的逆，行列式，特征值及矩陣分解。定理1.8設(shè)AERm"是非奇異的，u,vRn是任意向量。若1+vTAu0，則A的秩一校正A+uv 非奇異，其逆矩陣可以表示為J T Jt iiAuv A_“ cc、(A uv ) - = A 廠(1.33)1 +v A_u證明：可直接驗(yàn)證。上述定理的可進(jìn)一步推廣為：定理1.9設(shè)A是非奇異矩陣，U ,V是n x：m矩陣，若I +V * AU可逆，則A +UV *可逆，且(A UV*)=A丄一 A

14、U(IV * A "U ) "V * A J(1.34)下面介紹關(guān)于秩一校正的行列式定理定理 1.10 1)det( I uvT) =1 vTuTTTTTT2丿 det( I - U1U2 - U3U4 )二(1 - U1 U2)(1 - U3 U4) _(山 U4)(u2 U3)證明： 1 )若u =0，則結(jié)論顯然成立；若 u = 0，設(shè)w是(I uvT)的特征向量。貝U(I uv T ) - w易見(jiàn)w要么與v垂直，要么與u平行。若與v垂直，則特征值為1;若與u平行，則對(duì)應(yīng)特征值為1 vTu。進(jìn)一步，平行于u的特征向量只有一個(gè)(線性無(wú)關(guān))，而垂直于v的線性無(wú)關(guān)的向量有 n

15、_1 個(gè)，它們均為IuvT屬于特征值1的特征向量，即特征值1是(n-1)重根， 而1 - vTu是單根。故有det( I 亠uv T)=、二-n = 1n(1 亠 vT u) = 1 亠 vT u。2) 對(duì) I +u1u2' +u3u： =(l +ue T 廠 I + (I + UtU：)u3u： I使用上面結(jié)果，故有：det( I +ue 2： +u3u4T) =( I +uu2) 1 +u4： (I +u1u2：) u3 I丄 TI,丄 T6U；=(1 +5 u2)1 +u4 (I T)U3-1+u22_-(1 u；u2)(1 u；u4)(u；u4)(u：u3)。關(guān)于秩一校正矩陣的

16、特征值定理。定理1.11設(shè)A是對(duì)稱矩陣，其特征值為 _，2 -'n，又設(shè)A = A 二uuT，其特征值為_(kāi):，那么1）若二 7 ,則 1- 2 - - 'n2)若二：0，則 s _ s _ 2 一 2 一 n _ 'n五、函數(shù)與微分1.多元函數(shù)的梯度與Hessian矩陣梯度If (x)=(丄f)T(1.35)Hessian 矩陣(1.36)r2 f丸2方向?qū)?shù)：(設(shè)d為一方向向量，即長(zhǎng)度為1的單位向量，顯然與范數(shù)的取法有關(guān))11#(1.37). f (X 5) - f(X)limf (x) d注：對(duì)歐氏范數(shù)(2 范數(shù))而言，梯度方向是函數(shù)上升最快的方向，而負(fù)梯度方向則是

17、函數(shù)下降最 快的方向。正因?yàn)檫@個(gè)原因，使得梯度在最優(yōu)化理論與算法中占有特殊重要的地位。若f ： Rn ； R在開(kāi)凸集D上連續(xù)可微，則有(1.38)1f (x d ) = f (x)亠 I f (x td )T ddt = f (x)亠 f ( )T dL0其中三(x, x - d )。上式也可改寫為:f (y) = f (x) I f (x t(y -x)T (y -x) t- (0,1)或f (y) = f (x) I f (x)T (y - x) o( y -x )若f在D上二階連續(xù)可微，則對(duì)于任何x, x d ：= D，存在；：=(x, x - d )，使得1f (x d)二 f (x)

18、 I f (x)T d d 2 f ( ') d!= f(x) 、f(x)Td d- 2 f (x)d o( d )2!2.向量函數(shù)的微分設(shè)F ： Rn > Rm是一個(gè)向量函數(shù)，若其每個(gè)分量f'i =1，,m)都連續(xù)可微，則稱F (x)連續(xù)可微。F (x)在x處的導(dǎo)數(shù)記為:CXiF(x)=-戲1次n:=J(x)(1.39 )：fm；：Xif m：Xn稱之為F (x)在x處的Jacobi矩陣，而稱I F(x) = (F (x)T為向量函數(shù)F (x)在x處的梯度。右F ： R r Rm在開(kāi)凸集D上連續(xù)可微，則對(duì)任何 x, x亠d三D，有：1F (x d) F (x) = j

19、F (x td )ddt定義1.12 G：RnTRm>n在xDURn處稱為L(zhǎng)ipschitz連續(xù)的，若D，都有G(v) G(x)空 v x。若在D中每一點(diǎn)均Lipschitz連續(xù)，則稱G在d上Lipschitz連續(xù)，記為G Lip (D )。其中，稱為L(zhǎng)ipschitz常數(shù)。定理1.13 (向量函數(shù)線性化近似的誤差估計(jì))設(shè)F : Rn； Rm在開(kāi)凸集D上連續(xù)可微，F(xiàn) (x)在x的鄰域證明:D中Lipschitz連續(xù)，則對(duì)于任何x d三D，有I II | 2F (x +d) F (x) F x)d 蘭一|d|.Y1 'F (x d) F (x) F (x)d F '(x L

20、：;d)dd : - F (x)dL01-_F (x : d) - F (x) dd :-0從而F ( d)- F( x) F ( x)c)>d d13#1 1乞 0 (F (x ： d) F (x) d d：豈 0 F (x ： d) F (x)|d注：在1“咖d|d|'d 上 d2.上述證明過(guò)程中的第一個(gè)不等式并不平凡,它實(shí)際上要求，對(duì)一般向量函數(shù)的積分，下述命#題成立。命題：對(duì)可積向量函數(shù)f (t) = (f't), f2(t),fn(t)T，有 J f 吐 “ | f (t)|dt #證明：對(duì)于l1范數(shù)上述命題是成立的，這是因?yàn)?#bbbbf(t)dt = fi(

21、t)dt + f2(t)dt 十- +fn(t)dt11bbbb< J； fi(t)dt + f2(t)dt 葉 + 仁水=(fi(t) +|f2(t)葉 +1 f n (t)dtba 3嚴(yán)對(duì)于I 2范數(shù)上述命題也成立。事實(shí)上，II 2門bnb b(f(t)dt =瓦(fi(t)dt)2=£ f(t)fi(s)dtdsiidb b nb b(送 fi(t)fi(s)dtds E J送 fi2(t)J送 fi2(s)dtdsi 2d17Al/_k2-I a-Z fi2(s)ds =( J送 fi2(t)dt)2 =( | f (t)dt|dt)i 4i ±對(duì)于一般范數(shù)，

22、需借助于Banach空間弱Riemann積分理論進(jìn)行證明。定理1.13給出了線性近似的誤差界，下面考慮二次近似的誤差界。定理1.14設(shè)f ： Rn r在開(kāi)凸集D Rn上二次連續(xù)可微， 2 f (x)在x的鄰域D上Lipschitz連 續(xù)。則對(duì)于任何 x D有：_T1丁廠2f|3f(x+d)-.|f(x)+Nf(x) d+d 可 f(x)d 蘭一|d|證明：f (x +d )- f xx(T(d 一dTW2f x d )21 t1 t=d T 可2 f (x d )dd adt d 丁可2 f (x)dd adtT 2T 2d ' f (x Ud)d -d ' f (x)d|-：

23、；d d ： dti ti i y.d ： dt dod3定理1.15設(shè)F ：R -； R在開(kāi)凸集D二R上連續(xù)可微，則對(duì)任何 x,u,vD，有F(u) -F(v) -F (x)(u -v)F (v t(u - v) - F (x)若進(jìn)一步F在D中Lipschitz連續(xù)，則有:F(u) -F(v) -F (x)(u -v) <215證明:F (u) - F (v) -F (x)(u v)1=f f "(v+t(u _v) F &) (u _v)dt 01蘭F "(v +t(u -v) -F "(x)”u - v dt(由此式即可得第一部分結(jié)論)1_&#

24、176;v t(u-v)-x|u-vdt1=0 (1 -t)(v x) t(u x) u - V dt1-X 0(1-t)dt U -X#1定理1.16設(shè)F , F 滿足上面定理?xiàng)l件，假定矩陣If (x)存在(這蘊(yùn)含著 F (x)是方陣，即F(x):R“t Rn)° 則存在名:>0,，使得 F u, v D ，當(dāng) max | -x v -x 蘭名時(shí)，有:二 |u V F U- H 匹：-u V證明:F(u) F(v)| |F (x)(u _v)| 亠|F(u) F(v) F (x)(u v)_ 1彳|f Yx)| +?(|u -x|-V#勿 F &)|+Y町|u v|=

25、:u -v|(令：=F (x);)從而右邊不等式得證。另一方面，注意到：|u v| =|f f(x)F F(x)(u v)| m|fL(x)(u v)|)故有 |F(u) F(v)X| F(x)4u|DF4u) F( v) F-(x)(u v)F(U#1 1因此，若??；：:：1 I ,且令1- ；( 0)，則得左邊不等式結(jié)論。|f(x)牛|Fx)1()-F (x)，從而有> :Z > 0。由 1 二 F (x) °F (x)豈 F (x)| F (x)，可得六、差商(偏差商)設(shè)F(x)=(匚&)，fm(x)T是一個(gè)向量函數(shù)，其Jacobi矩陣的第i行j列元素可用差

26、商(偏差商)fi (x he j) - f 伙) aijh近似。由偏差商構(gòu)成的矩陣A = (a )m n稱為f (x)的差商矩陣。顯然差商矩陣的第j列為F (x he" -F (x)h關(guān)于差商矩陣與 Jacobi矩陣有如下誤差估計(jì)式定理1.17設(shè)F ： R“ T Rm在開(kāi)凸集D上連續(xù)可微，F(xiàn) "(x)在D中Lipschitz連續(xù)，則 |AjJ(x)2|h若采用的范數(shù)是I,范數(shù)，則有：|AJ(x)Lmh證明：將定理1.13中的d取為hej，則有hejF (x he)_F (x) _J(x)hej 二 F (x he)-F (x) _ J (x)兩邊同除h，則有Aj-J(x)丄

27、一1<-h217#類似地，也可以用中心差分來(lái)近似梯度和Hessian矩陣，并有如下誤差估計(jì)結(jié)果。定理1.18設(shè)f ： Rn r R在開(kāi)凸集D上二次連續(xù)可微，I 2f (x)在D上Lipschitz連續(xù)，又設(shè)所采用的范數(shù)滿足ej=1， (i =1,，n)，定乂 f (x)在x處的中心偏差商為:aif (x hej) f ( x hej)ai如采用I：:范數(shù)，則2h1 2 -Vf (x» 蘭_ h6-V 26a -Nf (x)蘭一h其中a =何，aJT 證明:由定理1.14有:f (x d )- f x 八 f x(T d-丄 d：2f2令d = hei，則有#1 2 2 f (x

28、 hej - f (x) -h I f (x)ihl f2(X) iiyJ 3_ -h6再令d = -hei，又有1 2f (x hej f (x)亠h ：計(jì)(x)i h :：/ f2(X) ii令上兩式中左端絕對(duì)值內(nèi)的部分分別為j則有x jh )e 2h (fi )x 冬 | 片一由此即得:f ( x hej) - f (x - hej)2hW (x)i =由l. 一范數(shù)的定義，有定理1.19設(shè)f (x)在開(kāi)凸集D上二次連續(xù)可微， 2f (x)在D上Lipschitz連續(xù)，采用的范數(shù)滿足ej=1 ，(i =1,，n),假定 x, x hei, x ' hej, x hei hej D

29、 (i, j =1,，n)。定義:f (x 亠 hei he)一f (x hei) f (x he) f (x)aj則有:aijWf(x)ij| 中h19#A f (x) _ 5 hn3若采用矩陣范數(shù)是IJ：或F-范數(shù)，則 (這里A =(aj)是Hessian矩陣的離散形式)。1證明： 令】-f ( x 亠hej 亠 he j) - f (x) - (he- he ：)- f (x) (he-he：)- 2 f (x)( he-he ：) jj2jj1 T 2 (T hej (I f x heG )()2T1T 2=f (x 亠 he ：) - f (x) - (he：) I f (x) (h

30、e ：) '、f (x)( he：)o( - P- n _2:=f (x 亠 hej ) - f x ) hei T I) f x經(jīng)簡(jiǎn)單計(jì)算有:h2f ( x)ij)#又由定理1.14有,- hei he ：618 h36#進(jìn)而有V",3 =汁361II31n< he j :二6j II6ai_2-勺 f (X)ijh31< (ah105+ P 十口)= Yh=-Yh63再由矩陣-丨一一及F-范數(shù)的定義立即可得：1 COA _ '、2 f (x)5 hn§ 1.3凸集與凸函數(shù)一、凸集(Convex Set)1 凸集的概念 定義1.20設(shè)S Rn，

31、若-x1, x S，都有:-Xt (1 -匚)x2 ：= S 一匚 0,1則稱S是凸集。定理1.21 Rn的子集S為凸集的充分必要條件是-X-X2，Xm S有m其中、©丄0 (i =1,，m)且疋二人=1 。凸集的例子：i z1n維球、半空間、超平面、:x Ax =b,x _0f等均為凸集。定理1.22若S,S2是Rn中的凸集，則1 )0 S2是凸集；(事實(shí)上，任意多個(gè)凸集的交仍為凸集)2 ) S±S2 =& ± X2 % 乏 S,X2 E S2 也是凸集2.凸包 集合S的凸包的定義如下：mmConv( S)=彳 x x =遲 阿備,乂嚴(yán) s,瓦 8=1,

32、8 蘭0, m =1,2,i zfci =fcS的凸由定義知，集合S的凸包由S中元素所有可能的凸組合構(gòu)成。還可證明：它是所有包含集合 集的交，即它是包含集合 S的最小凸集。3 錐、凸錐 定義1.23設(shè)K二Rn，若-x三K , -，. 0，有，x K，則稱K為錐；若錐K還是凸集，則稱之 為凸錐。容易證明：K是凸錐的充要條件是，K對(duì)正組合運(yùn)算封閉。定理1.23若c Rn是凸集，則C的閉包C也是凸集。證明：-X, y：=C，則存在序列XkWk；=C，使得lim xk = x， lim yk = yk ： ： k-:從而有丨 i m 仇 G1 yj = ) x ：卜一'( 1y ,10,1 I

33、k注意到Xk (仁 yj = c及c的閉性，可知 x (1 '；)y 三 C這就證明了 C是凸集。4.極點(diǎn)與極方向定義1.24設(shè)S Rn是非空凸集，x S，若x不在S中任何線段的內(nèi)部，則稱x是凸集S的極點(diǎn)。 顯然，多邊形頂點(diǎn)、圓周上的點(diǎn)均為極點(diǎn)。定義1.25設(shè)S Rn是閉凸集，d為非零向量，若對(duì)任意 x S，當(dāng) _0時(shí)，總有xS ,則稱d為S的方向；若S中的某方向d不能表示為該集合的兩個(gè)不同方向的正的線性組合，則稱d為S的極方向。極點(diǎn)與極方向是凸多面體中非常重要的概念，在線性規(guī)劃中有重要應(yīng)用，關(guān)于這些方面的詳細(xì) 討論，可參閱有關(guān)線性規(guī)劃教材。二、凸函數(shù)定義1.26設(shè)S Rn是非空凸集，

34、f是定義在S上的函數(shù)，若對(duì)任意的 X-X2，S都有：f (a x + (1 a % 蘆a f (x )(壬 f) 2x( ) Fa E ( 0 , 1 )則稱f是S上的凸函數(shù)。凸函數(shù)的另一等價(jià)定義是:f (7Xi)，if (Xi)i ±i An其中，7打=1_0。若X.PX2時(shí)，不等式嚴(yán)格成立，則稱f在S上是嚴(yán)格凸的。若_f在S上i 2是凸(嚴(yán)格凸)，則稱f在S上是凹(嚴(yán)格凹)。定理1.27設(shè)f (x)是定義在凸集S上的凸函數(shù)，1) 若_ 0 ,則f (x)是S上的凸函數(shù)；2) 若匚2是S上的凸函數(shù)，貝U f1 - f2也是凸函數(shù)。m由此立即可得：若 ft，fm是S上的凸函數(shù)，二，&

35、gt;m_0，則:-ifi也是S上的凸函數(shù)。i <凸函數(shù)的一階特征定理1.28設(shè)SRn是非空開(kāi)凸集，f是定義在S上的可微函數(shù)，則f為凸函數(shù)的充要條件是：f(y)_f(x) f(xf(y_x)_x, y S證明：必要性，設(shè)f是凸函數(shù)，則對(duì)任意的：(0,1)，有f (: y (1 - )x )_ : f (y )(壬 f) x("亠f(x + a(y_x)_ f ( x)因此有f(y)- f ( x)a令一；0 得、f(x)T (y- x)乞 f ( y)- f ( x即f ( y) _ f ( x)，、f (；)(y x必要性得證。充分性：設(shè) f ( y)蘭 f (x) + W

36、(x)T (y x) , Vx, y E S 成立。任取 Xt, x2 S 及：£ 三(0,1)，令 x = Xt (1 -)X2，于是有：f(xj 一 f(x) Vf (x)T(xx)f (X2 ) _ f (x)八、f (X)T(X2X)于是有：f ( X )(1 ： f X -) f X 八 fT x:) 1 x ¥ 1 2 x)- x=f ( x) = f ( ： Xi (1 -一)X2)即f © x + ()為)蘭。f (X 曠 (七 f) 2x()亦即f (x)是凸函數(shù)，充分性得證。幾何解釋：凸函數(shù)圖像位于割線之下，切線之上。凸函數(shù)的二階特征定理1.2

37、9設(shè)S二Rn是非空開(kāi)凸集，f是定義在S上的二次可微函數(shù)，則f為凸函數(shù)的充要條件是S上的每一點(diǎn)的 Hessian矩陣半正定。證明：充分性，設(shè)V/ 2故一 p 2 f (x) p 0( p 02兩邊除以 2并令0，則有T 2pf (x ) p 丄 0即、2f(x)半正定。注：對(duì)嚴(yán)格凸函數(shù)有類似的一階與二階特征，但要注意一些細(xì)微的差別。定理1.30設(shè)S Rn是非空開(kāi)凸集，f是定義在S上的可微函數(shù)，則f為嚴(yán)格凸的充要條件是f ( y) f ( x) l f (Tx) (y ,x -x, y S,x = y證明：充分性證明與前述凸函數(shù)情形完全類似，故從略。必要性的證明如下：f (x)在每一點(diǎn)x E S均

38、半正定。任取x, y S，由中值定理有：f (y)= f X 八 f x(T )y 4x TyxT'2f y(x»()_ f ( x)亠f ( x) ( y - x)(其中 在以x, y為端點(diǎn)的線段上)所以，f (x)是凸函數(shù)。必要性，設(shè)f (x)是凸函數(shù)，則任取 x S，對(duì)任意的p Rn，充分小時(shí)有f ( x 丁 .；，p) _ f( x)r，'f( Tx)p-2另一方面f(x+p)=f x "W X(Tp+pP2f x p 巧 I >L(p ()21設(shè)f(X)在S上嚴(yán)格凸，-x,yws且x = y，令z=_x -21y，則顯然z .= S。由于f(

39、 x)嚴(yán)格凸，211故有f(z) ： f(x) f(y)由上兩式有f ( z)_ f ( X) I f (Tx)(z11f(x) f (y) . f(x)22111f ( y) f ( x)222'、f(x)T (z X)f (Tx) (y x)2223#因此有定理1.31設(shè)是非空開(kāi)凸集,f是定義在S上的二次可微函數(shù)，若 -xS,' 2f(x)正定，則f (y) f (x)、f (x)T(y x).#f (x)為嚴(yán)格凸函數(shù)。注：嚴(yán)格凸不能推出I 2f(X)正定,因此I 2 f(X)正定是嚴(yán)格凸的充分條件，但不是必要條件。如4”f(x)二 X ， f (x)2卄二 12x ， f

40、 (0)不正定，但它是嚴(yán)格凸的。定理1.32設(shè)SRn是非空開(kāi)凸集,f是定義在S上的凸函數(shù)，是一個(gè) 實(shí)數(shù)，則水平集#x ：二S, f (x) 芒；是凸集。證明：略那么所以定理進(jìn)一步，若f (x)是連續(xù)凸函數(shù)，則f(x)=f ( l i XV =) lfi kk_jDCx L.，故L：.為閉集。1.33L.是閉凸集。_(； ；)設(shè)f (x)是s二Rn上二次連續(xù)可微的凸函數(shù),T 2.u f (x) u - m事實(shí)上，設(shè)且存在常數(shù)- x L (x0)， u Rn:Xk ；二 L 一，且 lim Xk = x k_, -m - 0，使得#則水平集L (x0) - ；x x S, f (x) _ f (x

41、0) ?是有界閉凸集。證明：由上面討論可知，L (x0)是閉凸集，因而僅需 證明L(x0)是有界的。由于L (x0)是凸的，因而y2x_x, y L( ox), x ： (y x)y (1 - ： )x L(x°)，從而有 (y-x)： f(x枚 (y-為)(尸 x)冷 m由Taylor展開(kāi)式,TT 2f(y) =f(x) f(x) (y _x) .o.o(y_x) f(x ：.(y_x)(y_x)d：.dt1f(x) lf(x)T(y x) omy._x二 f ( x) I f ( (y _ x)12可知,-y L (Xo), y = X。，有25#T 1 |f (y) - f(X

42、。)_ '、f (Xo) (y -x°) m y2 111-m y x2再由f ( y) f (ox ) ,o#故有XinXii 土p/p+ (送 yip/i去1I f(X。)m y _x2|y Xo| 蘭一|Rf (Xo)|m由y是L (x0)中任一向量，所以L (x0)有界，因而L (x0)是有界閉凸集。x y卩空x卩 y卩，即:定理1.34(Minkowski不等式)對(duì)p _1，有#證明：當(dāng)x或y為零向量時(shí)，結(jié)論顯然成立。當(dāng)p = 1時(shí)，也易證明。以下設(shè) x, y = 0，且p>1。p考慮函數(shù)w(t)=tp， t>0由于®"(t)= p

43、(L 供,0故®(t)嚴(yán)格凸。注意到擁p丄|y|p1+=1IIXL+IMIp IXL+IMIp由函數(shù)-:(t)的凸性，于是有,#因此,Xi yiln<zi韭_Xp_JXip_ypyip#pp =1Xp yp ypxL y p|x|由定義立即可知：一致凸=嚴(yán)格凸二.凸。致凸函數(shù)的判別定理定理1.36設(shè)f (x)是非空開(kāi)凸集D上連續(xù)可微函數(shù)，則f (x)在D上一致凸的充要條件是存在常數(shù)-0，使得證明:f(y) -f (x) _、f(x)T(y -x)y -x先證必要性。若f (x) 一致凸,2 ，一x, y Dppn由此即得y Xj + yji 2三、一致凸函數(shù)定義1.35設(shè)f是非

44、空凸集D上的函數(shù)，若存在一個(gè)常數(shù)1.0，使得對(duì)任意的x, y . D，及任意很三(0,1)。均有:f (x) (1 - :) f ( y) - f (x (1 -)y) _ (1 - : ) |則稱f (x)在凸集D上一致凸。#:f (x) (1 -)f (y)f (x (1 -)y) _ (1 -)J* xy從而:f (x) f (x) (1 - ： ) f (y) _ f (： x (1 - ： ) y) - f (x)(1)|x y因此f(y)f(x)_f(：x (1 =)y) f(x) xy*)f (、；x (1 - : ) y) = f (x (1 -)( y - x)=f (x)

45、+(1 G) W (x)T (y x) +o(|(1 G)( y x)|)將上式代入(*)即得:#f (y)(x),f(x)T(y_x)皿 922 x_y1 _a2272#f (y)(x)-、'、f (x)T (y x)亠| y x再證充分性。任取x,D，令x = ： x亠(1 - ： ) y，：丄三(0,1)。由D是凸集，故 x -D，因而有:f (x)-f (X):-j yf (x)T (x _x)丄X _xf (y)-f (X)小f(x)T (y 一刃：計(jì) y x2#2#兩式分別乘:-和(1 -二)再相加，則有X_X 2 (1 _：) y _x 1 2:f (x) (1 一)f

46、(y) - f (壬)_ l-：,:-1將x = ： x亠(1 - ：) y代入即得結(jié)論:-f (x) - (1二)f (y) f (： X (1二)y) _ (1二)、川 x -y2#2#定理1.37設(shè)f (x)是開(kāi)凸集D上連續(xù)可微函數(shù)，則f(x)在D上一致凸的充要條件是:-7-、-存在常數(shù)2#2#1 - 0，使得 、f ( y) _、f (x)T(y _x)；“：討 y _x證明：參見(jiàn)徐成賢等著近代優(yōu)化方法P15。定理1.38設(shè)f (x)在開(kāi)凸集D上二階連續(xù)可微，則f(x)在D上一致凸的充要條件是:-7-八、-P7.存在常數(shù)2#2#m 0，使得:2u " u 1令m，則2 f (

47、x)u，-X D， - U Rn 證明：充分性：-x, y三D，有1f (y) - f(X)八 f(X)T (y -X) (y_x)T、2f( )(yx)22#2#其中=x r( yx)， (0：:V ：: 1)。由于D是凸集，故-D。因此,2#2#()(y - x)2#2#f (y) f (X)-yf (x)T(y2#2#必要性：設(shè)f (x)在D上一致凸。任取x D，uRn且u 0，則有2#2291 1I 2 f (x) u = lim I f (x .；”u) - I f (x)T u = lim 2 f (x.；”u) - I f (x)T ；/. j0 Jlim。丄u2 八 u2.J治

48、。疔四、凸集的分離與支撐凸集的分離與支撐定理在研究約束最優(yōu)化問(wèn)題的最優(yōu)性條件時(shí)具有基本的重要性，起著十分關(guān)鍵的作用。定理1.39設(shè)S二Rn是非空閉凸集，y - S，則存在唯一的點(diǎn) 廠S，它與y的距離最短。進(jìn)一步 x與y距離最短的充要條件是：(x 一 * (x - y) _ ,0 - x S證明：先證定理的第一部分 存在性 任取一點(diǎn)x°三S，則集合D = x |y xm|yx0|,x S為一非空有界閉集， 而y-x是x的連續(xù)函數(shù)，故它必在D的某一點(diǎn)x上取得最小值，此x即為所 求。注意到x S，而y y S，必有| X - y = r . 0。唯一性 假定還有乂隹S，滿足 | y 岡彳y

49、二* =。由S的凸性，貝y- S2考慮y -x|+環(huán)一打=r2 | 22由r是S中點(diǎn)到y(tǒng)的最小距離，故上式必取等式。因而必有n Fy x = (y x )再由若=-1，則得y-x = y-x，得 二 1。y-x - - y 亠 x： 2 y 二x 亠 x ,與y F S矛盾。因而只能是 =1，即y_k=y_X，或x = X，唯一性得證。再證定理第二部分 若-x三S，都有T(x -x) (x - y) _ 0，y-x42 2二 y_x| x_xx -(x y>* X 習(xí) y- x即x與y有極小距離。反之，若-x三S，都有X -y 一 |x - y由于對(duì)充分小的因此另一方面,y _x - '(x _x)2-y所以xxyJ|x x|2，(xx)x y)-Tx -) x( x_) y兩邊同除，并令0 ,即得所要的結(jié)果。點(diǎn)與凸集的分離定理定理1.40設(shè)SRn是非空閉凸集,則存在向量p = 0和實(shí)數(shù)爲(wèi)，使得pTx_，- xS，并且同時(shí)滿足即超平面pTx = 嚴(yán)格分離點(diǎn)y和閉凸集S 。證明：由于S是閉凸集， X S。故定理1