线性规划 凸集凸函数

1、 凸集和凸函数在非线性规划的理论中具有重要作用，下面凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。给出凸集和凸函数的一些基本知识。定义定义1 设设 ，若对，若对D中任意两点中任意两点 与与 ，连接，连接 与与 的线段仍属于的线段仍属于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 (x

2、例例 (i) 超平面超平面 为凸集。为凸集。 b b= = =xPxTH定义为定义为(ii) 半空间半空间 为凸集。为凸集。 b b = =- -xPxTH定义为定义为 (iii) 射线射线 为凸集，其中为凸集，其中d为为给定的非零向量，给定的非零向量， 为定点。为定点。0,)0( + += = =l ll ldxxxL)0(x(iv) 超球超球 是凸集。是凸集。xr (v) 欧式空间欧式空间 是凸集，规定空集是凸集，规定空集 是凸集是凸集nR 凸集的性质凸集的性质有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。 设设 是凸集，则是凸集，则 是凸集。是凸集。12,kD DD12kDDD

3、设设 是凸集，则是凸集，则 是凸集。是凸集。D |,Dy yx xDbbbb=凸集的和集仍然是凸集。凸集的和集仍然是凸集。 设设 是凸集，则是凸集，则 是凸集。是凸集。12,D D1212|,DDy yxz xD zD+=+=+推论：设推论：设 是凸集，是凸集， ，则，则 也是凸集，也是凸集， 其中其中 。iD1kiiiDb b= = iRb b 1,2,ik= =定义定义3 3 极点（顶点）极点（顶点）：设设D D为凸集，为凸集，XD,XD,若若X X不能用不能用X X(1)(1)D,XD,X(2)(2)DD两点的两点的 一个凸组合表示为一个凸组合表示为X=XX=X(1)(1)+ (1-)X

4、+ (1-)X(2)(2), ,其中其中01 01 ， 则称则称X X为为D D的一个极点。的一个极点。 kii=1=1定义定义2.2.凸组合凸组合：设：设X X(1)(1)，X X(2)(2)，X X(k)(k)是是n n维欧式空间中的维欧式空间中的k k个个点，若存在点，若存在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)的凸组合。的凸组合。定义定义4 设设D为为R 中非空凸

5、集，若对中非空凸集，若对 ， D ，(0,1)恒有恒有n ) 1 (x) 2 (xa a f +(1- ) + (1- )f (*) 1 (xa) 2 (xa)() 1 (xfaa)()2(x则称则称 为为D上的凸函数；进一步，若上的凸函数；进一步，若 时，时，(*)式式仅仅成立。成立。)(xf xf(x)定理定理3（二阶条件）：（二阶条件）： 设设D是是R 中非空开凸集中非空开凸集, 是定义在是定义在D上的二次可上的二次可微函数微函数,则则 是是凸函数凸函数的充要条件为对的充要条件为对 x D, 0,即即Hesse矩阵矩阵 半正定半正定。n)(xf)(xf )(2xf )(2xf 若若 x

6、D , 0，即，即Hesse矩阵矩阵正定正定，则，则 为为严格严格凸函数凸函数。 )(2xf )(xf例：例：证明函数证明函数 是是 上的凸函数。上的凸函数。 22212( )Tnf xx xxxx=+=+nR若规划若规划 = = = = ljhmigtsfji, 2 , 1, 0)(, 2 , 1, 0)(. .)(minxxx中中, 和和- 为凸函数为凸函数, 是线性函数是线性函数,则上述问题为则上述问题为求凸规划。求凸规划。)(xf)(xig)(xih定义定义6:凸规划凸规划 设设D 为凸集为凸集, 是定义在是定义在D上的凸函数，则称规上的凸函数，则称规划问题划问题 为凸规划。为凸规划。min( )x Df x ( )f xnR 凸规划是非线性规划中的一种重要特殊情形，它具有凸规划是非线性规划中的一种重要特殊情形，它具有很好的性质。很好的性质。定理定理4：（：（1)凸规划的任意局部极小点就是整体极小点，且凸规划的任意局部极小点就是