工程優(yōu)化方法及應(yīng)用 第二章

1、Page 11 代數(shù)基礎(chǔ)：范數(shù)、正定性代數(shù)基礎(chǔ)：范數(shù)、正定性2 多元函數(shù)分析基礎(chǔ)：多元函數(shù)分析基礎(chǔ)： Hesse矩陣、方向?qū)?shù)、中值公式矩陣、方向?qū)?shù)、中值公式3 多元函數(shù)的極值多元函數(shù)的極值4 等高線等高線5 凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃6 最優(yōu)化算法的結(jié)構(gòu)最優(yōu)化算法的結(jié)構(gòu)Page 2向量范數(shù)定義向量范數(shù)定義12221niixxl2范數(shù)范數(shù)11niixxl1范數(shù)范數(shù)11pnpipixxlp范數(shù)范數(shù)l范數(shù)范數(shù)maxixx12(,)Tnnxx xxR列向量列向量Page 3范數(shù)常見不等式范數(shù)常見不等式xxn xxxn x2121 xxn x2l1-范數(shù)范數(shù)l2

2、 -范數(shù)范數(shù)l范數(shù)范數(shù)相互等價(jià)相互等價(jià)xxx21 Page 4max2()TA AAl2范數(shù)也稱譜范數(shù)范數(shù)也稱譜范數(shù)(ATA最大特征值開平方最大特征值開平方)0maxxAxAx 特別地，方陣有如下范數(shù)特別地，方陣有如下范數(shù)ABA B()ijm nAa 11maxnijjiAal1范數(shù)范數(shù)(列和的最大者列和的最大者 )1maxnijijAal范數(shù)范數(shù)(行和的最大者行和的最大者 )矩陣矩陣范數(shù)范數(shù)Page 5定義：設(shè)定義：設(shè)Q為為 nn 階階對(duì)稱矩陣對(duì)稱矩陣, 若若 ，均有均有 ，則稱則稱 Q 正正定定。 若若 ，均有，均有 ，則稱，則稱Q半正定。半正定。 若若 ，均有，均有 ，則稱，則稱Q負(fù)定。

3、負(fù)定。 若若 , 均有均有 ，則稱，則稱Q半負(fù)定。半負(fù)定。矩陣正定性矩陣正定性Page 6矩陣 Q 半正定 Q 的所有特征根大于等于零; Q 的各階主子式都大于等于零； 存在矩陣G，使得Q=GGT。矩陣 Q 正定 Q 的所有特征根大于零; Q 的各階順序主子式都大于零； Q 的各階主子式都大于零； 存在非奇異矩陣G，使得Q=GGT Page 7矩陣 Q 半負(fù)定 Q 的所有特征根小于等于零; Q 的所有奇數(shù)階主子式都小于等于零，且偶數(shù)階主子式都大于等于零； 存在矩陣G，使得-Q=GGT。矩陣 Q 負(fù)定 Q 的所有特征根小于零; Q 的所有奇數(shù)階順序主子式都小于零，且偶數(shù)階順序主子式都大于零； Q

4、 的所有奇數(shù)階主子式都小于零且偶數(shù)階主子式都大于零； 存在非奇異矩陣G，使得-Q=GGT Page 8對(duì)稱矩陣對(duì)稱矩陣Q Q 的三個(gè)順序主子式依次為的三個(gè)順序主子式依次為631320104Q 判定矩陣是否正定判定矩陣是否正定:631320100,1046330,32矩陣矩陣Q是正定的。是正定的。660,Page 9( ):nf xRR1( )nTiiif xc xbc xbn元函數(shù)：元函數(shù)： n元線性函數(shù)：元線性函數(shù)： n元二次函數(shù)：元二次函數(shù)： n元向量值線性函數(shù)：元向量值線性函數(shù)：11111( )22nnnTTijijiiijif xx Qxc xbq x xc xb11122( )( (

5、 ),.,( )=.,，TmmmmF xf xfxAxdA xdA xdAxdR12.nnxxxRx12.mAAAA12.mddddPage 10 若 滿足 ，則稱 為 Cauchy 序列。i.e. kx,lim0mlm lxxkx0,0,mlNm lNxx 當(dāng)有 收斂 是Cauchy 序列. Cauchy 序列的任一子列都收斂。kxkx設(shè) 為一向量序列，如果則稱序列 依范數(shù)收斂到 ,記為 *limkkxx*lim0kkxxkx*xkxPage 111:nfDRR給定區(qū)域給定區(qū)域 D上的上的 n 元實(shí)值函數(shù)元實(shí)值函數(shù) 12nfxxfxfxxfxx列向量列向量( )f xPage 12 12nf

6、xxfxfxxfxx 11222221121n222222222222 nnnnfxfxfxfxfxxx xx xfxfxfxx xxx xfxfxfxx xx xx( )f x( )f xPage 13 2,( )0Tn nf xb xf xbf x(1)則 21(2),2Tf xx xf xxf xI則 21(3),.2Tf xx Qxf xQxf xQ則 21(4)+,.2TTf xx Qx b x cf xQx bf xQ則Page 14設(shè)設(shè) 在點(diǎn)在點(diǎn) x 處可微處可微, d 為固為固定單位向量，則稱定單位向量，則稱 f(x) 在在x 處沿方向處沿方向 d 的方向?qū)?shù)為的方向?qū)?shù)為0

