凸分析教学课件

最优化理论与算法§2，凸分析与凸函数最优化理论与算法2.

凸集与凸函数2.1凸集与锥2.凸集与凸函数2.1凸集与锥2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数x0xx-x0px0xx-x0p2.凸集与凸函数x0xx-x0px0xx-x0p2.

凸集与凸函数2.凸集与凸函数运用定义不难验证如下命题：2.

凸集与凸函数运用定义不难验证如下命题：2.凸集与凸函数2.

凸集与凸函数多面体(polyhedralset)是有限闭半空间的交.(可表为

Axb).x4x3x2x1x5xy2.凸集与凸函数多面体(polyhedralset)是有2.

凸集与凸函数2.凸集与凸函数多面集

{x|Ax0}也是凸锥，称为多面锥。2.

凸集与凸函数由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合K(S)={λx|λ>0,xS}是包含S的最小凸锥.锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间约定:非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合(称为凸锥组合)的所有点所构成的集合,记为coneS.若S凸,则coneS=K(S)∪{0}多面集{x|Ax0}也是凸锥，称为多面锥。2.凸集与凸2.

凸集与凸函数Df2.5

非空凸集中的点

x

称为极点,若

x=x1+(1-)x2,(0,1),x1,x2

S,则x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一点都可表成极点的凸组合.2.凸集与凸函数Df2.5非空凸集中的点x称为极2.

凸集与凸函数Def2.6.设非空凸集SRn,Rn中向量d0

称为S的一个回收方向(方向),

若对每一

xS,

R(x.d)={x+d|0

}S.S的所有方向构成的尖锥称为S的回收锥,记为0+S

方向d1和d2

称为S的两个不同的方向,若对任意>0,都有

d1d2；方向d称为S的极方向extremedirection,若

d=d1+(1-)d2,(0,1),d1

,d2

是S的两个方向,则有

d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合x0x0ddd2.凸集与凸函数Def2.6.设非空凸集SRn,R2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数表示定理Th2.4

若多面体P={xRn|Axb},r(A)=n则:(1)P的极点集是非空的有限集合,记为{x}kkK则j(2)记P的极方向集为{d}jJ(约定P不存在极方向时J=)(3)指标集J是空集当且仅当P是有界集合,即多胞形.2.凸集与凸函数表示定理Th2.4若多面体P={xRn2.

凸集与凸函数表示定理直观描述:设X

为非空多面体.则存在有限个极点x1,…,xk,k>0.进一步,存在有限个极方向d1,…,dl,l>0

当且仅当X

无界.进而,xX

的充要条件是x

可以表为

x1,…,xk

的凸组合和d1,…,dl的非负线性组合(凸锥组合).xyx1x2x3d1d20推论2.1

若多面体S={x|Ax=b,x≥0}非空,则S必有极点.2.凸集与凸函数表示定理直观描述:设X为非空多面体.2.2凸集分离定理2.

凸集与凸函数2.2凸集分离定理2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数证明：令2.

凸集与凸函数证明：令2.凸集与凸函数所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。2.

凸集与凸函数下证明唯一性所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。22.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数xpX(i)(x-)(y-

)0

对任意xX.(ii)令p=y-

，

=pp.

Txxxyx

证明提纲2.凸集与凸函数xpXTxxxyx证明提纲由此可得2.

凸集与凸函数由此可得2.凸集与凸函数2.

凸集与凸函数Th2.7表明，S为闭凸集，yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理2.凸集与凸函数Th2.7表明，S为闭凸集，yS，则y证明2.

凸集与凸函数证明2.凸集与凸函数推论2.2：设S为Rn

中的非空集合，yS,则存在非零向量p，使对xclS,pT

(x-y)02.

凸集与凸函数推论2.2：设S为Rn中的非空集合，yS,则存在非零向量2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数

作为凸集分离定理的应用，下面介绍两个择一定理：Farkas定理和Gordan定理，它们在最优化理论中是很有用的。2.

凸集与凸函数2.3择一定理作为凸集分离定理的应用，下面介绍两个择一定理：Farka2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.4凸函数Df2.10设SRn是非空凸集,函数f:SR,若对任意x1,x2∈S,和每一λ∈(0,1)都有

f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)则称f是S上的凸函数.若上面的不等式对于xy严格成立,则称f是S上的严格凸函数.

