《3凸集+凸函数+凸规划》由会员分享，可在线阅读，更多相关《3凸集+凸函数+凸规划（44页珍藏版）》请在金锄头文库上搜索。
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)凸锥组合为以原点为锥顶并通过这两点的锥.凸集-定义凸集-定义定义1设集合若对于任意两点及实数都有：则称集合为凸集常见的凸集：单点集 x ，空集 ，整个欧氏空间 Rn，超平面：半空间：例： 证明超球为凸集证明： 设为超球中的任意两点，则有：即点属于超球,所以超球为凸集凸集-举例(1) 任意多个凸集的交集为凸集(2)设是凸集， 是一实数，则下面的集合是凸集：凸集-性质(3)推论： 设是凸集， 则也是凸集， 其中是实数(4) S 是凸集当且仅当S中任意有限个点的凸组合仍然在S中.凸集-性质注：和集和并集有很大的区别，凸集的并集未
3、必是凸集，而凸集的和集是凸集例：表示轴上的点表示轴上的点则表示两个轴的所有点， 它不是凸集；而凸集凸集-性质定义 设 S 中任意有限个点的所有凸 组合所构成的集合称为S的凸包，记为H(S),即凸集-凸包(Convex Hull)定理2.1.4 H(S)是Rn 中所有包含S 的凸集的交集.H(S)是包含S 的最小凸集.定义 锥、凸锥凸集-凸锥 (Convex Cone)定义 分离 (Separation)凸集-凸集分离定理性质 定理2.1.5凸集-凸集分离定理(2)是点到集合的最短距离点的充要条件为：注：闭凸集外一点与闭凸集的极小距离，即投影定理。定理2.1.5 直观解释我们不妨把一个闭凸集想象
4、为一个三维的充满了气体的气球（不一定为标准球形，但必须是凸的），那么，在气球外一点，到气球各点（包括内部）的距离是不一样的，但直觉告诉我们，肯定在气球上有一点，它到该点的距离是所有距离中最小的。这是凸集的特有性质。如果不是凸集，就不会这样了，比如一个平面上对称心形的图形（它不是凸的）外一点，至少可以找到2点，使其到外面那一点的距离最小。凸集-凸集分离定理凸集分离定理 定理2.1.6凸集-凸集分离定理ylS点与闭凸集的分离定理凸集分离定理应用-Farkas引理 定理2.1.7凸集-凸集分离定理应用Farkas引理在我们即将学习的最优性条件中是重要的基础.Farkas引理 几何解释设A的第i个行向
5、量为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所生成的 凸锥内.a2(2.1.4)有解，(2.1.5)无解a1amb凸集-凸集分离定理应用a1a2amb(2.1.4)无解，(2.1.5)有解凸集分离定理应用-Gordan 定理 定理2.1.8凸集-凸集分离定理应用 利用Farkas引理可推导下述的Gordan定理和择一性定理.凸集分离定理应用-择一性定理 定理2.1.9凸函数凸函数(Co
6、nvex Function)(Convex Function) -定义定义2.42.4设是非空凸集，若对任意的及任意的都有：则称函数为上的凸函数注：将上述定义中的不等式反向，可以得到凹函数的定义凸函数严格凸函数 设是非空凸集，若对任意的及任意的都有：则称函数为上的严格凸函数注：将上述定义中的不等式反向，可以 得到严格凹函数的定义凸函数l 对一元函数在几何上表示连接的线段所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方几何性质表示在点处的函数值l f(X)f(X)X Xf(Xf(X1 1) )f(Xf(X2 2) )X X1 1 X X2 2f(X)f(X)X Xf f(X(X
7、1 1) )f f(X(X2 2) )X X1 1 X X2 2 x x1 1+(1-+(1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) )f(X)f(X)X Xf f(X(X1 1) )f f(X(X2 2) )X X1 1 X X2 2 x x1 1+(1-+(1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) )f(X)f(X)X X f f( x( x1 1 ) )+(1- +(1- ) f( x) f( x2 2) )f(Xf(X1 1) )f(Xf(X2 2) )X X1 1 X X2 2 x x1 1+(1-+(
8、1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) )f(X)f(X)X Xf(Xf(X1 1) )f(Xf(X2 2) )X X1 1 X X2 2任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方 x x1 1+(1-+(1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) ) f f( x( x1 1 ) )+(1- +(1- ) f( x) f( x2 2) )例4.2.1(a) 凸函数 (b)凹函数该定义的一个应用证明不等式例：证明Young不等式推广：Hlder不等式 P41 2.37证
9、法：在Young不等式中令例：设试证明在上是严格凸函数证明:设且都有：因此,在上是严格凸函数凸函数例：试证线性函数是上的凸函数证明:设则故,是凸函数 类似可以证明也是凹函数 .凸函数凸函数定理1 设是凸集上的凸函数充要条件性质詹生(Jensen)不等式不等式应用: 设，证明:P41 2.36凸函数定理2性质正线性组合凸函数定理3设是凸集上的凸函数，则对任意，水平集是凸集水平集(Level Set)称为函数称为函数f f在集合在集合S S上关于数上关于数 的水平集的水平集. .注：定理3 的逆命题不成立.下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集.凸函数凸函数定理1:设是定义在凸
10、集上，令则:(1 )是定义在凸集是凸集上的凸函数的充要条件是对任意的一元函数为上的凸函数 . (2 )设若在上为严格凸函数， 则在上为严格凸函数凸函数凸函数 凸函数的判别定理该定理的几何意义是：凸函数上任意两点之 间的部分是一段向下凸的弧凸函数凸函数定理4设在凸集上可微， 则：在上为凸函数的充要条件是对任意的都有：严格凸函数(充要条件)?凸函数凸函数凸函数的判别定理-一阶条件注：定理4提供了一个判别可微函数是否为凸函数的依据.凸函数凸函数定理4- 几何 解释一个可微函数 是凸函数当且 仅当函数图形 上任一点处的 切线位于曲 线的下方.凸函数凸函数定理4- 几何 解释一个可微函数 是凸函数当且
11、仅当函数图形 上任一点处的 切平面位于曲 面的下方.定理5:设在开凸集内二阶可微,则 是内的凸函数的充要条件为:对任意 的Hesse矩阵半正定 ,其中：凸函数凸函数 凸函数的判别定理-二阶条件定理2.3.6: 设在开凸集内二阶可微,若在内正定,则在内是严格凸函数注: 反之不成立例 ：f(x)是严格凸的，但在点处不是正定的凸函数凸函数 凸函数的判别定理-二阶条件例：凸函数凸函数凸函数的判别定理-二阶条件凸规划凸规划(Convex Programming) 设为凸集，为上的凸函数，则称规划问题为凸规划问题例：为上的凸函数， 为无约束凸规划问题例：凸 规 划凸规划例：凸规划定理2.4 (1)凸规划问题的任一局部极小点是全局极小点，且全体极小点的集合为凸集(2 )若是凸集上的严格凸函数，且凸规划问题局部极小点x*存在， 则x*是唯一的全局极小点凸规划的基本性质定理 凸规划的任一局部最优解都是它的整体最优解。证明：设x*是凸规划的一个局部解，则存在0,使如果x*不是整体最优解，则又因为f是凸函数，所以取0充分小，有例 如下非线性规划是否为凸规划：正定， 凸函数所以，该问题为凸规划。半正定， 凸函数半正定， 凸函数如图所示，该问题最优解（最小点）在x*点取得。例 验证下列（MP）是凸规划作业nP38 2.1, 2.2, 2.4, 2.9-14,2.19, 2.20(后),2.32, 2.36