7、0lim()tfxfxtdfxdt實(shí)數(shù)1:nfRR 1( )( )cos(2)0( ) fxf xdf xddfxdf xxd注：（）若，稱 為在 處的上升方向Page 150 0( )( )=0=0 nfxdf xxdfxf xdRd若，稱 為在 處的下降方向若，則對(duì),有 ( )(3) ( )( )( )( )-( )f xf xxdf xf xf xxdf x在 處增加最快的方向在 處下降最快的方向Page 16由于由于 則函數(shù)在則函數(shù)在 處的最速處的最速下降方向下降方向試求目標(biāo)函數(shù)試求目標(biāo)函數(shù) 在點(diǎn)在點(diǎn) 處的最速下降方處的最速下降方向，并求沿這個(gè)方向移動(dòng)一個(gè)單位長度后新點(diǎn)的目標(biāo)函數(shù)值。向

8、，并求沿這個(gè)方向移動(dòng)一個(gè)單位長度后新點(diǎn)的目標(biāo)函數(shù)值。22121122( ,)34f x xxx xx0(0,1)Tx 12121264,42,f xf xxxxxxx 0(0,1)Tx 02204252514255f xef x 102255055.11151555xxe 112211222634|2 50.735xfxxx xx 1212112001210216444-22 xxxxf xxxxpf xxxf xx此方向上的單位向量此方向上的單位向量新點(diǎn)是新點(diǎn)是Page 17設(shè)設(shè) 二階可導(dǎo)，則在二階可導(dǎo)，則在x* 的鄰域內(nèi)有：的鄰域內(nèi)有：( ):nf xRR( )( *)( *)(*)(*)

9、( *) *(*)(*)TTf xf xfxxxo xxf xf xxxxx2221( )( *)( *)(*)(*)( *)(*)(* )21( *)( *)(*)(*) *(*)(*)2TTTTf xf xfxxxxxf xxxo xxf xfxxxxxf xxxxx0,1Page 181 代數(shù)基礎(chǔ)：范數(shù)、正定性代數(shù)基礎(chǔ)：范數(shù)、正定性2 多元函數(shù)分析基礎(chǔ)：多元函數(shù)分析基礎(chǔ)： Hesse矩陣、方向?qū)?shù)、中值公式矩陣、方向?qū)?shù)、中值公式3 多元函數(shù)的極值多元函數(shù)的極值4 等高線等高線5 凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃6 最優(yōu)化算法的結(jié)構(gòu)最優(yōu)化算法的結(jié)構(gòu)Page

10、 19 對(duì)于一個(gè)極小化問題，我們的目的是求出全局極小點(diǎn)，而全對(duì)于一個(gè)極小化問題，我們的目的是求出全局極小點(diǎn)，而全局極小點(diǎn)不好求，因此我們一般的做法是先求出所有局部極小值局極小點(diǎn)不好求，因此我們一般的做法是先求出所有局部極小值點(diǎn)，再從中找出全局極小點(diǎn)。點(diǎn)，再從中找出全局極小點(diǎn)。 為了求出函數(shù)的局部極小值點(diǎn)，我們需要考察函數(shù)為了求出函數(shù)的局部極小值點(diǎn)，我們需要考察函數(shù) f 在局部在局部極小點(diǎn)處滿足什么條件？反過來，滿足什么條件的點(diǎn)是局部極小極小點(diǎn)處滿足什么條件？反過來，滿足什么條件的點(diǎn)是局部極小點(diǎn)？首先回顧二元函數(shù)的極值條件（高等數(shù)學(xué)），然后推廣到多點(diǎn)？首先回顧二元函數(shù)的極值條件（高等數(shù)學(xué)），然后

11、推廣到多元函數(shù)。元函數(shù)。Page 200000(,)(,)0.f xyf xyxy 2( , ):f x yDRR 設(shè)設(shè) 00,xy(1) 為為D的一個(gè)內(nèi)點(diǎn)的一個(gè)內(nèi)點(diǎn); 00,xy( , )f x y可微可微;(2)在在 00,xy處處, （駐點(diǎn)）（駐點(diǎn)）則在則在( , )f x y的極值點(diǎn)的極值點(diǎn);(3)為為00( , )x y且且注：可微的極值點(diǎn)一定是駐點(diǎn)，注：可微的極值點(diǎn)一定是駐點(diǎn)，反之不一定成立。反之不一定成立。 在在 處梯處梯度為度為 ，但但 只是雙曲拋物面的鞍點(diǎn)，而不只是雙曲拋物面的鞍點(diǎn)，而不是極小點(diǎn)。是極小點(diǎn)。1212,f x xx x*xfx*0,0Tx 0,0(0,0)TfP

