第3讲 凸集、凸函数、凸规划.ppt

《第3讲 凸集、凸函数、凸规划.ppt》由会员分享，可在线阅读，更多相关《第3讲 凸集、凸函数、凸规划.ppt（51页珍藏版）》请在麦多课文档分享上搜索。

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),定义 分离 (Separation),凸集

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

4、,凸集-凸集分离定理应用,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),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

6、,X2,任意两点的函数值的连线上的点都在曲线的上方,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充分小，有,例 如下非线性规划是否为凸规划：,正定，凸函数,所以，该问题为凸规划。,半正定，凸函数,半正定，凸函数,如图所示，该问题最优解（最小点）在x*点取得。,例 验证下列（MP）是凸规划,作业,P38 2.1, 2.2, 2.4, 2.9-14,2.19, 2.20(后),2.32, 2.36,