凸集和凸函数和凸规划-课件

1、第3讲 凸集、凸函数、凸规划,凸集 (Convex Set) 凸函数 (Convex Function) 凸规划 (Convex Programming),凸性(Convexity)是最优化理论必须涉及到基本概念.具有凸性的非线性规划模型是一类特殊的重要模型，它在最优化的理论证明及算法研究中具有非常重要的作用.,凸集-定义,线性组合 (linear Combination),仿射组合 (Affine Combination),凸组合 (Convex Combination),凸锥组合 (Convex Cone Combination),凸集-定义,例 二维情况下，两点x1, x2的 (a)线性

2、组合为全平面； (b)仿射组合为过这两点的直线； (c)凸组合为连接这两点的线段； (b)凸锥组合为以原点为锥顶并通过这两点的锥.,凸集-定义,凸集-定义,常见的凸集：单点集 x ，空集 ，整个欧氏空间 Rn，,超平面：,半空间：,则有：,凸集-举例,凸集-性质,(3),凸集-性质,凸集-性质,定义 设 S 中任意有限个点的所有凸组合所构成的集合称为S的凸包，记为H(S),即,凸集-凸包(Convex Hull),定理2.1.4 H(S)是Rn 中所有包含S 的凸集的交集.,H(S)是包含S 的最小凸集.,定义 锥、凸锥,凸集-凸锥 (Convex Cone),定义 分离 (Separatio

3、n),凸集-凸集分离定理,性质 定理2.1.5,凸集-凸集分离定理,定理2.1.5 直观解释 我们不妨把一个闭凸集想象为一个三维的充满了气体的气 球（不一定为标准球形，但必须是凸的），那么，在气球外一 点，到气球各点（包括内部）的距离是不一样的，但直觉告诉 我们，肯定在气球上有一点，它到该点的距离是所有距离中最 小的。这是凸集的特有性质。如果不是凸集，就不会这样了， 比如一个平面上对称心形的图形（它不是凸的）外一点，至少 可以找到2点，使其到外面那一点的距离最小。,凸集-凸集分离定理,凸集分离定理 定理2.1.6,凸集-凸集分离定理,点与闭凸集的分离定理,凸集分离定理应用-Farkas引理 定

4、理2.1.7,凸集-凸集分离定理应用,Farkas引理在我们即将学习的最优性条件中是重要的基础.,Farkas引理 几何解释,设A的第i个行向量为ai,i=1,2,m,则(2.1.4)式有解当且仅当凸锥x|Ax0与半空间x|bTx0的交不空.即(2.1.4)式有解当且仅当存在向量x,它与各ai的夹角钝角或直角，而与b的夹角为锐角.,(2.1.5)式有解当且仅当b在由 a1, a2, , am所生成的凸锥内.,凸集-凸集分离定理应用,凸集分离定理应用-Gordan 定理 定理2.1.8,凸集-凸集分离定理应用,利用Farkas引理可推导下述的Gordan定理和择一性定理.,凸集分离定理应用-择一

5、性定理 定理2.1.9,凸函数,凸函数(Convex Function) -定义2.4,凸函数,严格凸函数,设,是非空凸集，,若对任意的,及任意的,都有：,则称函数,为,上的严格凸函数,注：将上述定义中的不等式反向，可以得到严格凹函数的定义,凸函数,几何性质,f(X),X,f(X1),f(X2),X1,X2,f(X),X,f(X1),f(X2),X1,X2,x1+(1-)x2,f(x1+(1-)x2 ),f(X),X,f( x1 ) +(1- ) f( x2),f(X1),f(X2),X1,X2,x1+(1-)x2,f(x1+(1-)x2 ),f(X),X,f(X1),f(X2),X1,X2,

6、任意两点的函数值的连线上的点都在曲线的上方,x1+(1-)x2,f(x1+(1-)x2 ),f( x1 ) +(1- ) f( x2),例4.2.1,(a) 凸函数 (b)凹函数,该定义的一个应用证明不等式 例：证明,Young不等式,推广：Hlder不等式,P41 2.37,证法：在Young不等式中令,凸函数,凸函数,凸函数,性质,詹生(Jensen)不等式,P41 2.36,凸函数,定理2,性质,正线性组合,凸函数,定理3,水平集(Level Set),称为函数f在集合S上关于数 的水平集.,注：定理3 的逆命题不成立.,凸函数,凸函数,凸函数,凸函数的判别定理,凸函数,严格凸函数(充要

7、条件)?,凸函数,凸函数的判别定理-一阶条件,注：定理4提供了一个判别可微函数是否为凸 函数的依据.,凸函数,定理4-几何解释,一个可微函数是凸函数当且仅当函数图形上任一点处的切平面位于曲面的下方.,凸函数,定理4-几何解释,一个可微函数是凸函数当且仅当函数图形上任一点处的切平面位于曲面的下方.,凸函数,凸函数的判别定理-二阶条件,例：,凸函数,凸函数的判别定理-二阶条件,例：,凸函数,凸函数的判别定理-二阶条件,凸规划,凸规划(Convex Programming),例：,凸规划,凸规划,例：,凸规划,定理2.4,凸规划的基本性质,定理 凸规划的任一局部最优解都是它的整体最优解。 证明：设x*是凸规划的一个局部解，则存在0,使,如果x*不是整体最优解，则 又因为f是凸函数，所以,取0充分小，有,例 如下非线性规划是否为凸规划：,正定，凸函数,所以，该问题为