《凸集与凸函数》由会员分享,可在线阅读,更多相关《凸集与凸函数(41页珍藏版)》请在金锄头文库上搜索。
1、2. 凸集与凸函数2.1 仿射集仿射集对n维欧氏空间中任意两点xy,则通过x和y的直线可表为 l(x,y)=(1-)x+y|R 2. 凸集与凸函数则一个仿射集的平移也是仿射集Th2.1 (1)Rn的子空间是包含原点的仿射集;(2),对每一非空的仿射集M,存在唯一的子空间L和向量aRn,使得约定 M-a=M+(-a)若aM,则M-a是子空间.2. 凸集与凸函数若非空仿射集M=L+a,则aM,于是唯一子空间L可表为Df2.2. 非空仿射集非空仿射集M的维数是指平行于仿射的维数是指平行于仿射集集M的子空间的维数的子空间的维数.Rn中的n-1维仿射集称为超平面超平面.2. 凸集与凸函数Th2.2 给定
2、向量p(0)Rn,R,则是Rn中的一个超平面.反之,Rn任一超平面都可表成上式的形式,且在相差一个非零常数的意义下,(p,)是唯一的.2. 凸集与凸函数可验证,仿射集的交集仍是仿射集仿射集的交集仍是仿射集Df2.3 给定Rn中集合S,包含S的所有仿射集的交集,即包含S的最小仿射集称为S的仿射包,记为affS2. 凸集与凸函数Df2.1 Rn中任一集合S的维数定义为它的仿射包affS的维数,即包含S的仿射集的最小维数.2. 凸集与凸函数命题2.1 下述断言相互等价.2. 凸集与凸函数2. 凸集与凸函数2.2 凸集与锥凸集与锥2. 凸集与凸函数2. 凸集与凸函数x0xx-x0px0xx-x0p2.
3、 凸集与凸函数运用定义不难验证如下命题:2. 凸集与凸函数2. 凸集与凸函数多面体多面体(polyhedral set)是有限闭半空间的交. (可表为 Axb ).x4x3x2x1x5xy2. 凸集与凸函数多面集 x|Ax0也是凸锥,称为多面锥多面锥。2. 凸集与凸函数由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合K(S)=x|0,xS是包含S的最小凸锥.锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间约定约定: 非空集合非空集合S生成的凸锥生成的凸锥,是指可以表示成是指可以表示成S中有限个中有限个元素的非负线性组合元素的非负线性组合(称为凸
4、锥组合称为凸锥组合)的所有点所构成的的所有点所构成的集合集合,记为记为coneS. 若若S凸凸,则则coneS=K(S) 02. 3 凸集分离定理凸集分离定理2. 凸集与凸函数2. 凸集与凸函数证明:令2. 凸集与凸函数所以为柯西列,必有极限,且由S为闭集知。此极限点必在S中。2. 凸集与凸函数下证明唯一性2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数xpX(i) (x- )(y- )0 对任意 xX.(ii) 令 p=y- , =p p. Txxxyx 证明提纲由此可得2. 凸集与凸函数2. 凸集与凸函数Th2.7表明,S为闭凸集, yS,则y与S可分离。若令clS表示非空集合S的闭包,则当yclS时,定理结论也真。实际上我们有下述定理证明2. 凸集与凸函数推论:设S为Rn 中的非空集合,yS,则存在非零向量p,使对xclS, pT (x-y)02. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数 作为凸集分离定理的应用,下面介绍两个择一定理:Farkas定理和Gordan定理,它们在最优化理论中是很有用的。2. 凸集与凸函数2.4 择一定理择一定理2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数2. 凸集与凸函数