凸優(yōu)化理論與應(yīng)用凸集PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1凸優(yōu)化理論與應(yīng)用凸集凸優(yōu)化理論與應(yīng)用凸集信息與通信工程學(xué)院 莊伯金 212(1), .yxxR .線段的表示：線段的表示：12(1), 0,1.yxx.仿射集的定義：過集合仿射集的定義：過集合C內(nèi)任意兩點(diǎn)的直線均在集合內(nèi)任意兩點(diǎn)的直線均在集合C內(nèi)，則稱集合內(nèi)，則稱集合C為仿射集。為仿射集。仿射集的例：直線、平面、超平面仿射集的例：直線、平面、超平面Axb第1頁/共37頁信息與通信工程學(xué)院 莊伯金 3aff |,1iiiiCxxC仿射維數(shù)：仿射包的維數(shù)。仿射維數(shù)：仿射包的維數(shù)。相對內(nèi)點(diǎn)（相對內(nèi)點(diǎn)（relative interior）：）：relint |( , )aff,0Cx B x

2、rCC r第2頁/共37頁信息與通信工程學(xué)院 莊伯金 4第3頁/共37頁信息與通信工程學(xué)院 莊伯金 51212,0,1,(1)x xCxxC則111,.,0,11,kkiiikiiixxCxC且 則第4頁/共37頁信息與通信工程學(xué)院 莊伯金 6第5頁/共37頁信息與通信工程學(xué)院 莊伯金 71212,0,1,(1)x xCxxC則所以仿射集一定是凸集第6頁/共37頁信息與通信工程學(xué)院 莊伯金 8第7頁/共37頁信息與通信工程學(xué)院 莊伯金 9第8頁/共37頁信息與通信工程學(xué)院 莊伯金 1011conv |,0,1kkiiiiiiiCxxC第9頁/共37頁信息與通信工程學(xué)院 莊伯金 11第10頁/共

3、37頁信息與通信工程學(xué)院 莊伯金 12,0,.xCxC 則有凸錐的定義：集合凸錐的定義：集合C既是凸集又是錐。既是凸集又是錐。12121 122,0,.x xCxxC 則有錐包的定義：集合錐包的定義：集合C內(nèi)點(diǎn)的所有錐組合。內(nèi)點(diǎn)的所有錐組合。1|,0kiiiiixxC第11頁/共37頁信息與通信工程學(xué)院 莊伯金 13第12頁/共37頁信息與通信工程學(xué)院 莊伯金 14第13頁/共37頁信息與通信工程學(xué)院 莊伯金 15 |Tx a xb半空間半空間(Halfspace)： |Tx a xb |Tx a xb第14頁/共37頁信息與通信工程學(xué)院 莊伯金 16第15頁/共37頁信息與通信工程學(xué)院 莊伯

4、金 17第16頁/共37頁信息與通信工程學(xué)院 莊伯金 1822(, ) | |() ()ccTccB x rxxxrxxxxxr橢球橢球(ellipsoid):12 |()(), TccExxxPxxrP為對稱正定矩陣第17頁/共37頁信息與通信工程學(xué)院 莊伯金 19第18頁/共37頁信息與通信工程學(xué)院 莊伯金 200,00;| |,xxxtxtx txyxy當(dāng)且僅當(dāng)；R ;范數(shù)球范數(shù)球(norm ball)：(, ) |ccB x rxxxr范數(shù)錐范數(shù)錐(norm cone)：( , )|x txt第19頁/共37頁信息與通信工程學(xué)院 莊伯金 21 |,TTjjiiPx a xb c xd單

5、純形單純形(simplex)：10000|0,1,.,kki iiikiivvvvv線性無關(guān)第20頁/共37頁信息與通信工程學(xué)院 莊伯金 22第21頁/共37頁信息與通信工程學(xué)院 莊伯金 23|nn nTSXXXnRn階半正定矩陣集：階半正定矩陣集：|0nnSXSXn階正定矩陣集：階正定矩陣集：|0nnSXSXn階半正定矩陣集階半正定矩陣集為凸錐！為凸錐！第22頁/共37頁信息與通信工程學(xué)院 莊伯金 24( , )/ ,nP z tz t ztRR線性分式函數(shù)線性分式函數(shù)(linear-fractional function)( )()/(),0Tm nmnTf xAxbc xdAbcdc x