12、age 21 (2) 當(dāng)當(dāng) 時(shí)，時(shí)， 不是不是 的極值點(diǎn)，的極值點(diǎn)， 稱為函數(shù)的稱為函數(shù)的鞍點(diǎn)鞍點(diǎn)；(3) 當(dāng)當(dāng) 時(shí)，不能確定，需另行討論。時(shí)，不能確定，需另行討論。2( , ):f x yDRR 設(shè)設(shè) 00,xy(1) 為為D的一個(gè)內(nèi)點(diǎn)的一個(gè)內(nèi)點(diǎn); 00,xy( , )f x y二次連續(xù)可微二次連續(xù)可微; ;(2)在在0000(,)(,)0;f xyf xyxy 00,x y( , )f x y的駐點(diǎn)，即的駐點(diǎn)，即(3)為為 000000,xxxyyyAfxyBfxyCfxy 且且令令則則20ACB (1) 當(dāng)當(dāng) 時(shí)，具有極值時(shí)，具有極值0A 0A 00002000000(,)(,)det,

13、(,)(,)xxxyyxyyfxyfxyACBHxyfxyfxy 00,x y( , )f x y取嚴(yán)格極大值取嚴(yán)格極大值取嚴(yán)格極小值取嚴(yán)格極小值20ACB 20ACB 00(,)xyHesse陣陣負(fù)定負(fù)定Hesse陣陣正定正定Page 22( ):nf xDRR 設(shè)設(shè)(1) x*為為D的一個(gè)內(nèi)點(diǎn)的一個(gè)內(nèi)點(diǎn);*x( )f x可微可微;(2)在在 *0.f x 則則( )f x的極值點(diǎn)的極值點(diǎn);(3)為為*x且且借助一元函數(shù)極值的必要條件，見下頁。借助一元函數(shù)極值的必要條件，見下頁。Page 23 設(shè)設(shè) 是是 的局部極小點(diǎn)，的局部極小點(diǎn)， 為任意單位向量。為任意單位向量。由定義知：由定義知： 當(dāng)

14、當(dāng) , 即即 時(shí)，總有：時(shí)，總有：e*x( )f xt*(, )xteN x0,令令 則則 而而 是是D的內(nèi)點(diǎn)，從的內(nèi)點(diǎn)，從而與之對(duì)應(yīng)的而與之對(duì)應(yīng)的 t=0 是是 的局部極小點(diǎn)。的局部極小點(diǎn)。 由一元函數(shù)極小點(diǎn)必要性條件知由一元函數(shù)極小點(diǎn)必要性條件知 , 而由前述而由前述性質(zhì)知性質(zhì)知 則則 , 由單位向量由單位向量任意性，即知任意性，即知 。*()().f xf xte*( )(),tf xte(0)( ),tt*x( ) t0( )|(0)0tt( )( *),Ttf xtee ( *) 0f x(0)( *)0Tf xe( *)0f x( *)( *)f xef x2( *)( *)( *

15、)0,Tf xf xf x （若（若 ，取，取 ，則，則 矛盾。）矛盾。）Page 24( ):nf xDRR 設(shè)設(shè)(1) x*為為D的一個(gè)內(nèi)點(diǎn)的一個(gè)內(nèi)點(diǎn);(2)*x( )f x二次連續(xù)可微二次連續(xù)可微;在在 *0;fx (3)則則( )f x的的嚴(yán)格局部極小點(diǎn)（嚴(yán)格局部極大點(diǎn)）嚴(yán)格局部極小點(diǎn)（嚴(yán)格局部極大點(diǎn)）。為為*x 2*fx (4)正定（負(fù)定）；正定（負(fù)定）；借助多元函數(shù)的泰勒公式：借助多元函數(shù)的泰勒公式：22221( )( *)( *)(*)(*)( *)(*)(* )21= ( *)(*)( *)(*)(* )2( *)TTTf xf xfxxxxxf xxxo xxf xxxf x

16、xxo xxf x（x 充分接近充分接近 時(shí)）。時(shí)）。*xPage 25P38 2.1 2.3 2.9- 2.14Page 261 代數(shù)基礎(chǔ)：范數(shù)、正定性代數(shù)基礎(chǔ)：范數(shù)、正定性2 多元函數(shù)分析基礎(chǔ)：多元函數(shù)分析基礎(chǔ)： Hesse矩陣、方向?qū)?shù)、中值公式矩陣、方向?qū)?shù)、中值公式3 多元函數(shù)的極值多元函數(shù)的極值4 等高線等高線5 凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃6 最優(yōu)化算法的結(jié)構(gòu)最優(yōu)化算法的結(jié)構(gòu)Page 27uZ=f(x,y) 的圖形是一條曲面。的圖形是一條曲面。uf(x,y)=c 的圖形稱為等高線或等的圖形稱為等高線或等值線。值線。u令令c=c1,c2, 等一系

