凸集和凸函數(shù)和凸規(guī)劃

關(guān)于凸集和凸函數(shù)和凸規(guī)劃第一頁，共五十頁，2022年，8月28日凸集---定義線性組合(linearCombination)仿射組合(AffineCombination)凸組合(ConvexCombination)凸錐組合(ConvexConeCombination)第二頁，共五十頁，2022年，8月28日凸集---定義例

二維情況下，兩點x1,x2的(a)線性組合為全平面；(b)仿射組合為過這兩點的直線；(c)凸組合為連接這兩點的線段；(b)凸錐組合為以原點為錐頂并通過這兩點的錐.第三頁，共五十頁，2022年，8月28日凸集---定義第四頁，共五十頁，2022年，8月28日凸集---定義定義1設(shè)集合若對于任意兩點及實數(shù)都有：則稱集合為凸集．常見的凸集：單點集{x}，空集

，整個歐氏空間Rn，超平面：半空間：第五頁，共五十頁，2022年，8月28日例：證明超球為凸集．證明：設(shè)為超球中的任意兩點，則有：即點屬于超球,所以超球為凸集．凸集----舉例第六頁，共五十頁，2022年，8月28日(1)任意多個凸集的交集為凸集．

(2)設(shè)是凸集，是一實數(shù)，則下面的集合是凸集：凸集-----性質(zhì)(3)第七頁，共五十頁，2022年，8月28日推論：設(shè)是凸集，則也是凸集，其中是實數(shù)．

(4)

S是凸集當(dāng)且僅當(dāng)S中任意有限個點的凸組合仍然在S中.P23,定理2.9凸集-----性質(zhì)第八頁，共五十頁，2022年，8月28日注：和集和并集有很大的區(qū)別，凸集的并集未必是凸集，而凸集的和集是凸集．例：表示軸上的點．表示軸上的點．則表示兩個軸的所有點，它不是凸集；而凸集．凸集-----性質(zhì)第九頁，共五十頁，2022年，8月28日定義設(shè)S中任意有限個點的所有凸組合所構(gòu)成的集合稱為S的凸包，記為H(S),即凸集-----凸包(ConvexHull)

H(S)是Rn

中所有包含S的凸集的交集.H(S)是包含S的最小凸集.第十頁，共五十頁，2022年，8月28日定義錐、凸錐凸集-----凸錐(ConvexCone)第十一頁，共五十頁，2022年，8月28日定義分離(Separation)凸集-----凸集分離定理第十二頁，共五十頁，2022年，8月28日性質(zhì)凸集-----凸集分離定理(2)是點到集合的最短距離點的充要條件為：注：閉凸集外一點與閉凸集的極小距離，即投影定理。第十三頁，共五十頁，2022年，8月28日定理2.1.5直觀解釋我們不妨把一個閉凸集想象為一個三維的充滿了氣體的氣球（不一定為標(biāo)準球形，但必須是凸的），那么，在氣球外一點，到氣球各點（包括內(nèi)部）的距離是不一樣的，但直覺告訴我們，肯定在氣球上有一點，它到該點的距離是所有距離中最小的。這是凸集的特有性質(zhì)。如果不是凸集，就不會這樣了，比如一個平面上對稱心形的圖形（它不是凸的）外一點，至少可以找到2點，使其到外面那一點的距離最小。凸集-----凸集分離定理第十四頁，共五十頁，2022年，8月28日凸集分離定理凸集-----凸集分離定理ylS點與閉凸集的分離定理第十五頁，共五十頁，2022年，8月28日凸集分離定理應(yīng)用---Farkas引理凸集-----凸集分離定理應(yīng)用Farkas引理在我們即將學(xué)習(xí)的最優(yōu)性條件中是重要的基礎(chǔ).第十六頁，共五十頁，2022年，8月28日Farkas引理–幾何解釋設(shè)A的第i個行向量為ai,i=1,2,…,m,則(2.1.4)式有解當(dāng)且僅當(dāng)凸錐{x|Ax≤0}與半空間{x|bTx>0}的交不空.即(2.1.4)式有解當(dāng)且僅當(dāng)存在向量x,它與各ai的夾角鈍角或直角，而與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)有解第十七頁，共五十頁，2022年，8月28日凸集分離定理應(yīng)用---Gordan定理凸集-----凸集分離定理應(yīng)用利用Farkas引理可推導(dǎo)下述的Gordan定理和擇一性定理.凸集分離定理應(yīng)用---擇一性定理第十八頁，共五十頁，2022年，8月28日凸函數(shù)凸函數(shù)(ConvexFunction)----定義2.4設(shè)是非空凸集，若對任意的及任意的都有：則稱函數(shù)為上的凸函數(shù)．注：將上述定義中的不等式反向，可以得到凹函數(shù)的定義．第十九頁，共五十頁，2022年，8月28日凸函數(shù)嚴格凸函數(shù)設(shè)是非空凸集，若對任意的及任意的都有：則稱函數(shù)為上的嚴格凸函數(shù)．注：將上述定義中的不等式反向，可以得到嚴格凹函數(shù)的定義．第二十頁，共五十頁，2022年，8月28日凸函數(shù)

對一元函數(shù)在幾何上表示連接的線段．所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點的線段總是位于曲線弧的上方．幾何性質(zhì)表示在點處的函數(shù)值．

第二十一頁，共五十頁，2022年，8月28日f(X)Xf(X1)f(X2)

X1X2第二十二頁，共五十頁，2022年，8月28日f(X)Xf(X1)f(X2)

