文档介绍：第第3 3讲讲凸集、凸函数、凸规划凸集、凸函数、凸规划??凸集凸集(Convex Set) (Convex Set) ??凸函数凸函数(Convex Function) (Convex Function) ??凸规划凸规划(Convex Programming) (Convex Programming) 凸性凸性( ( Convexity Convexity ) )是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念. .具有凸性具有凸性的非线性规划模型是一类特殊的重要模型,它在最优化的理论的非线性规划模型是一类特殊的重要模型,它在最优化的理论证明及算法研究中具有非常重要的作用证明及算法研究中具有非常重要的作用. .凸集凸集--- ---,,... 2,1,,, 1 1???????? mi i nii mi iim iRxR x???且其中. ,... 2,1,,, 1m iRxR x nii mi ii????????其中线性组合(bination) . ,... 2,1,,, 1m iRxR x nii mi ii???????其中仿射组合( bination) .1 ,... 2,1,,, m1i i 1????????????且其中 m iRxR x nii mi ii凸组合(bination) 凸锥组合(Convex bination) 凸集凸集--- ---定义定义例二维情况下,两点 x 1, x 2的(a) 线性组合为全平面; (b) 仿射组合为过这两点的直线; (c) 凸组合为连接这两点的线段; (b) 凸锥组合为以原点为锥顶并通过这两点的锥. 凸集凸集--- ---定义定义凸集凸集--- ---定义定义定义 1设集合, nRD?若对于任意两点,,Dyx?及实数??,10????都有: ??,1Dyx?????则称集合 D为凸集. 常见的凸集:单点集{ x },空集?,整个欧氏空间 R n, 超平面: ??, 2211bxaxaxaRxH nn n???????半空间: ???? 1 1 2 2 = n n n n T H x R a x a x a x b x R a x b ?? ? ????? ??例: 证明超球 rx?为凸集. 证明:设为超球中的任意两点, yx,,10???则有: ?? yx????1?? yx?????1??,1rrr??????即点?? yx????1属于超球,所以超球为凸集. 凸集凸集---- ---- 举例举例 (1) 任意多个凸集的交集为凸集. (2) 设 D是凸集, ?是一实数, 则下面的集合是凸集: ?? DxxyyD???,??凸集凸集----- ----- 性质性质(3) ????.,|)b( ;,|)a( 22112121 22112121 21 是凸集是凸集上的凸集,则是和设DxDxxxDD DxDxxxDD RDD n??????????推论: ?? ki iiD 1?设 kiD i,,2,1,??是凸集, 则也是凸集, 其中 i?是实数. (4) S 是凸集当且仅当 S中任意有限个点的凸组合仍然在 ----- ----- 性质性质注: 和集和并集有很大的区别,凸集的并集未必是凸集,而凸集的和集是凸集. 例: ???? RxxD T??0, 1表示 x轴上的点. ???? RyyD T??,0 2表示 y轴上的点. 则 21DD?表示两个轴的所有点, 它不是凸集; 221RDD??而凸集. 凸集凸集----- ----- 性质性质定义设S中任意有限个点的所有凸组合所构成的集合称为 S的凸包,记为 H(S),即, nRS?凸集凸集----- ----- 凸包凸包(Convex Hull) (Convex Hull) ???????????????? mi i ii mi ii Nm m iSxxSH 1 1,1,..., 2,1,0,)(???定理 H(S)是R n中所有包含 S 的凸集的交集. H(S)是包含 S 的最小凸集.