17、列的值，得等一系列的值，得到一族等高線。到一族等高線。u從等高線族的圖形上大致可以從等高線族的圖形上大致可以看出函數(shù)值的變化情況。（利用看出函數(shù)值的變化情況。（利用二維觀察三維）二維觀察三維）Page 28Page 29性質(zhì)：性質(zhì)：極值點(diǎn)附近，二元函數(shù)的等高線近似于一族同心橢圓極值點(diǎn)附近，二元函數(shù)的等高線近似于一族同心橢圓. .221212TTTf xxf xf xxxf xxf xxf xx * =理由理由: :注：極值點(diǎn)附近，注：極值點(diǎn)附近，二次函數(shù)二次函數(shù) 的等高線就是的等高線就是一族準(zhǔn)確的同心橢圓一族準(zhǔn)確的同心橢圓.極值點(diǎn)正好就是橢圓族的共同中心。因此極值點(diǎn)正好就是橢圓族的共同中心。因

18、此，求二次函數(shù)的極值點(diǎn)問題，從幾何上講，也就是求等值線族的，求二次函數(shù)的極值點(diǎn)問題，從幾何上講，也就是求等值線族的共同中心共同中心 。*1xQb 12TTf xx Qxb xcPage 30展開展開把二次函數(shù)把二次函數(shù) 化為矩陣向量形式并檢驗(yàn)化為矩陣向量形式并檢驗(yàn)Q是否正定，如正定，試用公式是否正定，如正定，試用公式 求這個(gè)函數(shù)的極小點(diǎn)。求這個(gè)函數(shù)的極小點(diǎn)。2221231231 21 312,32345f x x xxxxxxxxxx*1xQ b 12312TTfx x xx Qxb x1112131112321222321232313233331,2gggxxx x xgggxb b bxg

19、ggxx22211 122233 312 1 213 1 323231 1223 3111222g xg xg xg x xg x xg x xbxb xb x631320 ,104Q 45,0b與題中函數(shù)比較各項(xiàng)系數(shù)為：與題中函數(shù)比較各項(xiàng)系數(shù)為：Page 31由前例知由前例知 正定正定,*1812210101042 81223356 710101000 7233101010 xQ b 631320104Q 極小點(diǎn)為極小點(diǎn)為Page 32性質(zhì)：性質(zhì)：若函數(shù)在某點(diǎn)的梯度不為零，則該梯度必與過該點(diǎn)的等若函數(shù)在某點(diǎn)的梯度不為零，則該梯度必與過該點(diǎn)的等值線垂直值線垂直. .（梯度方向也稱法向量）（梯度

20、方向也稱法向量）( , )0,0fff x ycdxdyxyffdx dyxy即，理由理由: :注：梯度所指的方向總是等值線的法方向，并且在注：梯度所指的方向總是等值線的法方向，并且在極大值點(diǎn)處梯度方向指向近似橢圓的中心，而極大值點(diǎn)處梯度方向指向近似橢圓的中心，而在極在極小值點(diǎn)處梯度方向背離近似橢圓的中心。小值點(diǎn)處梯度方向背離近似橢圓的中心。Page 33在三維以上的空間中，使目標(biāo)函數(shù)在三維以上的空間中，使目標(biāo)函數(shù) z=f(x) 取同一常數(shù)取同一常數(shù)值的值的面面 x| f(x)=r, r是常數(shù)是常數(shù) 稱為目標(biāo)函數(shù)稱為目標(biāo)函數(shù) z=f(x) 的等值面。的等值面。 若多元函數(shù)在其極小點(diǎn)處的若多元函

21、數(shù)在其極小點(diǎn)處的 Hesse 陣正定，則它在這陣正定，則它在這個(gè)極小點(diǎn)附近的等值面近似地呈現(xiàn)為同心超橢球面族。個(gè)極小點(diǎn)附近的等值面近似地呈現(xiàn)為同心超橢球面族。2*2*2*2*1( )()() ()()()()21()() ()()()()21()()()()2TTTTTf xf xf xxxxxf xxxo xxf xf xxxxxf xxxf xxxf xxxrPage 34l不同值的等值面之間不相交，因?yàn)槟繕?biāo)函數(shù)是單值函數(shù)；l除了極值點(diǎn)所在的等值面外，不會(huì)在區(qū)域內(nèi)部中斷，因?yàn)槟繕?biāo)函數(shù)是連續(xù)的；l一般地，在極值點(diǎn)附近，等值面（線）近似地呈現(xiàn)為同心橢球面族（橢圓族），因?yàn)樘├展?；l二次函數(shù)的

