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設集合設集合,nRD 若對于任意兩點若對于任意兩點,Dyx 及實數及實數 ,10 都有：都有： ,1Dyx 則稱集合則稱集合D為為凸集凸集常見的凸集常見的凸集：單點集單點集 x ，空集空集 ，整個歐氏空間，整個歐氏空間 Rn，超平面超平面： ,2211bxaxaxaRxHnnn 半空間半空間：1122 =nnnnTHxRa x

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

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

5、 設設 S S 中任意有限個點的所有凸中任意有限個點的所有凸組合所構成的集合稱為組合所構成的集合稱為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、果果對對一一切切設設 SxRSn定義定義 分離分離 (Separation) .SS axpRxHaxpRxHS ,axpRxHS ,Ra0p,Rp,21TnTn2Tn1n21和和分分離離則則稱稱超超平平面面使使及及是是非非空空集集合合，如如果果存存在在設設 nRSS性質性質 定理定理2.1.52.1.5 .0Sxyxinfy-x , y ,Sx )1(S,Ryn 即即有有為為最最小小的的距距離離使使得得它它與與則則存存在在唯唯一一的的是是非非空空閉閉凸凸集集，設設nRS (2)Sx 是點是點y到集合到集合S的最短距離點的的最短距離點的充要條件為：充要條件為： .0SxyxxxT 注：注：閉凸

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

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

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

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

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

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

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

14、xf試證明試證明 xf在在 ,上是嚴格凸函數上是嚴格凸函數證明證明: :設設,Ryx 且且 1,0, yx都有：都有： yfxfyxf 11 22211111 yxyx 012 yx 因此因此, , xf在在 ,上是嚴格凸函數上是嚴格凸函數例：例：試證線性函數是試證線性函數是 nnTxcxcxcxcxf 2211nR上的凸函數上的凸函數證明證明: :設設 ,1,0, Ryx則則 yxcyxfT 11 yfxfycxcTT 11故故, ,xcT是凸函數是凸函數類似可以證明類似可以證明Tc x也是凹函數也是凹函數.定理定理1 1 設設 xf是凸集是凸集nRD 上的凸函數上的凸函數充要條件充要條件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上上的的凸凸函函數數都都是是和和則則上上的的凸凸函函數數是是凸凸集集SxfkiSfffiikiik 正線性組合正線性組合定理定理3 3設設 xf是凸集是凸集nRS 上的凸函數，上的凸函數，R 則對任意則對任意，水平集水平集 ,fS是凸集是凸集 .:,)(|,RSfRSxfSxfSn 其其中中 注

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

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

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

19、矩矩陣陣是是上上的的凸凸函函數數的的充充要要條條件件是是階階對對稱稱矩矩陣陣，則則是是其其中中為為二二次次函函數數，即即設設QRfQRfnQcxbQxxxfRRfnnTTn 凸規劃凸規劃(Convex Programming)(Convex Programming)設設nRD 為凸集為凸集， xf為為D上的凸函數上的凸函數，則稱規劃問題則稱規劃問題 xfDx min為凸規劃問題為凸規劃問題例：例： xf若若為為nR上的凸函數，上的凸函數， xfnRx min則則為無約束凸規劃問題為無約束凸規劃問題例：例：0 X bs.t.AX min CX線線性性規規劃劃凸凸規規劃劃例：例： ,.,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是凸規劃：是凸規劃：則下面三個規劃問題都則下面三個規劃問題都上的線性函數上的線性函數是是上的凹函數，上的凹函數，是是上的凸函數，上的凸函數，是是為開凸集，為開凸集，設設定理定理2.42.4(1)(1)凸規劃問題的任一局部極小點是全局凸規劃問題的任一局部極小點是全局極小點，且全體極小點的集合為凸集極小點，且全體極小點的集合為凸集(2)(2)若若 xf是凸集是凸集nRD 上的嚴格凸函數，上的嚴格凸函數，且凸規劃問題且凸規劃問題 xfDx min局部極小點局部極小點x x* *存在，存在，則則x x* *是唯一的全局極小點是唯一的全局極小點凸規劃的基本性質凸規劃的基本性質定理定理 凸規劃的任一局部最優解都是它的整體最優解。凸規劃的任一局部最優解都是它的整體最優解。證明：設證明：設x* *是凸規劃的一個局部解，則存在是凸規劃的一個局部解，則存在0,使使( *)(