《凸集与凸函数.ppt》由会员分享，可在线阅读，更多相关《凸集与凸函数.ppt（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 给定向量p(0)Rn,R,则
2、是Rn中的一个超平面.反之,Rn任一超平面都可表 成上式的形式,且在相差一个非零常数的意义下, (p,)是唯一的. 2. 凸集与凸函数 可验证,仿射集的交集仍是仿射集 Df2.3 给定Rn中集合S,包含S的所有仿射集的交集, 即包含S的最小仿射集称为S的仿射包,记为affS 2. 凸集与凸函数 Df2.1 Rn中任一集合S的维数定义为它的仿射包 affS的维数,即包含S的仿射集的最小维数. 2. 凸集与凸函数 命题2.1 下述断言相互等价. 2. 凸集与凸函数 2. 凸集与凸函数 2.2 凸集与锥 2. 凸集与凸函数 2. 凸集与凸函数 x0 x x-x0 p x0 x x-x0 p 2. 凸
3、集与凸函数 运用定义不难验证如下命题： 2. 凸集与凸函数 2. 凸集与凸函数 多面体(polyhedral set)是有限闭半空间的交. (可表为 Axb ). x4 x3 x2 x1 x5 x y 2. 凸集与凸函数 多面集 x|Ax0也是凸锥，称为多面锥。 2. 凸集与凸函数 由定义可知,锥关于正的数乘运算封闭,凸锥关于加法 和正的数乘封闭,一般的,对于凸集S,集合 K(S)=x|0,xS 是包含S的最小凸锥. 锥C称为尖锥,若0S.尖锥称为突出的,若它不包含 一维子空间 约定: 非空集合S生成的凸锥,是指可以表示成S中有限个 元素的非负线性组合(称为凸锥组合)的所有点所构成的 集合,记
4、为coneS. 若S凸,则 coneS=K(S) 0 2. 3 凸集分离定理 2. 凸集与凸函数 2. 凸集与凸函数 证明：令 2. 凸集与凸函数 所以为柯西列，必有极限,且由S为闭集知。 此极限点必在S中。 2. 凸集与凸函数 下证明唯一性 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 x p X (i) (x- )(y- )0 对任意 xX. (ii) 令 p=y- ， =p p. T xx x y x 证明提纲 由此可得 2. 凸集与凸函数 2. 凸集与凸函数 Th2.7表明，S为闭凸集， yS，则y与S可分离 。若令clS表示非空集合S的闭包，则当yclS时 ，定理结论也真。实际上我们有下述定理 证明 2. 凸集与凸函数 推论：设S为Rn 中的非空集合，yS,则存在 非零向量p，使对xclS, pT (x-y)0 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 作为凸集分离定理的应用，下面介绍两个择一 定理：Farkas定理和Gordan定理，它们在最优 化理论中是很有用的。 2. 凸集与凸函数 2.4 择一定理 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数 2. 凸集与凸函数