1 凸集

第二章凸性(Convexity)•凸集(ConvexSet)•多胞形的表示定理(Polytope)•凸函数(ConvexFunction)•凸规划(ConvexProgramming)凸性是最优化理论必须涉及到基本概念.具有凸性的非线性规划模型是一类特殊的重要模型，它在最优化的理论证明及算法研究中具有非常重要的作用.凸集---定义.1,,...2,1,,,11miiniimiiimiRxRx且其中.,...2,1,,,1miRxRxniimiii其中线性组合(linearCombination).,...2,1,,,1miRxRxniimiii其中仿射组合(AffineCombination).1,...2,1,,,m1ii1且其中miRxRxniimiii凸组合(ConvexCombination)凸锥组合(ConvexConeCombination)凸集---定义例二维情况下，两点x1,x2的(a)线性组合为全平面；(b)仿射组合为过这两点的直线；(c)凸组合为连接这两点的线段；(b)凸锥组合为以原点为锥顶并通过这两点的锥.凸集---定义凸集---定义定义1设集合,nRD若对于任意两点,,Dyx及实数,10都有：,1Dyx则称集合D为凸集．常见的凸集：单点集{x}，空集，整个欧氏空间Rn，超平面：,2211bxaxaxaRxHnnn半空间：.2211bxaxaxaRxHnnn例：证明超球rx为凸集．证明：设为超球中的任意两点，yx,,10则有：yx1yx1,1rrr即点yx1属于超球,所以超球为凸集．凸集----举例(1)任意多个凸集的交集为凸集．(2)设D是凸集，是一实数，则下面的集合是凸集：DxxyyD,凸集-----性质(3).,|)b(;,|)a(221121212211212121是凸集是凸集上的凸集，则是和设DxDxxxDDDxDxxxDDRDDn推论：kiiiD1设kiDi,,2,1,是凸集，则也是凸集，其中i是实数．(4)S是凸集当且仅当S中任意有限个点的凸组合仍然在S中.凸集-----性质注：和集和并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集．例：RxxDT0,1表示x轴上的点．RyyDT,02表示y轴上的点．则21DD表示两个轴的所有点，它不是凸集；221RDD而凸集．凸集-----性质定义设S中任意有限个点的所有凸组合所构成的集合称为S的凸包，记为H(S),即,nRS凸集-----凸包(ConvexHull)miiiimiiiNmmiSxxSH11,1,...,2,1,0,)(定理2.1.4H(S)是Rn中所有包含S的凸集的交集.H(S)是包含S的最小凸集.定义锥、凸锥.SS.xS,Sxx,0Sx,000为凸锥则称又是凸集，如果为顶点的锥以是则称有及，如果对一切设SxRSn凸集-----凸锥(ConvexCone)定义分离(Separation).SSaxpRxHaxpRxHS,axpRxHS,Ra0p,Rp,21TnTn2Tn1n21和分离则称超平面使及是非空集合，如果存在设nRSS凸集-----凸集分离定理性质定理2.1.5.0Sxyxinfy-x,y,Sx)1(S,\Ryn即有为最小的距离使得它与则存在唯一的是非空闭凸集，设nRS凸集-----凸集分离定理(2)Sx是点y到集合S的最短距离点的充要条件为：.0SxyxxxT注：闭凸集外一点与闭凸集的极小距离，即投影定理。定理2.1.5直观解释我们不妨把一个闭凸集想象为一个三维的充满了气体的气球（不一定为标准球形，但必须是凸的），那么，在气球外一点，到气球各点（包括内部）的距离是不一样的，但直觉告诉我们，肯定在气球上有一点，它到该点的距离是所有距离中最小的。这是凸集的特有性质。如果不是凸集，就不会这样了，比如一个平面上对称心形的图形（它不是凸的）外一点，至少可以找到2点，使其到外面那一点的距离最小。凸集-----凸集分离定理凸集分离定理定理2.1.6.Syaxp|RxHS,xy,paxp,Ra0,RpS,\RyTnTTn和分离即存在超平面使得及则存在唯一的是非空闭凸集，设pRSnn凸集-----凸集分离定理ylS点与闭凸集的分离定理凸集分离定理应用---Farkas引理定理2.1.7(2.1.5).0y,byA(2.1.4);0xb,0Ax,Rb,TTn有且仅有一组有解：则下列两个关系式组设nmRA凸集-----凸集分离定理应用Farkas引理在我们即将学习的最优性条件中是重要的基础.Farkas引理–几何解释设A的第i个行向量为ai,i=1,2,…,m,则(2.1.4)式有解当且仅当凸锥{x|Ax≤0}与半空间{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(2.1.6).0y0,y,0yA(2.1.5);0Ax,T且仅有一组有解：则下列两个关系式组有设nmRA凸集-----凸集分离定理应用利用Farkas引理可推导下述的Gordan定理和择一性定理.凸集分离定理应用---择一性定理定理2.1.9(2.1.9)0.yBuA,Rv0u,Ru(2.1.8)0Bx0,xA,,TTpm满足和无解当且仅当存在则关系式组设mpnmRBRA