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

1、關(guān)于凸集和凸函數(shù)和凸規(guī)劃第一張，PPT共五十頁，創(chuàng)作于2022年6月凸集-定義線性組合 (linear Combination)仿射組合 (Affine Combination)凸組合 (Convex Combination)凸錐組合 (Convex Cone Combination)第二張，PPT共五十頁，創(chuàng)作于2022年6月凸集-定義例 二維情況下，兩點(diǎn)x1, x2的 (a)線性組合為全平面； (b)仿射組合為過這兩點(diǎn)的直線； (c)凸組合為連接這兩點(diǎn)的線段； (b)凸錐組合為以原點(diǎn)為錐頂并通過這兩點(diǎn)的錐.第三張，PPT共五十頁，創(chuàng)作于2022年6月凸集-定義第四張，PPT共五十頁，創(chuàng)作于

2、2022年6月凸集-定義定義1設(shè)集合若對(duì)于任意兩點(diǎn)及實(shí)數(shù)都有：則稱集合為凸集常見的凸集：?jiǎn)吸c(diǎn)集 x ，空集 ，整個(gè)歐氏空間 Rn，超平面：半空間：第五張，PPT共五十頁，創(chuàng)作于2022年6月例：證明超球?yàn)橥辜C明：設(shè)為超球中的任意兩點(diǎn)，則有：即點(diǎn)屬于超球,所以超球?yàn)橥辜辜?舉例第六張，PPT共五十頁，創(chuàng)作于2022年6月 (1)任意多個(gè)凸集的交集為凸集 (2)設(shè)是凸集，是一實(shí)數(shù)，則下面的集合是凸集：凸集-性質(zhì)(3)第七張，PPT共五十頁，創(chuàng)作于2022年6月推論：設(shè)是凸集，則也是凸集，其中是實(shí)數(shù) (4) S 是凸集當(dāng)且僅當(dāng)S中任意有限個(gè)點(diǎn)的凸 組合仍然在S中.P23,定理2.9凸集-性質(zhì)第八

3、張，PPT共五十頁，創(chuàng)作于2022年6月注：和集和并集有很大的區(qū)別，凸集的并集未必是凸集，而凸集的和集是凸集例：表示軸上的點(diǎn)表示軸上的點(diǎn)則表示兩個(gè)軸的所有點(diǎn)，它不是凸集；而凸集凸集-性質(zhì)第九張，PPT共五十頁，創(chuàng)作于2022年6月定義 設(shè) S 中任意有限個(gè)點(diǎn)的所有凸組合所構(gòu)成的集合稱為S的凸包，記為H(S),即凸集-凸包(Convex Hull)定理2.1.4 H(S)是Rn 中所有包含S 的凸集的交集.H(S)是包含S 的最小凸集.第十張，PPT共五十頁，創(chuàng)作于2022年6月定義 錐、凸錐凸集-凸錐 (Convex Cone)第十一張，PPT共五十頁，創(chuàng)作于2022年6月定義 分離 (Sep

4、aration)凸集-凸集分離定理第十二張，PPT共五十頁，創(chuàng)作于2022年6月性質(zhì) 定理2.1.5凸集-凸集分離定理 (2)是點(diǎn)到集合的最短距離點(diǎn)的充要條件為：注：閉凸集外一點(diǎn)與閉凸集的極小距離，即投影定理。第十三張，PPT共五十頁，創(chuàng)作于2022年6月定理2.1.5 直觀解釋 我們不妨把一個(gè)閉凸集想象為一個(gè)三維的充滿了氣體的氣球（不一定為標(biāo)準(zhǔn)球形，但必須是凸的），那么，在氣球外一點(diǎn)，到氣球各點(diǎn)（包括內(nèi)部）的距離是不一樣的，但直覺告訴我們，肯定在氣球上有一點(diǎn)，它到該點(diǎn)的距離是所有距離中最小的。這是凸集的特有性質(zhì)。如果不是凸集，就不會(huì)這樣了，比如一個(gè)平面上對(duì)稱心形的圖形（它不是凸的）外一點(diǎn)，至

