第三節(jié) 凸函數(shù)

1、最優(yōu)化設(shè)計 汕頭大學(xué)工學(xué)院學(xué)習(xí)目標(biāo)1、理解凸函數(shù)的定義，并能進行簡單的凸函數(shù)證明。2、了解凸函數(shù)的基本性質(zhì)。3、掌握凸函數(shù)的一階與二階判定方法。第三節(jié) 凸函數(shù)凸函數(shù)的凸函數(shù)的定義定義凸函數(shù)凸函數(shù)的性質(zhì)的性質(zhì)凸函數(shù)凸函數(shù)的判定的判定一、凸函數(shù)的定義定義定義1 1 設(shè)函數(shù)設(shè)函數(shù)f f(x)(x)為定義在凸集為定義在凸集D D上的上的n n元實函數(shù)。元實函數(shù)。如果任取如果任取D D中的兩個不同點中的兩個不同點x x1 1，x x2 2，以及，以及0,10,1，都有，都有fx1+(1-)x2f(x1)+(1-)f(x2)則稱則稱f f(x)(x)是定義集是定義集D D上的凸函數(shù)。上的凸函數(shù)。定義定義2

2、 2 嚴格凸函數(shù)嚴格凸函數(shù)fx1+(1-)x2f(x1)+(1-)f(x2)則稱則稱f f(x)(x)是定義集是定義集D D上的凸函數(shù)。上的凸函數(shù)。注：將上述定義中的不等式反向，可以得到注：將上述定義中的不等式反向，可以得到凹函數(shù)的定義。凹函數(shù)的定義。凸函數(shù)的幾何性質(zhì) 對一元函數(shù)對一元函數(shù)f(x),f(x),在幾何上在幾何上f(xf(x1 1)+(1-)+(1-)f(x)f(x2 2) )（0 01)1)表示連接表示連接( (x x1 1，f(xf(x1 1) ) )， ( (x x2 2，f(xf(x2 2) ) )的的線段。線段。 f fx x1 1+(1-+(1-)x)x2 2 表示在點

3、表示在點x x1 1+(1-+(1-)x)x2 2處的處的 函數(shù)值。函數(shù)值。 所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點 的線段總是位于曲線弧的上方。的線段總是位于曲線弧的上方。 例例1 1：設(shè)：設(shè)f(x)=(x-1)f(x)=(x-1)2 2, ,試證明試證明f(x)f(x)在在（- -，+ +） 上是嚴格上是嚴格凸函數(shù)。凸函數(shù)。 證明：設(shè)證明：設(shè)x x，y yR R，且，且x xy y，（0 0 ，1 1）都有：都有： f fx+(1-x+(1-)y-)y-f(x)+(1-f(x)+(1-)f(y)f(y) = =x+(1-x+(1- )y-1)y-1

4、2 2 - - (x-1)(x-1)2 2 - (1- (1- )(y-1)(y-1)2 2 = = - -(1-(1- )(x-y)(x-y)2 20 0 因此因此f(x)f(x)在在（- -，+ +）上是嚴格凸函數(shù)。上是嚴格凸函數(shù)。 例例2 2：試證線性函數(shù)是：試證線性函數(shù)是R Rn n上的凸函數(shù)。上的凸函數(shù)。 f(x)=cf(x)=cT Tx=cx=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn n 證明：設(shè)證明：設(shè)x x，y yR R，（0,10,1），），則則 f fx x+(1-+(1-)y)y=c=cT T xx+(1- )y+(1- )y = c = cT

5、 Tx+(1-) cx+(1-) cT Ty=y=ff(x)+(1-)f(y)(x)+(1-)f(y) 所以所以c cT Tx x是凸函數(shù)。是凸函數(shù)。 類似可以證明類似可以證明c cT Tx x是凸函數(shù)。是凸函數(shù)。 二、凸函數(shù)的性質(zhì) 性質(zhì)性質(zhì)1 1：定義在同一凸集上的有限個凸函：定義在同一凸集上的有限個凸函數(shù)的非負線性組合是凸函數(shù)。數(shù)的非負線性組合是凸函數(shù)。 證明證明: : 設(shè)設(shè)f fi i(x),(x),ii=1,2,=1,2,k k是定義在同一凸集是定義在同一凸集D D上的上的k k個凸函數(shù)，個凸函數(shù)，1 1，2 2，k k是是k k個非負數(shù)。記個非負數(shù)。記f(x)= f(x)= f fi

6、i(x) (x) 現(xiàn)任取現(xiàn)任取D D內(nèi)的兩個點內(nèi)的兩個點x x1 1，x x2 2，以及以及（0,10,1），），由于由于 是是D D上的凸函數(shù)，必有上的凸函數(shù)，必有 f fii x x1 1+(1-+(1-)x)x2 2 fifi(x1)+(1-)(x1)+(1-)fi fi(x2)(x2)，ii=1,2,k=1,2,k 1kii( )ifx f fx x1 1+(1-+(1-)x)x2 2= = f fii ( (x x1 1+(1-+(1-)x)x2 2) ) ffii(x(x1 1)+(1-)f(x)+(1-)f(x2 2) ) = = f fii(x(x1 1)+(1- ) f(x)

7、+(1- ) f(x2 2) ) = =ff(x(x1 1)+(1-)f(x)+(1-)f(x2 2) ) 由凸函數(shù)的定義，可知由凸函數(shù)的定義，可知f(x)f(x)是是D D上的凸函數(shù)。上的凸函數(shù)。kii=11kiikii=1kii=1 定義定義3 3 （-水平集）水平集） 設(shè)設(shè)f(x)f(x)是定義在集合是定義在集合R R上的實函數(shù)，上的實函數(shù)，是是實數(shù)，則稱如下的集合實數(shù)，則稱如下的集合S S=x | x=x | xR , f(x)R , f(x) 是函數(shù)是函數(shù)f(x)f(x)的的-水平集。水平集。性質(zhì)性質(zhì)2 2 凸函數(shù)的任一凸函數(shù)的任一-水平集是凸集。水平集是凸集。 證明證明 設(shè)設(shè)f(x

8、)是定義在凸集是定義在凸集D D上的凸函數(shù)，上的凸函數(shù)，是任一給定的是任一給定的實數(shù)?，F(xiàn)任取實數(shù)?，F(xiàn)任取S內(nèi)兩點內(nèi)兩點x1,x2以及以及（0, 1），），則由則由S的定的定義義f(xi)，且且xiD,i =1，2D是凸集是凸集x1+(1-)x2D 又因為又因為f(x)f(x)是是D上的凸函數(shù)，所以有上的凸函數(shù)，所以有 fx1+(1-)x2f(x1)+(1-)f(x2) +(1-)= 表明，表明，x1+(1-)x2 S 所以，所以， S是凸集。是凸集。 下面的圖形給出了凸函數(shù)下面的圖形給出了凸函數(shù) f(f(x,yx,y) = x) = x4 4 + 3x+ 3x2 2 +y+y4 4 + + y

9、 y2 2 + +xyxy的等值線的圖形，可以看出水平集是凸集。的等值線的圖形，可以看出水平集是凸集。 性質(zhì)性質(zhì)3 3 設(shè)設(shè)D D是內(nèi)部非空的凸集，是內(nèi)部非空的凸集，f(x)f(x)是定義是定義在在D D上的凸函數(shù)，則上的凸函數(shù)，則f(x)f(x)在在D D的內(nèi)部連續(xù)。的內(nèi)部連續(xù)。 注意：凸函數(shù)在定義域的邊界注意：凸函數(shù)在定義域的邊界有可能有可能不連續(xù)。不連續(xù)。 例如，設(shè)例如，設(shè)f(x)f(x)的定義域是區(qū)間的定義域是區(qū)間1,41,4x x2 2,1x4,1x4 2, 2,x x=1 =1 f(x)f(x)是區(qū)間是區(qū)間1,41,4上的凸函數(shù)，但顯然在邊界點上的凸函數(shù)，但顯然在邊界點x=1x=1

10、處不連續(xù)。處不連續(xù)。 f (x)=f (x)=三、凸函數(shù)的判定定理1 （凸函數(shù)的一階充要條件） 設(shè)設(shè)D D是開凸集，是開凸集，f(x)f(x)在在D D上具有一階連續(xù)導(dǎo)上具有一階連續(xù)導(dǎo)數(shù)。那么，數(shù)。那么，f(x)f(x)是是D D上的凸函數(shù)的充要條上的凸函數(shù)的充要條件是：對件是：對D D上任意兩個不同點上任意兩個不同點x1,x2，恒有恒有 f(x2) f(x1) + f(x1)T(x2-x1) 證明證明 （必要性）（必要性）X1+ (x2-x1) = x2+(1-)x1D由由一階一階Taylor展式展式，有，有f(x1+ (x2-x1)= f(x1) + f(x1)T(x2-x1)+o() (

11、1)而由于而由于f(x)f(x)是是D上的凸函數(shù)，又有上的凸函數(shù)，又有f(x1+ (x2-x1)=f( x2+ (1- )x1) f(x2) + (1- ) f(x1) (2)兩式聯(lián)立，有兩式聯(lián)立，有 f(x2) + (1- ) f(x1) f(x1) + f(x1)T(x2-x1)+o() f(x2) f(x1) + f(x1)T(x2 - x1)+ 令令0+，則有則有 0 故故 f(xf(x2 2) ) f(xf(x1 1) + ) + f(xf(x1 1) )T T(x(x2 2-x-x1 1) )（充分性）任取（充分性）任取01，記記X= x1+(1-)x2 由已知條件有由已知條件有

12、f(xf(x1 1) ) f(x) + f(x) + f(x)f(x)T T(x(x1 1-x)-x) f(xf(x2 2) ) f(x) + f(x) + f(x)f(x)T T(x(x2 2-x)-x) 所以所以 f(xf(x1 1) ) f(x) + f(x) + f(x)f(x)T T(x(x1 1-x)-x)o(o() )o(o() ) (1-) f(xf(x2 2) ) (1-) f(x) + f(x) + (1-)f(x)f(x)T T(x(x2 2-x)-x) 兩式相加，并進行整理，得兩式相加，并進行整理，得 f(xf(x1 1) ) +(1-) f(xf(x2 2) )f(x

13、) +f(x) + f(x)f(x)T T x x1 1+(1-+(1-)x)x2 2 -x-x 注意到正好有注意到正好有X =X =x x1 1+(1-+(1-)x)x2 2 因此因此 f(xf(x1 1) ) +(1-) f(xf(x2 2) )f(x) =ff(x) =fx x1 1+(1-+(1-)x)x2 2 表明表明f(x)f(x)是凸集是凸集D D上的凸函數(shù)。上的凸函數(shù)。定理1（嚴格凸函數(shù)的一階充要條件）設(shè)設(shè)D D為開凸集，為開凸集，f(x)f(x)在在D D上具有一階連續(xù)導(dǎo)上具有一階連續(xù)導(dǎo)數(shù)。那么，數(shù)。那么，f(x)f(x)是是D D上的凸函數(shù)的充要條上的凸函數(shù)的充要條件是：對

14、件是：對D D上任意兩個不同點上任意兩個不同點x x1 1,x,x2 2，恒有，恒有 f(x f(x2 2) ) f(xf(x1 1) + ) + f(xf(x1 1) )T T(x(x2 2-x-x1 1) )例例3 3 設(shè)設(shè)f(x)=xf(x)=x4 4，x x屬于屬于（- -，+ +），），判斷函數(shù)判斷函數(shù)的凸凹性。的凸凹性。解：任取兩相異點解：任取兩相異點x x1 1，x x2 2，則有則有f(xf(x1 1)= f)= f(x x1 1)=4x)=4x1 13 3f(xf(x2 2)-f(x)-f(x1 1) + ) + f(xf(x1 1) )T T(x(x2 2-x-x1 1)

15、=x =x2 24 4-x-x1 14 4-4x-4x1 13 3(x(x2 2-x-x1 1) ) =x =x2 24 4-2x-2x1 12 2x x2 22 2+x+x1 14 4+2x+2x1 12 2x x2 22 2-4x-4x1 13 3x x2 2+2x+2x1 14 4 =(x=(x1 12 2-x-x2 22 2) )2 2+2x+2x1 12 2(x(x1 1-x-x2 2) )2 20 0由定理由定理1，知知f(x)f(x)是嚴格凸函數(shù)。是嚴格凸函數(shù)。定理2 （凸函數(shù)的二階充要條件） 設(shè)設(shè)D D是開凸集，是開凸集，f(x)f(x)在在D D上二次可微。上二次可微。那么，

16、那么， f(x) f(x)是是D D上的凸函數(shù)的充要條上的凸函數(shù)的充要條件是：件是： f(x)f(x)在在D D上的上的HesseHesse矩陣矩陣2 2f(x)f(x)是半正定的。是半正定的。證明證明 （充分性）（充分性） 設(shè)對設(shè)對D D上任一點上任一點X X， 2 2f(x)f(x)是半正定矩是半正定矩陣?，F(xiàn)任取陣。現(xiàn)任取D D上兩相異點上兩相異點x x1 1,x,x2 2, ,由由TaylorTaylor展式，有展式，有f(xf(x2 2)=f(x)=f(x1 1)+)+f(xf(x1 1) )T T(x(x2 2-x-x1 1)+)+ (x(x2 2-x-x1 1) ) T T 2 2

17、 (x(x2 2-x-x1 1) )其中，其中， =x=x1 1+(1-)x+(1-)x2 2 , 0, 01 1由于由于D D是凸集，故是凸集，故 D,D,由已知條件，當(dāng)然由已知條件，當(dāng)然2 2 也是半正也是半正定矩陣。于是有定矩陣。于是有(x(x2 2-x-x1 1) )T T 2 2 (X(X2 2-X-X1 1) ) 0 012_f(x)_x_x_f(x)_( )f x（所以，所以， f(xf(x2 2) ) f(xf(x1 1) + ) + f(xf(x1 1) )T T(x(x2 2-x-x1 1) ) 表明表明f(x)f(x)確為凸函數(shù)。確為凸函數(shù)。（必要性）由于（必要性）由于D

18、 D是開集，故對是開集，故對D D上任意點上任意點X X，以及，以及任一給定的非零向量任一給定的非零向量Y Y，總可找到充分小的正數(shù)，總可找到充分小的正數(shù)，使得，使得X+X+Y Y D D由由TaylorTaylor展式，有展式，有f(X+f(X+Y)=f(X)+Y)=f(X)+ f(X)f(X)T TY + YY + YT T2 2f( )f( )T TY Y +o(+o(2 2) )_X2 22 2又由于又由于f(X)f(X)是是D D上的凸函數(shù)，由凸函數(shù)的一階條件，上的凸函數(shù)，由凸函數(shù)的一階條件，有有f(X+f(X+Y)Y) f(X)+f(X)+ f(X)f(X)T T Y Y因此因此

19、Y YT T2 2f( )f( )T T Y +o(Y +o(2 2) ) 0 0 Y YT T2 2f( )Y + f( )Y + 0 0令令0 0+ +，則有，則有 0 0則則 Y YT T2 2f( )Yf( )Y 0 0 由半正定矩陣的定義，知由半正定矩陣的定義，知 2 2f( )f( )是半正定矩陣。是半正定矩陣。2 22 2_X_X2 22 2o(o( ) )2 22 2o(o( ) )_X_X定理2 （嚴格凸函數(shù)的二階充分條件）設(shè)設(shè)f(x)f(x)是開凸集上的實函數(shù)，若是開凸集上的實函數(shù)，若f(x)f(x)的的HesseHesse矩陣矩陣2 2f(x)f(x)在在D D上處處正定，則上處處正定，則 f(x)f(x)是是D D上的嚴格凸函數(shù)。上的嚴格凸函數(shù)。 證明略 例4 試判斷下列函數(shù)的凸凹性。 a)f(x)=5x12+x1x2+x22-5x1+4x2,x（-,+） b)f(x)=-x12+3x1x2-4x22-6x1+3,x（-,+） c)f(x)=x12+2x23-x3,x10,x20,-x3+ d)f(x)=x12+4x1x2-x22解 a)由于由于2 2f(x)f(x)的一階順序主子式為的一階順序主子式為1010，大于零，大于零，