凸分析教学ppt课件

《凸分析教学ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化理论与算法§2，凸分析与凸函数2.凸集与凸函数2.1凸集与锥2.凸集与凸函数2.凸集与凸函数x0xx-x0px0xx-x0p2.凸集与凸函数运用定义不难验证如下命题：2.凸集与凸函数2.凸集与凸函数多面体(polyhedralset)是有限闭半空间的交.(可表为Axb).x4x3x2x1x5xy2.凸集与凸函数多面集{x

2、Ax0}也是凸锥，称为多面锥。2.凸集与凸函数由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合K(S)={λx

3、λ>0,xS}是包含S的

4、最小凸锥.锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间约定:非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合(称为凸锥组合)的所有点所构成的集合,记为coneS.若S凸,则coneS=K(S)∪{0}2.凸集与凸函数Df2.5非空凸集中的点x称为极点,若x=x1+(1-)x2,(0,1),x1,x2S,则x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一点都可表成极点的凸组合.2.凸集与凸函数Def2

5、.6.设非空凸集SRn,Rn中向量d0称为S的一个回收方向(方向),若对每一xS,R(x.d)={x+d

6、0}S.S的所有方向构成的尖锥称为S的回收锥,记为0+S方向d1和d2称为S的两个不同的方向,若对任意>0,都有d1d2；方向d称为S的极方向extremedirection,若d=d1+(1-)d2,(0,1),d1,d2是S的两个方向,则有d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合x0x0ddd2.凸集与凸函数2.凸集与凸函数表示定理Th2.4若多面体P=

7、{xRn

8、Axb},r(A)=n则:(1)P的极点集是非空的有限集合,记为{x}kkK则j(2)记P的极方向集为{d}jJ(约定P不存在极方向时J=)(3)指标集J是空集当且仅当P是有界集合,即多胞形.2.凸集与凸函数表示定理直观描述:设X为非空多面体.则存在有限个极点x1,…,xk,k>0.进一步,存在有限个极方向d1,…,dl,l>0当且仅当X无界.进而,xX的充要条件是x可以表为x1,…,xk的凸组合和d1,…,dl的非负线性组合(凸锥组合).xyx1x2x3d1d20推论2.1若多面体

9、S={x

10、Ax=b,x≥0}非空,则S必有极点.2.2凸集分离定理2.凸集与凸函数2.凸集与凸函数证明：令2.凸集与凸函数所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。2.凸集与凸函数下证明唯一性2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数xpX(i)(x-)(y-)0对任意xX.(ii)令p=y-，=pp.Txxxyx证明提纲由此可得2.凸集与凸函数2.凸集与凸函数Th2.7表明，S为闭凸集，yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际

11、上我们有下述定理证明2.凸集与凸函数推论2.2：设S为Rn中的非空集合，yS,则存在非零向量p，使对xclS,pT(x-y)02.凸集与凸函数2.凸集与凸函数2.凸集与凸函数作为凸集分离定理的应用，下面介绍两个择一定理：Farkas定理和Gordan定理，它们在最优化理论中是很有用的。2.凸集与凸函数2.3择一定理2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数2.4凸函数Df2.10设SRn是非空凸集

12、,函数f:SR,若对任意x1,x2∈S,和每一λ∈(0,1)都有f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)则称f是S上的凸函数.若上面的不等式对于xy严格成立,则称f是S上的严格凸函数.若-f是S上的凸函数,则称f是S上的凹函数.若-f是S上的严格凸函数,则称f是S上的严格凹函数.2.4.1基本性质2.凸集与凸函数Th2.13设f是一凸函数，则对任意的xRn和d(0)Rn，f在x处沿方向d的方向导数存在。2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数命题2.3设f是定义在凸

13、集S上的凸函数，则(1)所有凸函数f的集合关于凸锥组合运算是封闭的,即(a)实数0，则f也是定义在S上的凸函数(b)设f1和f2是定义在凸集S上的凸函数，则f1+f2也是定义在S上的凸函数2.凸集与凸函数(2)函数f在开集intS内是连续的.(3)函数f的水平集L(f,)={x

14、xS,f(x)≤},R和上镜图epi(f)={(x,y)

15、xS,yR,y≥f(x)}都是凸集2.凸集与凸函数设S为R