5、少可以找到2點(diǎn)，使其到外面那一點(diǎn)的距離最小。凸集-凸集分離定理第十四張，PPT共五十頁，創(chuàng)作于2022年6月凸集分離定理 定理2.1.6凸集-凸集分離定理ylS點(diǎn)與閉凸集的分離定理第十五張，PPT共五十頁，創(chuàng)作于2022年6月凸集分離定理應(yīng)用-Farkas引理 定理2.1.7凸集-凸集分離定理應(yīng)用Farkas引理在我們即將學(xué)習(xí)的最優(yōu)性條件中是重要的基礎(chǔ).第十六張，PPT共五十頁，創(chuàng)作于2022年6月Farkas引理 幾何解釋 設(shè)A的第i個(gè)行向量為ai,i=1,2,m,則(2.1.4)式有解當(dāng)且僅當(dāng)凸錐x|Ax0與半空間x|bTx0的交不空.即(2.1.4)式有解當(dāng)且僅當(dāng)存在向量x,它與各ai的

6、夾角鈍角或直角，而與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)有解第十七張，PPT共五十頁，創(chuàng)作于2022年6月凸集分離定理應(yīng)用-Gordan 定理 定理2.1.8凸集-凸集分離定理應(yīng)用利用Farkas引理可推導(dǎo)下述的Gordan定理和擇一性定理.凸集分離定理應(yīng)用-擇一性定理 定理2.1.9第十八張，PPT共五十頁，創(chuàng)作于2022年6月凸函數(shù)凸函數(shù)(Convex Function) -定義2.4設(shè)是非空凸集，若對(duì)任意的及任

7、意的都有：則稱函數(shù)為上的凸函數(shù)注：將上述定義中的不等式反向，可以得到凹函數(shù)的定義第十九張，PPT共五十頁，創(chuàng)作于2022年6月凸函數(shù)嚴(yán)格凸函數(shù)設(shè)是非空凸集，若對(duì)任意的及任意的都有：則稱函數(shù)為上的嚴(yán)格凸函數(shù)注：將上述定義中的不等式反向，可以得到嚴(yán)格凹函數(shù)的定義第二十張，PPT共五十頁，創(chuàng)作于2022年6月凸函數(shù) 對(duì)一元函數(shù)在幾何上表示連接的線段所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點(diǎn)的線段總是位于曲線弧的上方幾何性質(zhì)表示在點(diǎn)處的函數(shù)值 第二十一張，PPT共五十頁，創(chuàng)作于2022年6月f(X)Xf(X1)f(X2) X1X2第二十二張，PPT共五十頁，創(chuàng)作于2022年6月f(X)Xf(X1)f(X

8、2) X1X2x1+(1-)x2f(x1+(1-)x2 )第二十三張，PPT共五十頁，創(chuàng)作于2022年6月f(X)Xf( x1 ) +(1- ) f( x2)f(X1)f(X2) X1X2x1+(1-)x2f(x1+(1-)x2 )第二十四張，PPT共五十頁，創(chuàng)作于2022年6月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第二十五張，PPT共五十頁，創(chuàng)作于2022年6月(a) 凸函數(shù) (b)凹函數(shù)該定義的一個(gè)應(yīng)用證明不等式例：證明Young不等式推廣：Hlde

9、r不等式P41 2.37證法：在Young不等式中令第二十六張，PPT共五十頁，創(chuàng)作于2022年6月例：設(shè)試證明在上是嚴(yán)格凸函數(shù)證明:設(shè)且都有：因此,在上是嚴(yán)格凸函數(shù)凸函數(shù)第二十七張，PPT共五十頁，創(chuàng)作于2022年6月例：試證線性函數(shù)是上的凸函數(shù)證明:設(shè)則故,是凸函數(shù)類似可以證明也是凹函數(shù).凸函數(shù)第二十八張，PPT共五十頁，創(chuàng)作于2022年6月凸函數(shù)定理1設(shè)是凸集上的凸函數(shù)充要條件性質(zhì)詹生(Jensen)不等式不等式應(yīng)用: 設(shè)，證明:P41 2.36第二十九張，PPT共五十頁，創(chuàng)作于2022年6月凸函數(shù)定理2性質(zhì)正線性組合第三十張，PPT共五十頁，創(chuàng)作于2022年6月凸函數(shù)定理3設(shè)是凸集上的

