1、线性规划线性规划 凸集和凸函数凸集和凸函数 1 凸集和凸函数在非线性规划的理论中具有重要作用，下面 给出凸集和凸函数的一些基本知识。 定义1 设 ，若对D中任意两点 与 ，连接 与 的线段仍属于D；换言之，对 ， D， 0,1恒有 +(1- ) D 则称D为凸集。 + (1- ) 称为 和 的凸组合。 n R D ) 1 ( x ) 2 ( x ) 1 ( x ) 2 ( x ) 1 ( x ) 2 ( xa ) 1 ( xa ) 2 ( xa ) 1 ( xaa ) 2 ( x ) 1 ( x ) 2 ( x 2 例 3 (i) 超平面 为凸集。 b= xPx T H 定义为 (ii) 半空
2、间 为凸集。b= - xPx T H 定义为 (iii) 射线 为凸集，其中d为 给定的非零向量， 为定点。 0, )0( +=lldxxxL )0( x (iv) 超球 是凸集。 (v) 欧式空间 是凸集，规定空集 是凸集 4 凸集的性质 有限个凸集的交集仍然是凸集。 设 是凸集，则 是凸集。 设 是凸集，则 是凸集。 凸集的和集仍然是凸集。 设 是凸集，则 是凸集。 推论：设 是凸集， ，则 也是凸集， 其中 。 5 定义3 极点（顶点）：设设D D是凸集是凸集, , 若若D D中的点中的点x x 不能成为不能成为D D中中 任何线段上的内点，则称任何线段上的内点，则称x x为凸集为凸集D
3、 D的极点。的极点。 设D为凸集，XD,若X不能用X(1)D,X(2)D两点的 一个凸组合表示为X=X(1)+ (1-)X(2),其中00，即Hesse矩阵正定，则 为严格 凸函数。 )( 2 xf )(xf 例：证明函数 是 上的凸函数。 17 若规划 = = ljh migts f j i , 2 , 1, 0)( , 2 , 1, 0)(. . )(min x x x 中, 和- 为凸函数, 是线性函数,则上述问题为 求凸规划。 )(xf)(x i g)(x i h 定义6:凸规划 设D 为凸集, 是定义在D上的凸函数，则称规 划问题 为凸规划。 18 凸规划是非线性规划中的一种重要特殊情形，它具有 很好的性质。 定理4：（1)凸规划的任意局部极小点就是整体极小点，且 极小点集合是凸集。 (2)如果凸规划的目标函数是严格凸函数，又存在极 小点，则它的极小点还是唯一的。 19