X1X2αx1+(1-α)x2f(αx1+(1-α)x2)第二十三頁，共五十頁，2022年，8月28日f(X)Xαf(x1)

+(1-α)f(x2)f(X1)f(X2)

X1X2αx1+(1-α)x2f(αx1+(1-α)x2)第二十四頁，共五十頁，2022年，8月28日f(X)Xf(X1)f(X2)

X1X2任意兩點的函數(shù)值的連線上的點都在曲線的上方αx1+(1-α)x2f(αx1+(1-α)x2)αf(x1)

+(1-α)f(x2)第二十五頁，共五十頁，2022年，8月28日(a)凸函數(shù)(b)凹函數(shù)該定義的一個應(yīng)用——證明不等式例：證明Young不等式推廣：H?lder不等式P412.37證法：在Young不等式中令第二十六頁，共五十頁，2022年，8月28日例：設(shè)試證明在上是嚴格凸函數(shù)．證明:設(shè)且都有：因此,在上是嚴格凸函數(shù)．凸函數(shù)第二十七頁，共五十頁，2022年，8月28日例：試證線性函數(shù)是上的凸函數(shù)．證明:設(shè)則故,是凸函數(shù)．類似可以證明也是凹函數(shù).凸函數(shù)第二十八頁，共五十頁，2022年，8月28日凸函數(shù)定理1設(shè)是凸集上的凸函數(shù)充要條件性質(zhì)詹生(Jensen)不等式不等式應(yīng)用:設(shè)，證明:P412.36第二十九頁，共五十頁，2022年，8月28日凸函數(shù)定理2性質(zhì)正線性組合第三十頁，共五十頁，2022年，8月28日凸函數(shù)定理3設(shè)是凸集上的凸函數(shù)，則對任意，水平集是凸集．水平集(LevelSet)稱為函數(shù)f在集合S上關(guān)于數(shù)的水平集.注：定理3的逆命題不成立.第三十一頁，共五十頁，2022年，8月28日下面的圖形給出了凸函數(shù)的等值線的圖形，可以看出水平集是凸集.凸函數(shù)第三十二頁，共五十頁，2022年，8月28日凸函數(shù)第三十三頁，共五十頁，2022年，8月28日定理1:設(shè)是定義在凸集上，令則:(1)是定義在凸集是凸集上的凸函數(shù)的充要條件是對任意的一元函數(shù)為上的凸函數(shù).(2)設(shè)若在上為嚴格凸函數(shù)，則在上為嚴格凸函數(shù)．凸函數(shù)凸函數(shù)的判別定理第三十四頁，共五十頁，2022年，8月28日該定理的幾何意義是：凸函數(shù)上任意兩點之間的部分是一段向下凸的?。购瘮?shù)第三十五頁，共五十頁，2022年，8月28日定理4設(shè)在凸集上可微，則：在上為凸函數(shù)的充要條件是對任意的都有：嚴格凸函數(shù)(充要條件)??凸函數(shù)凸函數(shù)的判別定理---一階條件注：定理4提供了一個判別可微函數(shù)是否為凸

函數(shù)的依據(jù).第三十六頁，共五十頁，2022年，8月28日凸函數(shù)定理4-----

幾何

解釋一個可微函數(shù)

是凸函數(shù)當(dāng)且

僅當(dāng)函數(shù)圖形

上任一點處的

切平面位于曲

面的下方.第三十七頁，共五十頁，2022年，8月28日凸函數(shù)定理4-----

幾何

解釋一個可微函數(shù)

是凸函數(shù)當(dāng)且

僅當(dāng)函數(shù)圖形

上任一點處的

切平面位于曲

面的下方.第三十八頁，共五十頁，2022年，8月28日定理5:設(shè)在開凸集內(nèi)二階可微,則是內(nèi)的凸函數(shù)的充要條件為:對任意的Hesse矩陣半正定,其中：凸函數(shù)凸函數(shù)的判別定理---二階條件第三十九頁，共五十頁，2022年，8月28日定理2.3.6:設(shè)在開凸集內(nèi)二階可微,若在內(nèi)正定,則在內(nèi)是嚴格凸函數(shù)．注:反之不成立．例：f(x)是嚴格凸的，但在點處不是正定的凸函數(shù)凸函數(shù)的判別定理---二階條件第四十頁，共五十頁，2022年，8月28日例：凸函數(shù)凸函數(shù)的判別定理---二階條件第四十一頁，共五十頁，2022年，8月28日凸規(guī)劃凸規(guī)劃(ConvexProgramming)設(shè)為凸集，為上的凸函數(shù)，則稱規(guī)劃問題為凸規(guī)劃問題．例：為上的凸函數(shù)，為無約束凸規(guī)劃問題．例：凸規(guī)劃第四十二頁，共五十頁，2022年，8月28日凸規(guī)劃例：第四十三頁，共五十頁，2022年，8月28日凸規(guī)劃定理2.4(1)凸規(guī)劃問題的任一局部極小點是全局極小點，且全體極小點的集合為凸集．(2)若是凸集上的嚴格凸函數(shù)，且凸規(guī)劃問題局部極小點x*存在，則x*是唯一的全局極小點．凸規(guī)劃的基本性質(zhì)第四十四頁，共五十頁，2022年，8月28日定理凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。證明：設(shè)x*是凸規(guī)劃的一個局部解，則存在δ>0,使如果x*不是整體最優(yōu)解，則又因為f是凸函數(shù)，所以取α>0充分小，有第四十五頁，共五十頁，202