22、等值面是同心橢球面族，極值點(diǎn)是這個(gè)橢圓球面的共同中心。 l二元函數(shù)，梯度所指的方向總是等值線的法方向，并且在極大值點(diǎn)處梯度方向指向近似橢圓的中心，而在極小值點(diǎn)處梯度方向背離近似橢圓的中心。Page 352x1xff0G 221212min21. .50 xxs txx *3,2Tz ， 2.f z 用圖解法求解用圖解法求解 先畫出目標(biāo)函數(shù)等值線，再畫出約束曲線。先畫出目標(biāo)函數(shù)等值線，再畫出約束曲線。對(duì)應(yīng)的最優(yōu)值為對(duì)應(yīng)的最優(yōu)值為由圖易見約束直線與等值線的切點(diǎn)由圖易見約束直線與等值線的切點(diǎn)是最優(yōu)點(diǎn)，利用解析幾何的方法得是最優(yōu)點(diǎn)，利用解析幾何的方法得該切點(diǎn)為該切點(diǎn)為本處約束曲線是一條直線，這條直本處

23、約束曲線是一條直線，這條直線就是可行域；而最優(yōu)點(diǎn)就是可行線就是可行域；而最優(yōu)點(diǎn)就是可行域上使等值線具有最小值的點(diǎn)域上使等值線具有最小值的點(diǎn). .Page 361 代數(shù)基礎(chǔ)：范數(shù)、正定性代數(shù)基礎(chǔ)：范數(shù)、正定性2 多元函數(shù)分析基礎(chǔ)：多元函數(shù)分析基礎(chǔ)： Hesse矩陣、方向?qū)?shù)、中值公式矩陣、方向?qū)?shù)、中值公式3 多元函數(shù)的極值多元函數(shù)的極值4 等高線等高線5 凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃6 最優(yōu)化算法概述最優(yōu)化算法概述Page 37 若若f(x)在區(qū)間在區(qū)間a,b上是凸的，則上是凸的，則x*是是f(x)的極小值點(diǎn)等價(jià)于的極小值點(diǎn)等價(jià)于x*是是f(x)的最小值。的

24、最小值。 且由微分學(xué)知：若且由微分學(xué)知：若 ，則，則f(x)是凸的。是凸的。( )0fx 設(shè)設(shè)f(x)定義在定義在D內(nèi)，若內(nèi)，若x*為為f(x)的最小值點(diǎn)，則的最小值點(diǎn)，則x*為為f(x)的極小值的極小值點(diǎn)。反過來不一定成立。點(diǎn)。反過來不一定成立。為研究多元函數(shù)的極值與最值的關(guān)系，下面介紹多元函數(shù)凸性。為研究多元函數(shù)的極值與最值的關(guān)系，下面介紹多元函數(shù)凸性。Page 3812,0,1 ,x xD 12(1),0,1,xxD D,nDR空集和單元素集是凸集?？占蛦卧丶峭辜?根據(jù)定義：三角形，矩形，圓，球，凸多邊形，第一象限，第根據(jù)定義：三角形，矩形，圓，球，凸多邊形，第一象限，第一卦限等

25、都是凸集。一卦限等都是凸集。設(shè)設(shè)若集合若集合 中任意兩點(diǎn)的連線都屬于中任意兩點(diǎn)的連線都屬于 ，則稱，則稱 為凸集。為凸集。因?yàn)閮牲c(diǎn)因?yàn)閮牲c(diǎn) 連線上任一點(diǎn)可以表示為連線上任一點(diǎn)可以表示為 12(1) ,0,1.xxx 12,x xDDD凸集的幾何特征凸集的幾何特征凸集的代數(shù)特征凸集的代數(shù)特征稱集合稱集合 為凸集為凸集 。恒有恒有Page 39凸集：在點(diǎn)集中任取兩點(diǎn)，則其連線仍在其中。凸集：在點(diǎn)集中任取兩點(diǎn)，則其連線仍在其中。即沒有凹入的部分；沒有空洞。即沒有凹入的部分；沒有空洞。ABCDPage 400,1 , 1212(1)(1)(1),AxxAxAxbbb12,x xH12,Axb Axb即

26、即12(1),xxH所以所以即即H是凸集。是凸集。,nTHx xRc xb 集合集合是凸集是凸集, 稱為超平面，稱為超平面，c為為n維向量。維向量。鄰域鄰域00,|,0N xx x x 是凸集。是凸集。m nmHx A xb 集合集合是凸集是凸集.Page 41設(shè)設(shè) 那么稱那么稱 是是 的凸組合。的凸組合。 121,.,0,1,mmniiix xxRS 是凸集是凸集 S 中任意有限個(gè)點(diǎn)的凸組合屬于中任意有限個(gè)點(diǎn)的凸組合屬于 S。證明：見書中定理證明：見書中定理 2.9 (P23)。充分性顯然。必要性：歸納法。充分性顯然。必要性：歸納法。1miiix12,.,mx xx設(shè)設(shè) 是凸集，則是凸集，則