若-f是S上的凸函数,则称f是S上的凹函数.若-f是S上的严格凸函数,则称f是S上的严格凹函数.2.4.1基本性质2.凸集与凸函数2.4凸函数Df2.10设SRn是2.

凸集与凸函数2.凸集与凸函数Th2.13设f是一凸函数，则对任意的xRn

和d(0)Rn，f在x处沿方向d的方向导数存在。2.

凸集与凸函数Th2.13设f是一凸函数，则对任意的xRn和d(2.

凸集与凸函数2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数命题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|xS,f(x)

≤},R

和上镜图epi(f)={(x,y)|xS,yR,y≥f(x)}都是凸集命题2.3设f是定义在凸集S上的凸函数，则2.凸集与凸2.

凸集与凸函数设S为Rn中的非空凸集,则f(x)是凸的当且仅当上镜图

epif={(x,y)|x∈S,y∈R,y≥f(x)}是凸集对上镜图事实上我们有如下定理2.凸集与凸函数设S为Rn中的非空凸集,则f(x)是2.

凸集与凸函数2.凸集与凸函数定理2.14设SRn为一非空凸集，f是定义在S上的凸函数，则f在S上的局部极小点是整体极小点，且极小点的集合为凸集。2.

凸集与凸函数定理2.14设SRn为一非空凸集，f是定义在S上的凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.5.2凸函数的判别Th2.16.设S是Rn

中的非空开凸集,f(x):SR

是可微的函数则

f(x)

是凸函数当且仅当对任意的x*S,我们有f(x)f(x*)+f(x*)(x-x*),

任意

xS.

类似的,f(x)

严格凸当且仅当对每一x*S,f(x)>

f(x*)+f(x*)(x-x*),

任意

xS.2.4.2凸函数的判别2.凸集与凸函数2.5.2凸函数的判别Th2.16.设2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数Th2.16*.设S是

Rna上的非空开凸集,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.

2.凸集与凸函数Th2.16*.设S是Rna上2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数Def2.11.设S是Rn

上的非空开集,f(x)f(x):SR

的函数则

f(x)

在点x*int(S)称为二次可微的,若存在向量f(x*),和

nn

(Hessian)矩阵

H(x*),及函数:Rn

R

使得对所有的

xS,f(x)=f(x*)+f(x*)(x-x*)+0.5(x-x*)H(x*)(x-x*)+||x-x*||

(x-x*)其中lim

(x-x*)=0.2x*x*xx*Th2.17设S是

Rna上的非空开凸集,f(x)为S

到R上的二次可微函数.则(1)

f(x)

是凸函数当且仅当S上每一点的Hessian矩阵是半正定的.(2)f(x)

是严格凸函数当且仅当S上每一点的Hessian矩阵是正定的.2.凸集与凸函数Def2.11.设S是Rn上的凸规划2.

凸集与凸函数凸规划2.凸集与凸函数最优化理论与算法§2，凸分析与凸函数最优化理论与算法2.

凸集与凸函数2.1凸集与锥2.凸集与凸函数2.1凸集与锥2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数x0xx-x0px0xx-x0p2.凸集与凸函数x0xx-x0px0xx-x0p2.

凸集与凸函数2.凸集与凸函数运用定义不难验证如下命题：2.

凸集与凸函数运用定义不难验证如下命题：2.凸集与凸函数2.

凸集与凸函数多面体(polyhedralset)是有限闭半空间的交.(可表为

Axb).x4x3x2x1x5xy2.凸集与凸函数多面体(polyhedralset)是有2.

凸集与凸函数2.凸集与凸函数多面集

{x|Ax0}也是凸锥，称为多面锥。2.

凸集与凸函数由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合K(S)={λx|λ>0,xS}是包含S的最小凸锥.锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间约定:非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合(称为凸锥组合)的所有点所构成的集合,记为coneS.若S凸,则coneS=K(S)∪{0}多面集{x|Ax0}也是凸锥，称为多面锥。2.凸集与凸2.

凸集与凸函数Df2.5

非空凸集中的点

x

称为极点,若

x=x1+(1-)x2,(0,1),x1,x2

S,则x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一点都可表成极点的凸组合.2.凸集与凸函数Df2.5非空凸集中的点x称为极2.

凸集与凸函数Def2.6.设非空凸集SRn,Rn中向量d0

称为S的一个回收方向(方向),

若对每一

xS,

R(x.d)={x+d|0

}S.S的所有方向构成的尖锥称为S的回收锥,记为0+S

方向d1和d2

