資源描述:
《凸集、凸函數(shù)、凸規(guī)劃》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第3講凸集、凸函數(shù)、凸規(guī)劃凸集(ConvexSet)凸函數(shù)(ConvexFunction)凸規(guī)劃(ConvexProgramming)凸性(Convexity)是最優(yōu)化理論必須涉及到基本概念.具有凸性的非線性規(guī)劃模型是一類特殊的重要模型,它在最優(yōu)化的理論證明及算法研究中具有非常重要的作用.凸集---定義線性組合(linearCombination)仿射組合(AffineCombination)凸組合(ConvexCombination)凸錐組合(ConvexConeCombination)凸集---定義例二維情況下
2、,兩點(diǎn)x1,x2的(a)線性組合為全平面;(b)仿射組合為過這兩點(diǎn)的直線;(c)凸組合為連接這兩點(diǎn)的線段;(b)凸錐組合為以原點(diǎn)為錐頂并通過這兩點(diǎn)的錐.凸集---定義凸集---定義定義1設(shè)集合若對于任意兩點(diǎn)及實(shí)數(shù)都有:則稱集合為凸集.常見的凸集:單點(diǎn)集{x},空集?,整個(gè)歐氏空間Rn,超平面:半空間:例:證明超球?yàn)橥辜C明:設(shè)為超球中的任意兩點(diǎn),則有:即點(diǎn)屬于超球,所以超球?yàn)橥辜辜?---舉例(1)任意多個(gè)凸集的交集為凸集.(2)設(shè)是凸集,是一實(shí)數(shù),則下面的集合是凸集:凸集-----性質(zhì)(3)推論:設(shè)是凸集,
3、則也是凸集,其中是實(shí)數(shù).(4)S是凸集當(dāng)且僅當(dāng)S中任意有限個(gè)點(diǎn)的凸組合仍然在S中.凸集-----性質(zhì)注:和集和并集有很大的區(qū)別,凸集的并集未必是凸集,而凸集的和集是凸集.例:表示軸上的點(diǎn).表示軸上的點(diǎn).則表示兩個(gè)軸的所有點(diǎn),它不是凸集;而凸集.凸集-----性質(zhì)定義設(shè)S中任意有限個(gè)點(diǎn)的所有凸組合所構(gòu)成的集合稱為S的凸包,記為H(S),即凸集-----凸包(ConvexHull)定理2.1.4H(S)是Rn中所有包含S的凸集的交集.H(S)是包含S的最小凸集.定義錐、凸錐凸集-----凸錐(ConvexCone)定義
4、分離(Separation)凸集-----凸集分離定理性質(zhì)定理2.1.5凸集-----凸集分離定理(2)是點(diǎn)到集合的最短距離點(diǎn)的充要條件為:注:閉凸集外一點(diǎn)與閉凸集的極小距離,即投影定理。定理2.1.5直觀解釋我們不妨把一個(gè)閉凸集想象為一個(gè)三維的充滿了氣體的氣球(不一定為標(biāo)準(zhǔn)球形,但必須是凸的),那么,在氣球外一點(diǎn),到氣球各點(diǎn)(包括內(nèi)部)的距離是不一樣的,但直覺告訴我們,肯定在氣球上有一點(diǎn),它到該點(diǎn)的距離是所有距離中最小的。這是凸集的特有性質(zhì)。如果不是凸集,就不會這樣了,比如一個(gè)平面上對稱心形的圖形(它不是凸的)外
5、一點(diǎn),至少可以找到2點(diǎn),使其到外面那一點(diǎn)的距離最小。凸集-----凸集分離定理凸集分離定理定理2.1.6凸集-----凸集分離定理ylS點(diǎn)與閉凸集的分離定理凸集分離定理應(yīng)用---Farkas引理定理2.1.7凸集-----凸集分離定理應(yīng)用Farkas引理在我們即將學(xué)習(xí)的最優(yōu)性條件中是重要的基礎(chǔ).Farkas引理–幾何解釋設(shè)A的第i個(gè)行向量為ai,i=1,2,…,m,則(2.1.4)式有解當(dāng)且僅當(dāng)凸錐{x
6、Ax≤0}與半空間{x
7、bTx>0}的交不空.即(2.1.4)式有解當(dāng)且僅當(dāng)存在向量x,它與各ai的夾角鈍角或直
8、角,而與b的夾角為銳角.(2.1.5)式有解當(dāng)且僅當(dāng)b在由a1,a2,…,am所生成的凸錐內(nèi).a2(2.1.4)有解,(2.1.5)無解a1amb凸集-----凸集分離定理應(yīng)用a1a2amb(2.1.4)無解,(2.1.5)有解凸集分離定理應(yīng)用---Gordan定理定理2.1.8凸集-----凸集分離定理應(yīng)用利用Farkas引理可推導(dǎo)下述的Gordan定理和擇一性定理.凸集分離定理應(yīng)用---擇一性定理定理2.1.9凸函數(shù)凸函數(shù)(ConvexFunction)----定義2.4設(shè)是非空凸集,若對任意的及任意的都有:則
9、稱函數(shù)為上的凸函數(shù).注:將上述定義中的不等式反向,可以得到凹函數(shù)的定義.凸函數(shù)嚴(yán)格凸函數(shù)設(shè)是非空凸集,若對任意的及任意的都有:則稱函數(shù)為上的嚴(yán)格凸函數(shù).注:將上述定義中的不等式反向,可以得到嚴(yán)格凹函數(shù)的定義.凸函數(shù)對一元函數(shù)在幾何上表示連接的線段.所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點(diǎn)的線段總是位于曲線弧的上方.幾何性質(zhì)表示在點(diǎn)處的函數(shù)值.f(X)Xf(X1)f(X2)X1X2f(X)Xf(X1)f(X2)X1X2αx1+(1-α)x2f(αx1+(1-α)x2)f(X)Xf(X1)f(X2)X1X2αx1+(1
10、-α)x2f(αx1+(1-α)x2)f(X)Xαf(x1)+(1-α)f(x2)f(X1)f(X2)X1X2αx1+(1-α)x2f(αx1+(1-α)x2)f(X)Xf(X1)f(X2)X1X2任意兩點(diǎn)的函數(shù)值的連線上的點(diǎn)都在曲線的上方αx1+(1-α)x2f(αx1+(1-α)x2)αf(x1)+(1-α)f(x2)例4.2.1(a)凸函數(shù)(b)凹函數(shù)