27、 也是凸集。也是凸集。,AB AB AB,nA BR: :,: :,.ABab aA bBABa b aA bB 不一定是凸集。不一定是凸集。AB設(shè)設(shè) 是凸集，則是凸集，則 也是凸集。也是凸集。,AB AB AB,nA BR: :,: :,.ABab aA bBABa b aA bB11211211211211111111+.+.kkkkkkkkikkkkiiiiiiixxxxxxxx11(0)kiiPage 42包含集合包含集合D D 的所有凸集的交集的所有凸集的交集, ,稱為稱為D D 的凸包的凸包. .記作記作 Co(DCo(D) ) 或者或者 H(D).H(D).由性質(zhì)由性質(zhì)1 1可知

28、，可知，Co(DCo(D) )是包含是包含D D 的最小凸集。的最小凸集。0nDR0 xDxDD設(shè)設(shè) ，如果對(duì)任意的，如果對(duì)任意的 及所有的及所有的 ， 都有都有 ，則稱，則稱 是一個(gè)錐。一個(gè)同時(shí)是凸集的錐，稱為是一個(gè)錐。一個(gè)同時(shí)是凸集的錐，稱為 凸錐。凸錐。有限個(gè)點(diǎn)的凸包有限個(gè)點(diǎn)的凸包12 ,.,mco x xxPage 43HS2S1設(shè)設(shè) 是非空集合，如果存在向是非空集合，如果存在向量量 及及 ，使得，使得12,nS SR npR aR 則稱超平面則稱超平面 分離分離 和和 。 nTHxRp xa1S2S 12 ,nTnTSHxRp xaSHxRp xa Page 44設(shè)設(shè) 是非空凸集，是

29、非空凸集， ， 則則nSR yS （1 1）存在唯一的）存在唯一的 使得它與使得它與 y 的距離最小，即的距離最小，即xS -inf0 xyxy xS（2 2） 是點(diǎn)是點(diǎn) y 到到 S S 的距離最小的充要條件為的距離最小的充要條件為 0TxxxyxS xS 令令 kxS inf0rxy xS根據(jù)下確界的定義，存在序列根據(jù)下確界的定義，存在序列 使得使得 。下面證它是柯西列即可。下面證它是柯西列即可。kxyrySxPage 45設(shè)設(shè) 是非空凸集，是非空凸集， ，則如果存在唯一的則如果存在唯一的 及及 ，使得，使得nSR yS ,0npRpaR ,TTp xap yxS 即存在超平面即存在超平面

30、 分離分離 y 和和 S。 |nTHxRp xa ylS: -inf0.pyxxxyxy xSPage 46 設(shè)設(shè) 則下列關(guān)系式有且僅有則下列關(guān)系式有且僅有一組有解：一組有解：(1)0,0; (2),0. TTAxc xA yc y,m nnARcR a a2 2a a1 1a am mc ca a1 1a a2 2a am mc c(1)式有解當(dāng)且僅當(dāng)凸錐式有解當(dāng)且僅當(dāng)凸錐x|Ax0與半空間與半空間x|cTx0的交非空的交非空.(2)式有解當(dāng)且僅當(dāng)式有解當(dāng)且僅當(dāng) c 在由在由 A的行向量的行向量a1, a2, , am所生成的凸錐內(nèi)所生成的凸錐內(nèi).Page 47 設(shè)集合設(shè)集合 D Rn 為凸

31、集，函數(shù)為凸集，函數(shù) f :DR, 若若 x, y D, (0 , 1) ，均有，均有 f( x+(1- ) y ) f(x)+(1- )f(y) ，則稱則稱 f(x)為凸集為凸集 D 上的凸函數(shù)。上的凸函數(shù)。u凸函數(shù)：任意兩個(gè)點(diǎn)的凸組合的函數(shù)值小于等于這兩個(gè)點(diǎn)的函凸函數(shù)：任意兩個(gè)點(diǎn)的凸組合的函數(shù)值小于等于這兩個(gè)點(diǎn)的函數(shù)值的凸組合。數(shù)值的凸組合。進(jìn)一步，若有上面不等式以嚴(yán)格不等式成立，則進(jìn)一步，若有上面不等式以嚴(yán)格不等式成立，則稱稱 f(x)為凸集為凸集 上的嚴(yán)格凸函數(shù)。上的嚴(yán)格凸函數(shù)。當(dāng)當(dāng)-f(x)為凸函數(shù)為凸函數(shù)(嚴(yán)格凸嚴(yán)格凸)時(shí)，則稱時(shí)，則稱 f(x)為凹函數(shù)為凹函數(shù)(嚴(yán)格嚴(yán)格凹凹)。P

32、age 48Page 49設(shè)設(shè) f1, f2 是凸集是凸集 D D 上的凸函數(shù)，上的凸函數(shù)，設(shè)設(shè)a, b 0, 則則 af1+bf2 是凸函數(shù)；是凸函數(shù)； f(x)= maxf1(x) , f2 (x) 是凸函數(shù)。是凸函數(shù)。 af1 - bf2 是否是凸函數(shù)？是否是凸函數(shù)？ g(x)= min f1(x) , f2 (x) 是否是凸函數(shù)？是否是凸函數(shù)？ f(x) 為凸集為凸集 S 上的凸函數(shù)上的凸函數(shù) S 上任意有限點(diǎn)的凸組合上任意有限點(diǎn)的凸組合 的函數(shù)值小于等于各點(diǎn)函數(shù)值的凸組合。的函數(shù)值小于等于各點(diǎn)函數(shù)值的凸組合。 參見文中參見文中 P26 定理定理2.10的證明。充分性顯然，必要性用的證

