線性規(guī)劃凸集凸函數(shù)（課堂PPT）

1、12 凸集和凸函數(shù)在非線性規(guī)劃的理論中具有重要作用，下面凸集和凸函數(shù)在非線性規(guī)劃的理論中具有重要作用，下面給出凸集和凸函數(shù)的一些基本知識(shí)。給出凸集和凸函數(shù)的一些基本知識(shí)。定義定義1 設(shè)設(shè) ，若對，若對D中任意兩點(diǎn)中任意兩點(diǎn) 與與 ，連接，連接 與與 的線段仍屬于的線段仍屬于D；換言之，對；換言之，對 ， D，0,1恒有恒有 +(1- ) D則稱則稱D為為凸集凸集。 + (1- ) 稱為稱為 和和 的的凸組合凸組合。nRD ) 1 (x) 2 (x) 1 (x) 2 (x ) 1 (x) 2 (xa a ) 1 (xa a) 2 (xa a) 1 (xa aa a) 2 (x) 1 (x) 2

2、(x3例例 4(i) 超平面超平面 為凸集。為凸集。 b b= = =xPxTH定義為定義為(ii) 半空間半空間 為凸集。為凸集。 b b = =- -xPxTH定義為定義為 (iii) 射線射線 為凸集，其中為凸集，其中d為為給定的非零向量，給定的非零向量， 為定點(diǎn)。為定點(diǎn)。0,)0( + += = =l ll ldxxxL)0(x(iv) 超球超球 是凸集。是凸集。xr (v) 歐式空間歐式空間 是凸集，規(guī)定空集是凸集，規(guī)定空集 是凸集是凸集nR 5凸集的性質(zhì)凸集的性質(zhì)有限個(gè)凸集的交集仍然是凸集。有限個(gè)凸集的交集仍然是凸集。 設(shè)設(shè) 是凸集，則是凸集，則 是凸集。是凸集。12,kD DD1

3、2kDDD設(shè)設(shè) 是凸集，則是凸集，則 是凸集。是凸集。D |,Dy yx xDb bb b= = = 凸集的和集仍然是凸集。凸集的和集仍然是凸集。 設(shè)設(shè) 是凸集，則是凸集，則 是凸集。是凸集。12,D D1212 |,DDy yxz xD zD+ += = =+ + 推論：設(shè)推論：設(shè) 是凸集，是凸集， ，則，則 也是凸集，也是凸集， 其中其中 。iD1kiiiDb b= = iRb b 1,2,ik= =6定義定義3 3 極點(diǎn)（頂點(diǎn)）極點(diǎn)（頂點(diǎn)）：設(shè)設(shè)D D為凸集，為凸集，XD,XD,若若X X不能用不能用X X(1)(1)D,XD,X(2)(2)DD兩點(diǎn)的兩點(diǎn)的 一個(gè)凸組合表示為一個(gè)凸組合表

4、示為X=XX=X(1)(1)+ (1-)X+ (1-)X(2)(2), ,其中其中01 01 ， 則稱則稱X X為為D D的一個(gè)極點(diǎn)。的一個(gè)極點(diǎn)。 kii=1=1定義定義2.2.凸組合凸組合：設(shè)：設(shè)X X(1)(1)，X X(2)(2)，X X(k)(k)是是n n維歐式空間中的維歐式空間中的k k個(gè)個(gè)點(diǎn)，若存在點(diǎn)，若存在1,1, 2 2, , k k滿足滿足00i i1,( 1,( i=1,2,k), 使使X=X=1 1X X(1)(1)+2 2 X X(2)(2)+k k X X(k)(k)， 則稱則稱X X為為X X(1)(1)，X X(2)(2)，X X(k)(k)的凸組合。的凸組合。

5、78定義定義4 設(shè)設(shè)D為為R 中非空凸集，若對中非空凸集，若對 ， D ，(0,1)恒有恒有n ) 1 (x) 2 (xa a f +(1- ) + (1- )f (*) 1 (xa) 2 (xa)() 1 (xfaa)()2(x則稱則稱 為為D上的凸函數(shù)；進(jìn)一步，若上的凸函數(shù)；進(jìn)一步，若 時(shí)，時(shí)，(*)式式僅僅成立。成立。)(xf xf(x)17定理定理3（二階條件）：（二階條件）： 設(shè)設(shè)D是是R 中非空開凸集中非空開凸集, 是定義在是定義在D上的二次可上的二次可微函數(shù)微函數(shù),則則 是是凸函數(shù)凸函數(shù)的充要條件為對的充要條件為對 x D, 0,即即Hesse矩陣矩陣 半正定半正定。n)(xf)

6、(xf )(2xf )(2xf 若若 x D , 0，即，即Hesse矩陣矩陣正定正定，則，則 為為嚴(yán)格嚴(yán)格凸函數(shù)凸函數(shù)。 )(2xf )(xf例：例：證明函數(shù)證明函數(shù) 是是 上的凸函數(shù)。上的凸函數(shù)。 22212( )Tnf xx xxxx= = =+ + + +nR18若規(guī)劃若規(guī)劃 = = = = ljhmigtsfji, 2 , 1, 0)(, 2 , 1, 0)(. .)(minxxx中中, 和和- 為凸函數(shù)為凸函數(shù), 是線性函數(shù)是線性函數(shù),則上述問題為則上述問題為求凸規(guī)劃。求凸規(guī)劃。)(xf)(xig)(xih定義定義6:凸規(guī)劃凸規(guī)劃 設(shè)設(shè)D 為凸集為凸集, 是定義在是定義在D上的凸函數(shù)，則稱規(guī)上的凸函數(shù)，則稱規(guī)劃問題劃問題 為凸規(guī)劃。為凸規(guī)劃。min( )x Df x ( )f xnR 19 凸規(guī)劃是非線性規(guī)劃中的一種重要特殊情形，它具有凸規(guī)劃是非線性規(guī)劃中的一種重要特殊情形，它具有很好的性質(zhì)。很好的性質(zhì)。定理定理4：（：（1)凸規(guī)劃的任意局部極小點(diǎn)就是整體極小點(diǎn)，且凸規(guī)劃的任意局部極小點(diǎn)就