1、. 1,.2 , 1, ,11 miiniimiiimiRxRx 且且其中其中.,.2 , 1, ,1miRxRxniimiii 其其中中線性組合線性組合 (linear Combination).,.2,1, ,1miRxRxniimiii 其其中中仿射組合仿射組合 ( (Affine Combination). 1,.2 , 1, ,m1ii1 且且其其中中miRxRxniimiii凸組合凸組合 (Convex Combination)凸錐組合凸錐組合 (Convex Cone Combination)例例 二維情況下，兩點二維情況下，兩點x1 1, , x2 2 的的 (a)(a)線性組

2、合為全平面；線性組合為全平面； (b)(b)仿射組合為過這兩點的直線；仿射組合為過這兩點的直線； (c)(c)凸組合為連接這兩點的線段；凸組合為連接這兩點的線段； (b)(b)凸錐組合為以原點為錐頂并通過這兩點的錐凸錐組合為以原點為錐頂并通過這兩點的錐. .定義定義1 1設(shè)集合設(shè)集合,nRD 若對于任意兩點若對于任意兩點,Dyx 及實數(shù)及實數(shù) ,10 都有：都有： ,1Dyx 則稱集合則稱集合D為為凸集凸集常見的凸集常見的凸集：單點集單點集 x ，空集空集 ，整個歐氏空間，整個歐氏空間 Rn，超平面超平面： ,2211bxaxaxaRxHnnn 半空間半空間：1122 =nnnnTHxRa x

3、a xa xbxRa xb例：例： 證明超球證明超球rx 為凸集為凸集證明證明： 設(shè)設(shè)為超球中的任意兩點，為超球中的任意兩點，yx ,10 則有：則有： yx 1 yx 1 , 1rrr 即點即點 yx 1屬于超球?qū)儆诔? ,所以超球為凸集所以超球為凸集 (1) (1) 任意多個凸集的交集任意多個凸集的交集為凸集為凸集 (2)(2)設(shè)設(shè)D是凸集，是凸集，是一實數(shù)，是一實數(shù)，則下面的則下面的集合是凸集：集合是凸集： DxxyyD , (3)(3) .,|)b(;,|)a(221121212211212121是凸集是凸集是凸集是凸集上的凸集，則上的凸集，則是是和和設(shè)設(shè)DxDxxxDDDxDxxx

4、DDRDDn 推論推論： kiiiD1 設(shè)設(shè)kiDi,2,1, 是凸集，是凸集， 則則也是凸集，也是凸集， 其中其中i是實數(shù)是實數(shù) (4)(4) S 是凸集當(dāng)且僅當(dāng)是凸集當(dāng)且僅當(dāng)S中任意有限個點的凸中任意有限個點的凸 組合仍然在組合仍然在S中中. .注：注：和集和集和和并集并集有很大的區(qū)別，凸集的并集有很大的區(qū)別，凸集的并集未必是凸集，而凸集的和集是凸集未必是凸集，而凸集的和集是凸集例例： RxxDT 0 ,1表示表示x軸上的點軸上的點 RyyDT ,02表示表示y軸上的點軸上的點則則21DD 表示兩個軸的所有點，表示兩個軸的所有點， 它不是凸集；它不是凸集；221RDD 而而凸集凸集定義定義

5、 設(shè)設(shè) S S 中任意有限個點的所有凸中任意有限個點的所有凸組合所構(gòu)成的集合稱為組合所構(gòu)成的集合稱為S S的凸包，記為的凸包，記為H H( (S S),),即即,nRS miiiimiiiNmmiSxxSH11, 1,.,2 , 1, 0,)( 定理定理2.1.42.1.4 H H( (S S) )是是Rn 中所有包含中所有包含S S 的凸集的交集的凸集的交集. .H H( (S S) )是包含是包含S S 的最小凸集的最小凸集. .定義定義 錐、凸錐錐、凸錐.SS .xS ,Sxx,0Sx,000為為凸凸錐錐則則稱稱又又是是凸凸集集，如如果果為為頂頂點點的的錐錐以以是是則則稱稱有有及及，如如

6、果果對對一一切切設(shè)設(shè) SxRSn定義定義 分離分離 (Separation) .SS axpRxHaxpRxHS ,axpRxHS ,Ra0p,Rp,21TnTn2Tn1n21和和分分離離則則稱稱超超平平面面使使及及是是非非空空集集合合，如如果果存存在在設(shè)設(shè) nRSS性質(zhì)性質(zhì) 定理定理2.1.52.1.5 .0Sxyxinfy-x , y ,Sx )1(S,Ryn 即即有有為為最最小小的的距距離離使使得得它它與與則則存存在在唯唯一一的的是是非非空空閉閉凸凸集集，設(shè)設(shè)nRS (2)Sx 是點是點y到集合到集合S的最短距離點的的最短距離點的充要條件為：充要條件為： .0SxyxxxT 注：注：閉凸

7、集外一點與閉凸集的極小距離閉凸集外一點與閉凸集的極小距離，即投影定理投影定理。定理定理2.1.5 2.1.5 直觀解釋直觀解釋 我們不妨把一個閉凸集想象為一個三維的充滿了氣體的氣我們不妨把一個閉凸集想象為一個三維的充滿了氣體的氣球（不一定球（不一定為為標(biāo)準(zhǔn)球形，但必須是凸的），那么，在標(biāo)準(zhǔn)球形，但必須是凸的），那么，在氣氣球外一球外一點，到點，到氣氣球各點（包括內(nèi)部）的距離是不一樣的，但直覺告訴球各點（包括內(nèi)部）的距離是不一樣的，但直覺告訴我們，肯定在我們，肯定在氣氣球上有一點，它到該點的距離是所有距離中最球上有一點，它到該點的距離是所有距離中最小的。這是凸集的特有性質(zhì)。如果不是凸集，就不會這

8、樣了，小的。這是凸集的特有性質(zhì)。如果不是凸集，就不會這樣了，比如一個平面上對稱心形的圖形（它不是凸的）外一點，至少比如一個平面上對稱心形的圖形（它不是凸的）外一點，至少可以找到可以找到2 2點，使其到外面那一點的距離最小。點，使其到外面那一點的距離最小。凸集分離定理凸集分離定理 定理定理2.1.62.1.6 .Syaxp|RxHS,xy,paxp ,R a0,Rp S,RyTnTTn和和分離分離即存在超平面即存在超平面使得使得及及則存在唯一的則存在唯一的是非空閉凸集，是非空閉凸集，設(shè)設(shè) pRSnnylS點與閉凸集的分離定理點與閉凸集的分離定理凸集分離定理應(yīng)用凸集分離定理應(yīng)用-Farkas-Fa

9、rkas引理引理 定理定理2.1.72.1.7(2.1.5) . 0y,by A(2.1.4) ; 0 xb, 0 Ax,Rb,TTn 有且僅有一組有解：有且僅有一組有解：則下列兩個關(guān)系式組則下列兩個關(guān)系式組設(shè)設(shè)nmRAFarkasFarkas引理在我們即將學(xué)習(xí)的最優(yōu)性條件中是重要的基礎(chǔ)引理在我們即將學(xué)習(xí)的最優(yōu)性條件中是重要的基礎(chǔ). .FarkasFarkas引理引理 幾何解釋幾何解釋 設(shè)設(shè)A的第的第i個行向量為個行向量為ai,i=1,2,m,則則(2.1.4)式有解式有解當(dāng)且僅當(dāng)凸錐當(dāng)且僅當(dāng)凸錐x|Ax0與半空間與半空間x|bTx0的交不空的交不空.即即(2.1.4)式有解當(dāng)且僅當(dāng)存在向量式

10、有解當(dāng)且僅當(dāng)存在向量x,它與各它與各ai的夾角鈍的夾角鈍角或直角，而與角或直角，而與b的夾角為銳角的夾角為銳角. (2.1.5)式有解當(dāng)且僅當(dāng)式有解當(dāng)且僅當(dāng)b在由在由 a1, a2, , am所生成的所生成的凸錐內(nèi)凸錐內(nèi).a a2 2a a1 1a am mb ba a1 1a a2 2a am mb b凸集分離定理應(yīng)用凸集分離定理應(yīng)用-Gordan-Gordan 定理定理 定理定理2.1.82.1.8(2.1.6) . 0y0,y, 0y A(2.1.5) ; 0 Ax,T 且且僅僅有有一一組組有有解解：則則下下列列兩兩個個關(guān)關(guān)系系式式組組有有設(shè)設(shè)nmRA利用利用FarkasFarkas引理

11、可推導(dǎo)下述的引理可推導(dǎo)下述的GordanGordan定理和擇一性定理定理和擇一性定理. .凸集分離定理應(yīng)用凸集分離定理應(yīng)用-擇一性定理擇一性定理 定理定理2.1.92.1.9(2.1.9) 0.yBu A ,Rv0u,Ru(2.1.8) 0Bx0,x A,TTpm 滿滿足足和和無無解解當(dāng)當(dāng)且且僅僅當(dāng)當(dāng)存存在在則則關(guān)關(guān)系系式式組組設(shè)設(shè)mpnmRBRA凸函數(shù)凸函數(shù) -設(shè)設(shè) ,:RSxf是非空凸集，是非空凸集，nRD 若對任意的若對任意的,Dyx 及任意的及任意的 1,0 都有：都有： yfxfyxf 11則稱函數(shù)則稱函數(shù) xf為為D上的凸函數(shù)上的凸函數(shù)注：注：將上述定義中的不等式反向，可以得到將上

12、述定義中的不等式反向，可以得到凹函數(shù)凹函數(shù)的定義的定義嚴(yán)格凸函數(shù)嚴(yán)格凸函數(shù)設(shè)設(shè) ,:RSxf是非空凸集，是非空凸集，nRD 若對任意的若對任意的,(),x yD xy及任意的及任意的0,1都有：都有： 11fxyfxfy則稱函數(shù)則稱函數(shù) xf為為D上的上的嚴(yán)格凸函數(shù)嚴(yán)格凸函數(shù)注：注：將上述定義中的不等式反向，可以將上述定義中的不等式反向，可以得到得到嚴(yán)格凹函數(shù)嚴(yán)格凹函數(shù)的定義的定義l 對一元函數(shù)對一元函數(shù) ,xf在幾何上在幾何上 211xfxf 10 表示連接表示連接 2211,xfxxfx的線段的線段所以所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點一元凸函數(shù)表示連接函數(shù)圖形上任意兩點的線段總是位

13、于曲線弧的上方的線段總是位于曲線弧的上方 211xxf 表示在點表示在點 211xx 處的處的函數(shù)值函數(shù)值l 例例4.2.1(a) (a) 凸函數(shù)凸函數(shù) (b)(b)凹函數(shù)凹函數(shù)該定義的一個應(yīng)用該定義的一個應(yīng)用證明不等式證明不等式例：證明例：證明11,pqxyx ypq11,0, ,0,1.pqx yp q其中( )lnf tt 凹pqxxxypqYoung不等式不等式11111pqnnnpqkkkkkkkx yxy 推廣：推廣：Hlder不等式不等式P41 2.37證法：在證法：在YoungYoung不等式中令不等式中令1:nppikkxxx 1:nqqikkyyy 例：例：設(shè)設(shè) ,12 x

14、xf試證明試證明 xf在在 ,上是嚴(yán)格凸函數(shù)上是嚴(yán)格凸函數(shù)證明證明: :設(shè)設(shè),Ryx 且且 1,0, yx都有：都有： yfxfyxf 11 22211111 yxyx 012 yx 因此因此, , xf在在 ,上是嚴(yán)格凸函數(shù)上是嚴(yán)格凸函數(shù)例：例：試證線性函數(shù)是試證線性函數(shù)是 nnTxcxcxcxcxf 2211nR上的凸函數(shù)上的凸函數(shù)證明證明: :設(shè)設(shè) ,1,0, Ryx則則 yxcyxfT 11 yfxfycxcTT 11故故, ,xcT是凸函數(shù)是凸函數(shù)類似可以證明類似可以證明Tc x也是凹函數(shù)也是凹函數(shù).定理定理1 1 設(shè)設(shè) xf是凸集是凸集nRD 上的凸函數(shù)上的凸函數(shù)充要條件充要條件1

15、21ii11,.,0(1, 2,.,),1, fxf(x ).kkiiikkiiiixxxDik則0ix 1112(1),ppppnnxxxxxpnn1112(1),ppppnnxxxxxpnnP41 2.36定理定理2 2.)(max(x) ),.,2 , 1(0),(xf(x) ,.,ki11i21上上的的凸凸函函數(shù)數(shù)都都是是和和則則上上的的凸凸函函數(shù)數(shù)是是凸凸集集SxfkiSfffiikiik 正線性組合正線性組合定理定理3 3設(shè)設(shè) xf是凸集是凸集nRS 上的凸函數(shù)，上的凸函數(shù)，R 則對任意則對任意，水平集水平集 ,fS是凸集是凸集 .:,)(|,RSfRSxfSxfSn 其其中中 注

16、：注：定理定理3 3 的逆命題不成立的逆命題不成立. .下面的圖形給出了凸函數(shù)下面的圖形給出了凸函數(shù)xyy 2 4243,yxxyxf 的等值線的圖形，可以看出水平集是凸集的等值線的圖形，可以看出水平集是凸集. .定理定理1:1:設(shè)設(shè) xf是定義在凸集nRD 上，上，,Dyx 令令 ,1,0,1 tyttxft 則則: :(1)(1) xf是定義在凸集是定義在凸集是凸集是凸集D上的上的凸函數(shù)凸函數(shù)的充要條件是對的充要條件是對任意的任意的,Dyx一元函數(shù)一元函數(shù) t為為1,0上的凸函數(shù)上的凸函數(shù). .(2)(2)設(shè)設(shè),yxDyx 若若 t 在在 1,0上為上為嚴(yán)格嚴(yán)格凸函數(shù)凸函數(shù)， 則則 xf在

17、在D上為嚴(yán)格凸函數(shù)上為嚴(yán)格凸函數(shù)該定理的該定理的幾何意義幾何意義是：凸函數(shù)上任意兩點之是：凸函數(shù)上任意兩點之間的部分是一段向下凸的弧間的部分是一段向下凸的弧定理定理4 4設(shè)在凸集設(shè)在凸集nRD 上上 xf可微可微， 則：則： xf在D上為凸函數(shù)的充要條件是對任意的上為凸函數(shù)的充要條件是對任意的,Dyx 都有：都有： .xyxfxfyfT 嚴(yán)格凸函數(shù)嚴(yán)格凸函數(shù)( (充要條件充要條件)?)? ()Tfyf xf xyxxy 定理定理5:5:設(shè)在開凸集設(shè)在開凸集nRD 內(nèi)內(nèi) xf二階可微二階可微, ,則則 xf是D內(nèi)的凸函數(shù)的充要條件為內(nèi)的凸函數(shù)的充要條件為: :對任意對任意,Dx xf的的Hess

18、eHesse矩陣矩陣 xG半正定半正定, , 22221222222122122122122nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxfxG其中：其中：定理定理2.3.6:2.3.6: 設(shè)在開凸集設(shè)在開凸集nRD 內(nèi)內(nèi) xf二階可微二階可微, ,若在若在D內(nèi)內(nèi) xG正定正定, ,則則 xf在在D內(nèi)內(nèi)是嚴(yán)格凸函數(shù)是嚴(yán)格凸函數(shù)注注: : 反之不成立反之不成立例例： 4xxf f(x)是嚴(yán)格凸的，是嚴(yán)格凸的，但在點但在點0 x處 xG不是正定的不是正定的例：例：.)2(.)1(,21)( :為為正正定定矩矩陣陣條條件件是是上上的的嚴(yán)嚴(yán)格格凸凸函函數(shù)數(shù)的的充充要要是是為為半半正正定定

19、矩矩陣陣是是上上的的凸凸函函數(shù)數(shù)的的充充要要條條件件是是階階對對稱稱矩矩陣陣，則則是是其其中中為為二二次次函函數(shù)數(shù)，即即設(shè)設(shè)QRfQRfnQcxbQxxxfRRfnnTTn 凸規(guī)劃凸規(guī)劃(Convex Programming)(Convex Programming)設(shè)設(shè)nRD 為凸集為凸集， xf為為D上的凸函數(shù)上的凸函數(shù)，則稱規(guī)劃問題則稱規(guī)劃問題 xfDx min為凸規(guī)劃問題為凸規(guī)劃問題例：例： xf若若為為nR上的凸函數(shù)，上的凸函數(shù)， xfnRx min則則為無約束凸規(guī)劃問題為無約束凸規(guī)劃問題例：例：0 X bs.t.AX min CX線線性性規(guī)規(guī)劃劃凸凸規(guī)規(guī)劃劃例：例： ,.,1, 0)