33、明。充分性顯然，必要性用數(shù)學(xué)歸納法。數(shù)學(xué)歸納法。Page 50 設(shè)設(shè)D Rn 為非空凸集，函數(shù)為非空凸集，函數(shù) f :DR 在在 D 上可微，則上可微，則 (1) f 在在D上為凸函數(shù)上為凸函數(shù) 任意任意x，y D，恒有，恒有 f (y) f (x)+ f T(x)(y-x) (1) (2) f 在在D上為嚴(yán)格凸函數(shù)上為嚴(yán)格凸函數(shù) 任意任意xy D，恒有，恒有 f (y) f (x)+ f T(x)(y-x) . (2) 見書中定理見書中定理 2.11 (P27) ，見下一頁。，見下一頁。嚴(yán)格凸函數(shù)嚴(yán)格凸函數(shù)凸函數(shù)凸函數(shù)Page 51設(shè) f(x) 為凸函數(shù)，根據(jù)定義( )(1) ( )(1)

34、)(),(0,1)f yf xfyxf xyxx yD()( )( )- ( )f xyxf xf y f x所以( )- ( )( )() Tf y f xf xyx兩邊取極限得即( )( )+( )()Tf yf xf xyx若 f(x) 嚴(yán)格凸函數(shù)，則有1111( )( )()2222f yf xfyx故有( )( )+( )()Tf yf xf xyx1( )+( )()2Tf xf xyxPage 52設(shè)(1)zxy令( )( )( )()( )(1)( )()TTf xf zf zxzf zf zxy由假設(shè)得一式乘以a，二式乘以1-a，相加得( )( )+( )(),(0,1)Tf

35、 yf xf xyxx yD若 f(x) 嚴(yán)格凸函數(shù)，上述大于等于號(hào)均變成大于號(hào)，即成立。( )( )( )()( )( )() TTf yf zf zyzf zf zxy( )(1) ( )( )(1) )f xf yf zfxyPage 53Page 54 設(shè)設(shè)D Rn 為含內(nèi)點(diǎn)的非空凸集，函數(shù)為含內(nèi)點(diǎn)的非空凸集，函數(shù) f :DR在在 D 上二次可微，則上二次可微，則 a) f 在在 D 上為凸函數(shù)上為凸函數(shù) x D， 2f (x) 半正定；半正定； b) x D， 2f (x) 正定正定 f 在在D上為嚴(yán)格凸函數(shù)上為嚴(yán)格凸函數(shù)（特別注意逆命（特別注意逆命題不成立）題不成立）。21( )=

36、 ( )+()( )+()( )()2( )+()( )TTTf yf xyxf xyxfyxf xyxf x2222()= ( )+( )+( )()2TTf xzf xzf xzf x zoz0令 得，2f (x) 半正定。()( )+( )Tf xzf xzf x222222()( )2()0Tozzf x zzzPage 55設(shè)二次函數(shù)設(shè)二次函數(shù) ，根據(jù)二階條件得，根據(jù)二階條件得 (1) (1) 若若 為半正定矩陣，為半正定矩陣， 在在 中為凸函數(shù)；中為凸函數(shù)； (2) (2) 若若 為正定矩陣，為正定矩陣， 在在 中為嚴(yán)格凸函數(shù)。中為嚴(yán)格凸函數(shù)。判斷判斷 f(x)=5x12-6x1x

37、2+5x22 在凸集在凸集D上是否是凸函數(shù)？上是否是凸函數(shù)？ 的順序主子式都是正的，所以正定，因此的順序主子式都是正的，所以正定，因此f(x)在凸集在凸集D上是嚴(yán)格凸函數(shù)。上是嚴(yán)格凸函數(shù)。 2106( )6 10f x Tf xx AxA( )f xnRnR( )f xAPage 5622211121112(1)()(1)()xxxx221112()()0 xx01,20,使使( *)( )( *)1f xf xxXNx ，（）如果如果x*不是整體最優(yōu)解，則不是整體最優(yōu)解，則又因?yàn)橛忠驗(yàn)閒是凸函數(shù)，所以是凸函數(shù)，所以(1) *)(1) ( *)( *)(1) ( *)( *)2fxxf xf