称为S的两个不同的方向,若对任意>0,都有

d1d2；方向d称为S的极方向extremedirection,若

d=d1+(1-)d2,(0,1),d1

,d2

是S的两个方向,则有

d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合x0x0ddd2.凸集与凸函数Def2.6.设非空凸集SRn,R2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数表示定理Th2.4

若多面体P={xRn|Axb},r(A)=n则:(1)P的极点集是非空的有限集合,记为{x}kkK则j(2)记P的极方向集为{d}jJ(约定P不存在极方向时J=)(3)指标集J是空集当且仅当P是有界集合,即多胞形.2.凸集与凸函数表示定理Th2.4若多面体P={xRn2.

凸集与凸函数表示定理直观描述:设X

为非空多面体.则存在有限个极点x1,…,xk,k>0.进一步,存在有限个极方向d1,…,dl,l>0

当且仅当X

无界.进而,xX

的充要条件是x

可以表为

x1,…,xk

的凸组合和d1,…,dl的非负线性组合(凸锥组合).xyx1x2x3d1d20推论2.1

若多面体S={x|Ax=b,x≥0}非空,则S必有极点.2.凸集与凸函数表示定理直观描述:设X为非空多面体.2.2凸集分离定理2.

凸集与凸函数2.2凸集分离定理2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数证明：令2.

凸集与凸函数证明：令2.凸集与凸函数所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。2.

凸集与凸函数下证明唯一性所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。22.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数xpX(i)(x-)(y-

)0

对任意xX.(ii)令p=y-

，

=pp.

Txxxyx

证明提纲2.凸集与凸函数xpXTxxxyx证明提纲由此可得2.

凸集与凸函数由此可得2.凸集与凸函数2.

凸集与凸函数Th2.7表明，S为闭凸集，yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理2.凸集与凸函数Th2.7表明，S为闭凸集，yS，则y证明2.

凸集与凸函数证明2.凸集与凸函数推论2.2：设S为Rn

中的非空集合，yS,则存在非零向量p，使对xclS,pT

(x-y)02.

凸集与凸函数推论2.2：设S为Rn中的非空集合，yS,则存在非零向量2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数

作为凸集分离定理的应用，下面介绍两个择一定理：Farkas定理和Gordan定理，它们在最优化理论中是很有用的。2.

凸集与凸函数2.3择一定理作为凸集分离定理的应用，下面介绍两个择一定理：Farka2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.4凸函数Df2.10设SRn是非空凸集,函数f:SR,若对任意x1,x2∈S,和每一λ∈(0,1)都有

f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)则称f是S上的凸函数.若上面的不等式对于xy严格成立,则称f是S上的严格凸函数.

若-f是S上的凸函数,则称f是S上的凹函数.若-f是S上的严格凸函数,则称f是S上的严格凹函数.2.4.1基本性质2.凸集与凸函数2.4凸函数Df2.10设SRn是2.

凸集与凸函数2.凸集与凸函数Th2.13设f是一凸函数，则对任意的xRn

和d(0)Rn，f在x处沿方向d的方向导数存在。2.

凸集与凸函数Th2.13设f是一凸函数，则对任意的xRn和d(2.

凸集与凸函数2.凸集与凸函数2.凸集与凸函数2.凸集与凸函数命题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|xS,f(x)

≤},R

和上镜图epi(f)={(x,y)|xS,yR,y≥f(x)}都是凸集命题2.3设f是定义在凸集S上的凸函数，则2.凸集与凸2.

凸集与凸函数设S为Rn中的非空凸集,则f(x)是凸的当且仅当上镜图

epif={(x,y)|x∈S,y∈R,y≥f(x)}是凸集对上镜图事实上我们有如下定理2.凸集与凸函数设S为Rn中的非空凸集,则f(x)是2.

凸集与凸函数2.凸集与凸函数定理2.14设SRn为一非空凸集，f是定义在S上的凸函数，则f在S上的局部极小点是整体极小点，且极小点的集合为凸集。2.

凸集与凸函数定理2.14设SRn为一非空凸集，f是定义在S上的凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.凸集与凸函数2.

凸集与凸函数2.5.2凸函数的判别Th2.16.设S是Rn

中的非空开凸集,f(x):SR

是可微的函数则

f(x)

是凸函数当且仅当对任意的x*S,我们有f(x)f(x*)+f(x*)(x-x*),

任意

xS.

类似的,f(x)

严格凸当且仅当对每一