10、凸函數(shù)，則對(duì)任意，水平集是凸集水平集(Level Set)稱為函數(shù)f在集合S上關(guān)于數(shù) 的水平集.注：定理3 的逆命題不成立.第三十一張，PPT共五十頁，創(chuàng)作于2022年6月下面的圖形給出了凸函數(shù)的等值線的圖形，可以看出水平集是凸集.凸函數(shù)第三十二張，PPT共五十頁，創(chuàng)作于2022年6月凸函數(shù)第三十三張，PPT共五十頁，創(chuàng)作于2022年6月定理1:設(shè)是定義在凸集上，令則:(1)是定義在凸集是凸集上的凸函數(shù)的充要條件是對(duì)任意的一元函數(shù)為上的凸函數(shù).(2)設(shè)若在上為嚴(yán)格凸函數(shù)，則在上為嚴(yán)格凸函數(shù)凸函數(shù)凸函數(shù)的判別定理第三十四張，PPT共五十頁，創(chuàng)作于2022年6月該定理的幾何意義是：凸函數(shù)上任意兩點(diǎn)

11、之間的部分是一段向下凸的弧凸函數(shù)第三十五張，PPT共五十頁，創(chuàng)作于2022年6月定理4設(shè)在凸集上可微，則：在上為凸函數(shù)的充要條件是對(duì)任意的都有：嚴(yán)格凸函數(shù)(充要條件)?凸函數(shù)凸函數(shù)的判別定理-一階條件注：定理4提供了一個(gè)判別可微函數(shù)是否為凸 函數(shù)的依據(jù).第三十六張，PPT共五十頁，創(chuàng)作于2022年6月凸函數(shù)定理4-幾何解釋一個(gè)可微函數(shù)是凸函數(shù)當(dāng)且僅當(dāng)函數(shù)圖形上任一點(diǎn)處的切平面位于曲面的下方.第三十七張，PPT共五十頁，創(chuàng)作于2022年6月凸函數(shù)定理4-幾何解釋一個(gè)可微函數(shù)是凸函數(shù)當(dāng)且僅當(dāng)函數(shù)圖形上任一點(diǎn)處的切平面位于曲面的下方.第三十八張，PPT共五十頁，創(chuàng)作于2022年6月定理5:設(shè)在開凸集

12、內(nèi)二階可微,則是內(nèi)的凸函數(shù)的充要條件為:對(duì)任意的Hesse矩陣半正定,其中：凸函數(shù)凸函數(shù)的判別定理-二階條件第三十九張，PPT共五十頁，創(chuàng)作于2022年6月定理2.3.6:設(shè)在開凸集內(nèi)二階可微,若在內(nèi)正定,則在內(nèi)是嚴(yán)格凸函數(shù)注:反之不成立例：f(x)是嚴(yán)格凸的，但在點(diǎn)處不是正定的凸函數(shù)凸函數(shù)的判別定理-二階條件第四十張，PPT共五十頁，創(chuàng)作于2022年6月例：凸函數(shù)凸函數(shù)的判別定理-二階條件第四十一張，PPT共五十頁，創(chuàng)作于2022年6月凸規(guī)劃凸規(guī)劃(Convex Programming)設(shè)為凸集，為上的凸函數(shù)，則稱規(guī)劃問題為凸規(guī)劃問題例：為上的凸函數(shù)，為無約束凸規(guī)劃問題例：凸規(guī)劃第四十二張，PPT共五十頁，創(chuàng)作于2022年6月凸規(guī)劃例：第四十三張，PPT共五十頁，創(chuàng)作于2022年6月凸規(guī)劃定理2.4(1)凸規(guī)劃問題的任一局部極小點(diǎn)是全局極小點(diǎn)，且全體極小點(diǎn)的集合為凸集(2)若是凸集上的嚴(yán)格凸函數(shù)，且凸規(guī)劃問題局部極小點(diǎn)x*存在，則x*是唯一的全局極小點(diǎn)凸規(guī)劃的基本性質(zhì)第四十四張，PPT共五十頁，創(chuàng)作于2022年6月定理 凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。證明：設(shè)x*是凸規(guī)劃的一個(gè)局部解，則存在0,使如果x*不是整體最優(yōu)解，則又因?yàn)閒是凸函數(shù)，所以取0充分小，有第四十五張，PPT共五十頁，創(chuàng)作于2022年6月例 如下非線性規(guī)劃是否為凸規(guī)劃