38、xf xf xf x( (（）xX ，使使( *)( )f xf x，取取0充分?。撼浞中。?(1) *( *),(1*)()*f xxxXfNxxx（），與與（2）2）矛矛盾盾Page 6222121112221212min()44()20()10,0f Xxxxg XxxgXxxx x 2221212222212()() 2 0 ,0 2 f Xffx xxf Xffxxx 解解的的正定，正定，凸函數(shù)凸函數(shù)Page 63221121212122112212222221212222222212()(). 0 0 , 0 0 2 0 0 0 ggx xxg Xggxxxggx xxgXggxx

39、x 所以，該問題為凸規(guī)劃。半正定，半正定，凸函數(shù)凸函數(shù)半正定，半正定，凸函數(shù)凸函數(shù)Page 64 如圖所示，該問題最優(yōu)解（最小點(diǎn)）在x*點(diǎn)取得。8 . 3)()34. 1 58. 0( ) (*2*1*XfxxXTT1x2xo11224*(0.58, 1.34) x0)(1Xg0)(2Xg2( *)3.8f X222212112112221212min()44(2)()20()10,0f Xxxxxxg XxxgXxxx x Page 652221231231 31 21222112321233123min( ,)222. .( )0( )216( )0f x x xxxxx xx xxxst

40、g xxxxg xxxxg xxxxPage 66課后作業(yè)課后作業(yè) Page 671 代數(shù)基礎(chǔ)：范數(shù)、正定性、序列收斂代數(shù)基礎(chǔ)：范數(shù)、正定性、序列收斂2 多元函數(shù)分析基礎(chǔ)：多元函數(shù)分析基礎(chǔ)： Hesse矩陣、方向?qū)?shù)、中值公式矩陣、方向?qū)?shù)、中值公式3 多元函數(shù)的極值多元函數(shù)的極值4 等高線等高線5 凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃凸分析基礎(chǔ)：凸集、凸函數(shù)、凸規(guī)劃6 最優(yōu)化算法的結(jié)構(gòu)最優(yōu)化算法的結(jié)構(gòu)Page 68:nfDRR n元函數(shù)元函數(shù)min( )nx Rf x 求解無約束優(yōu)化問題求解無約束優(yōu)化問題 設(shè) (1) 為 D 的一個(gè)內(nèi)點(diǎn); (2) 在 可微; (3) 為 的極值點(diǎn); 則 。:nf

41、DRR 0f x ( )f xx x x ( )f x設(shè)設(shè) (1) 為為 D 的一個(gè)內(nèi)點(diǎn)的一個(gè)內(nèi)點(diǎn); (2) 在在 二次連續(xù)可微二次連續(xù)可微; (3) ; (4) 正定正定;則則 為為 的嚴(yán)格局部極小點(diǎn)。的嚴(yán)格局部極小點(diǎn)。:nfDRR 2f x ( *)0f x ( )f xx ( )f xx x A. 對(duì)一般對(duì)一般n元函數(shù)，由條件元函數(shù)，由條件 得到一非線得到一非線性方程組，解它相當(dāng)困難。性方程組，解它相當(dāng)困難。B. 對(duì)于不可微函數(shù)，當(dāng)然談不上使用這樣的方法。對(duì)于不可微函數(shù)，當(dāng)然談不上使用這樣的方法。( )0f xI.根據(jù)一階必要條件，令函數(shù)梯度等于零，求得駐點(diǎn)；根據(jù)一階必要條件，令函數(shù)梯度

42、等于零，求得駐點(diǎn)；II.然后用充分條件進(jìn)行判別，求出所要的最優(yōu)解。然后用充分條件進(jìn)行判別，求出所要的最優(yōu)解。Page 69大致想法：大致想法：為了求為了求函數(shù)函數(shù) f(x) 的最優(yōu)解，的最優(yōu)解，u首先給定一個(gè)初始估計(jì)首先給定一個(gè)初始估計(jì)u然后按某種規(guī)則然后按某種規(guī)則( (即算法即算法) )找出比找出比 更好的解更好的解u再按此種規(guī)則找出比再按此種規(guī)則找出比 更好的解更好的解u如此即可得到一個(gè)解的序列如此即可得到一個(gè)解的序列0 x0 x1x，1x10( )( )f xf x221()()xf xf x，.kxu若這個(gè)解序列收斂于該問題的最優(yōu)解若這個(gè)解序列收斂于該問題的最優(yōu)解x*，則算法有效。，則

43、算法有效。min( )nx Rf x 無約束優(yōu)化問題無約束優(yōu)化問題 (P1)min( ). .( )0 (1,2,)if xs tg xim 約束優(yōu)化問題約束優(yōu)化問題問題問題 (P2)Page 701kkkkxxd：可行可行方向、下降方向方向、下降方向希望找到迭代序列希望找到迭代序列xk，其迭代格式為，其迭代格式為（可行方向可行方向）設(shè)）設(shè) D 為可行域，在點(diǎn)為可行域，在點(diǎn) 處，對(duì)于非零向量處，對(duì)于非零向量 d ，若存在實(shí)數(shù)，若存在實(shí)數(shù) ，使得，使得 ， 則稱則稱 d 為為 f(x) 在在 點(diǎn)的可行方向。點(diǎn)的可行方向。_x_,(0,)xdD0_xxkxk+1dkakPage 71注：注：根據(jù)泰勒公式根據(jù)泰勒公式即即()( )( )(