最优化理论与算法(二)凸分析课件.ppt

《最优化理论与算法(二)凸分析课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化理论与算法2021/10/812.凸集与凸函数2.1凸集与锥2021/10/822.凸集与凸函数2021/10/832.凸集与凸函数x0xx-x0px0xx-x0p2021/10/842.凸集与凸函数2021/10/85运用定义不难验证如下命题：2.凸集与凸函数2021/10/862.凸集与凸函数多面体(polyhedralset)是有限闭半空间的交.(可表为Axb).x4x3x2x1x5xy2021/10/872.凸集与凸函数2021/10/88多面集{x

2、Ax0}也是凸锥，称为多面锥。2.凸集

3、与凸函数由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合K(S)={λx

4、λ>0,xS}是包含S的最小凸锥.锥C称为尖锥,若0S.约定:非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合(称为凸锥组合)的所有点所构成的集合,记为coneS.若S凸,则coneS=K(S)∪{0}2021/10/892.凸集与凸函数Df2.5非空凸集中的点x称为极点,若x=x1+(1-)x2,(0,1),x1,x2S,则x=x1=x2.换言之,x不能表示成S中

5、两个不同点的凸组合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一点都可表成极点的凸组合.2021/10/8102.凸集与凸函数Def2.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的两

7、个方向,则有d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合x0x0ddd2021/10/8112.凸集与凸函数2021/10/8122.凸集与凸函数2.4凸函数Df2.10设SRn是非空凸集,若对任意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基本性

8、质2021/10/8132.凸集与凸函数2021/10/814Th2.13设f是一凸函数，则对任意的xRn和d(0)Rn，f在x处沿方向d的方向导数存在。2.凸集与凸函数2021/10/815命题2.3设f是定义在凸集S上的凸函数，则(1)所有凸函数f的集合关于凸锥组合运算是封闭的,即(a)实数0，则f也是定义在S上的凸函数(b)设f1和f2是定义在凸集S上的凸函数，则f1+f2也是定义在S上的凸函数2.凸集与凸函数(2)函数f在开集intS内是连续的.(3)函数f的水平集L(f,)={x

9、x

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

11、x∈S,y∈R,y≥f(x)}都是凸集2021/10/8162.凸集与凸函数设S为Rn中的非空凸集,则f(x)是凸的当且仅当上镜图epif={(x,y)

12、x∈S,y∈R,y≥f(x)}是凸集对上镜图事实上我们有如下定理2021/10/8172.凸集与凸函数2.5.2凸函数的判别Th2.16.设S是Rn中的非空开凸集,f(x):SR是可微的函数则f(x)是凸函数当且仅当对任意的x*S,我们有f(x)f(x*)+f(x*)(x-x*),任意

13、xS.类似的,f(x)严格凸当且仅当对每一x*S,f(x)>f(x*)+f(x*)(x-x*),任意xS.2.4.2凸函数的判别2021/10/8182.凸集与凸函数Th2.16*.设S是Rn上的非空开凸集,f(x)为S到R上的可微函数.则f(x)是凸函数当且仅当任意的x1,x2S,有(f(x2)-f(x1))(x2-x1)0.类似的,f严格凸当且仅当对任意相异的x1,x2S,(f(x2)-f(x1))(x2-x1)>0.2021/10/8192.凸集与凸函数Def2.11.设S是Rn

14、上的非空开集,f(x)f(x):SR的函数则f(x)在点x*int(S)称为二次可微的,若存在向量f(x*),和nn(Hessian)矩阵H(x*),及函数:RnR使得对所有的xS,f(x)=f(x*)+f(x*)(x-x*)+0.5(x-x*)H(x*)(x-x*)+

15、

16、x-x*

17、

18、(x-x*)其中lim(x-x*)=0.2x*x*xx*Th2.17设S是Rn上的非空开凸集,f(x)为S到