20、( ,.,1, 0)(.min(3) ,.,1, 0)(.min (2) ,.,1, 0)(.min (1) , ),.,2 , 1(h),.,2 , 1(ljxhmixgtsf(x)mixgtsf(x) ljxhtsf(x)RljSmigSfRSjiijnjin是凸規(guī)劃：是凸規(guī)劃：則下面三個規(guī)劃問題都則下面三個規(guī)劃問題都上的線性函數(shù)上的線性函數(shù)是是上的凹函數(shù)，上的凹函數(shù)，是是上的凸函數(shù)，上的凸函數(shù)，是是為開凸集，為開凸集，設(shè)設(shè)定理定理2.42.4(1)(1)凸規(guī)劃問題的任一局部極小點是全局凸規(guī)劃問題的任一局部極小點是全局極小點，且全體極小點的集合為凸集極小點，且全體極小點的集合為凸集(2)(2)若若 xf是凸集是凸集nRD 上的嚴(yán)格凸函數(shù)，上的嚴(yán)格凸函數(shù)，且凸規(guī)劃問題且凸規(guī)劃問題 xfDx min局部極小點局部極小點x x* *存在，存在，則則x x* *是唯一的全局極小點是唯一的全局極小點凸規(guī)劃的基本性質(zhì)凸規(guī)劃的基本性質(zhì)定理定理 凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。證明：設(shè)證明：設(shè)x* *是凸規(guī)劃的一個局部解，則存在是凸規(guī)劃的一個局部解，則存在0,使使( *)(