6、dRRRR第23頁/共37頁信息與通信工程學(xué)院 莊伯金 25真錐的定義：錐真錐的定義：錐 滿足如下條件滿足如下條件nKR1.4.KKKK為凸集；2. 為閉集；3. 非中空；有端點(diǎn)。K具有內(nèi)點(diǎn)具有內(nèi)點(diǎn)K內(nèi)不含直線內(nèi)不含直線第24頁/共37頁信息與通信工程學(xué)院 莊伯金 26真錐真錐 下的下的偏序關(guān)系偏序關(guān)系：KKxyyxK intKxyyxK 例：例：逐項(xiàng)不等式逐項(xiàng)不等式矩陣不等式矩陣不等式廣義不等式廣義不等式嚴(yán)格廣義不等嚴(yán)格廣義不等式式第25頁/共37頁信息與通信工程學(xué)院 莊伯金 271.;2.,;3.,;4.,;5.,0;6.,lim,lim.KKKKKKKKKKKiKiiiKxxxy yxx

7、yxy yzxzxy uvxuyvxyxyxyxxyyxy第26頁/共37頁信息與通信工程學(xué)院 莊伯金 281.;2.;3.,;4.,05.,.KKKKKKKKKKxyxyxxxy uvxuyvxyxyxy uxuy足夠小第27頁/共37頁信息與通信工程學(xué)院 莊伯金 29最小元的定義：設(shè)最小元的定義：設(shè) ，對，對 ，都有，都有 成立，則稱成立，則稱 為為 的最小元。的最小元。xSyS KxyxS極小元的定義：設(shè)極小元的定義：設(shè) ，對于，對于 ，若，若 ，則，則 成立，則稱成立，則稱 為為 的極小元。的極小元。xSySKyxxSyx第28頁/共37頁信息與通信工程學(xué)院 莊伯金 30定理：設(shè)定理：

8、設(shè) 和和 為兩不相交凸集，則存在超平面將為兩不相交凸集，則存在超平面將 和和 分離。即：分離。即：,.TTxC a xbxD a xb 且CDCD第29頁/共37頁信息與通信工程學(xué)院 莊伯金 31定義：設(shè)集合定義：設(shè)集合 ， 為為 邊界上的點(diǎn)。若存在邊界上的點(diǎn)。若存在 ，滿，滿足對任意足對任意 ，都有，都有 成立，則稱超平面成立，則稱超平面 為集合為集合 在點(diǎn)在點(diǎn) 處的支撐超平面。處的支撐超平面。C0 xC0a xC0TTa xa x0 |TTx a xa xC0 x定理：凸集邊界上任意一點(diǎn)均存在支撐超平面。定理：凸集邊界上任意一點(diǎn)均存在支撐超平面。定理：若一個(gè)閉的非中空集合，在邊界上的任意一

9、點(diǎn)定理：若一個(gè)閉的非中空集合，在邊界上的任意一點(diǎn)存在支撐超平面，則該集合為凸集。存在支撐超平面，則該集合為凸集。第30頁/共37頁信息與通信工程學(xué)院 莊伯金 32對偶錐的定義：設(shè)對偶錐的定義：設(shè) 為錐，則集合為錐，則集合 稱為對偶錐。稱為對偶錐。K* |0,TKy x yxK 對偶錐的性質(zhì)：對偶錐的性質(zhì)：*1.3.KKKKKKK是閉凸集；2若 非中空，則有端點(diǎn)；若 的閉包有端點(diǎn)，則非中空；4.是 的閉凸包；真錐的對偶錐仍真錐的對偶錐仍然是真錐！然是真錐！第31頁/共37頁信息與通信工程學(xué)院 莊伯金 33廣義不等式與對偶等價(jià)性質(zhì)廣義不等式與對偶等價(jià)性質(zhì)*,for all 0;,for all 0,0.TTKKTTKKxyxyxyxy最小元的對偶特性：最小元的對偶特性：*0, ,.TKxSKxz zS為集合 中關(guān)于 偏序的最小元對所有為使最小的值第32頁/共37頁信息與通信工程學(xué)院 莊