凸分析教學(xué)課件

最優(yōu)化理論與算法§2，凸分析與凸函數(shù)最優(yōu)化理論與算法2.

凸集與凸函數(shù)2.1凸集與錐2.凸集與凸函數(shù)2.1凸集與錐2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)x0xx-x0px0xx-x0p2.凸集與凸函數(shù)x0xx-x0px0xx-x0p2.

凸集與凸函數(shù)2.凸集與凸函數(shù)運(yùn)用定義不難驗(yàn)證如下命題：2.

凸集與凸函數(shù)運(yùn)用定義不難驗(yàn)證如下命題：2.凸集與凸函數(shù)2.

凸集與凸函數(shù)多面體(polyhedralset)是有限閉半空間的交.(可表為

Axb).x4x3x2x1x5xy2.凸集與凸函數(shù)多面體(polyhedralset)是有2.

凸集與凸函數(shù)2.凸集與凸函數(shù)多面集

{x|Ax0}也是凸錐，稱為多面錐。2.

凸集與凸函數(shù)由定義可知,錐關(guān)于正的數(shù)乘運(yùn)算封閉,凸錐關(guān)于加法和正的數(shù)乘封閉,一般的,對于凸集S,集合K(S)={λx|λ>0,xS}是包含S的最小凸錐.錐C稱為尖錐,若0S.尖錐稱為突出的,若它不包含一維子空間約定:非空集合S生成的凸錐,是指可以表示成S中有限個元素的非負(fù)線性組合(稱為凸錐組合)的所有點(diǎn)所構(gòu)成的集合,記為coneS.若S凸,則coneS=K(S)∪{0}多面集{x|Ax0}也是凸錐，稱為多面錐。2.凸集與凸2.

凸集與凸函數(shù)Df2.5

非空凸集中的點(diǎn)

x

稱為極點(diǎn),若

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

S,則x=x1=x2.換言之,x不能表示成S中兩個不同點(diǎn)的凸組合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一點(diǎn)都可表成極點(diǎn)的凸組合.2.凸集與凸函數(shù)Df2.5非空凸集中的點(diǎn)x稱為極2.

凸集與凸函數(shù)Def2.6.設(shè)非空凸集SRn,Rn中向量d0

稱為S的一個回收方向(方向),

若對每一

xS,

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

}S.S的所有方向構(gòu)成的尖錐稱為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.凸集與凸函數(shù)Def2.6.設(shè)非空凸集SRn,R2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)表示定理Th2.4

若多面體P={xRn|Axb},r(A)=n則:(1)P的極點(diǎn)集是非空的有限集合,記為{x}kkK則j(2)記P的極方向集為2jjhwdtjJ(約定P不存在極方向時J=)(3)指標(biāo)集J是空集當(dāng)且僅當(dāng)P是有界集合,即多胞形.2.凸集與凸函數(shù)表示定理Th2.4若多面體P={xRn2.

凸集與凸函數(shù)表示定理直觀描述:設(shè)X

為非空多面體.則存在有限個極點(diǎn)x1,…,xk,k>0.進(jìn)一步,存在有限個極方向d1,…,dl,l>0

當(dāng)且僅當(dāng)X

無界.進(jìn)而,xX

的充要條件是x

可以表為

x1,…,xk

的凸組合和d1,…,dl的非負(fù)線性組合(凸錐組合).xyx1x2x3d1d20推論2.1

若多面體S={x|Ax=b,x≥0}非空,則S必有極點(diǎn).2.凸集與凸函數(shù)表示定理直觀描述:設(shè)X為非空多面體.2.2凸集分離定理2.

凸集與凸函數(shù)2.2凸集分離定理2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)證明：令2.

凸集與凸函數(shù)證明：令2.凸集與凸函數(shù)所以為柯西列，必有極限,且由S為閉集知。此極限點(diǎn)必在S中。2.

凸集與凸函數(shù)下證明唯一性所以為柯西列，必有極限,且由S為閉集知。此極限點(diǎn)必在S中。22.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)xpX(i)(x-)(y-

)0

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

，

=pp.

Txxxyx

證明提綱2.凸集與凸函數(shù)xpXTxxxyx證明提綱由此可得2.

凸集與凸函數(shù)由此可得2.凸集與凸函數(shù)2.

凸集與凸函數(shù)Th2.7表明，S為閉凸集，yS，則y與S可分離。若令clS表示非空集合S的閉包，則當(dāng)yclS時，定理結(jié)論也真。實(shí)際上我們有下述定理2.凸集與凸函數(shù)Th2.7表明，S為閉凸集，yS，則y證明2.

凸集與凸函數(shù)證明2.凸集與凸函數(shù)推論2.2：設(shè)S為Rn

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

(x-y)02.

凸集與凸函數(shù)推論2.2：設(shè)S為Rn中的非空集合，yS,則存在非零向量2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)

作為凸集分離定理的應(yīng)用，下面介紹兩個擇一定理：Farkas定理和Gordan定理，它們在最優(yōu)化理論中是很有用的。2.

凸集與凸函數(shù)2.3擇一定理作為凸集分離定理的應(yīng)用，下面介紹兩個擇一定理：Farka2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.4凸函數(shù)Df2.10設(shè)SRn是非空凸集,函數(shù)f:SR,若對任意x1,x2∈S,和每一λ∈(0,1)都有

f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)則稱f是S上的凸函數(shù).若上面的不等式對于xy嚴(yán)格成立,則稱f是S上的嚴(yán)格凸函數(shù).

若-f是S上的凸函數(shù),則稱f是S上的凹函數(shù).若-f是S上的嚴(yán)格凸函數(shù),則稱f是S上的嚴(yán)格凹函數(shù).2.4.1基本性質(zhì)2.凸集與凸函數(shù)2.4凸函數(shù)Df2.10設(shè)SRn是2.

凸集與凸函數(shù)2.凸集與凸函數(shù)Th2.13設(shè)f是一凸函數(shù)，則對任意的xRn

和d(0)Rn，f在x處沿方向d的方向?qū)?shù)存在。2.

凸集與凸函數(shù)Th2.13設(shè)f是一凸函數(shù)，則對任意的xRn和d(2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.凸集與凸函數(shù)2.凸集與凸函數(shù)命題2.3設(shè)f是定義在凸集S上的凸函數(shù)，則(1)所有凸函數(shù)f的集合關(guān)于凸錐組合運(yùn)算是封閉的,即(a)實(shí)數(shù)0，則f也是定義在S上的凸函數(shù)(b)設(shè)f1和f2是定義在凸集S上的凸函數(shù)，則f1+f2也是定義在S上的凸函數(shù)2.

凸集與凸函數(shù)(2)函數(shù)f在開集intS內(nèi)是連續(xù)的.(3)函數(shù)f的水平集L(f,)={x|xS,f(x)

≤},R

和上鏡圖epi(f)={(x,y)|xS,yR,y≥f(x)}都是凸集命題2.3設(shè)f是定義在凸集S上的凸函數(shù)，則2.凸集與凸2.

凸集與凸函數(shù)設(shè)S為Rn中的非空凸集,則f(x)是凸的當(dāng)且僅當(dāng)上鏡圖

epif={(x,y)|x∈S,y∈R,y≥f(x)}是凸集對上鏡圖事實(shí)上我們有如下定理2.凸集與凸函數(shù)設(shè)S為Rn中的非空凸集,則f(x)是2.

凸集與凸函數(shù)2.凸集與凸函數(shù)定理2.14設(shè)SRn為一非空凸集，f是定義在S上的凸函數(shù)，則f在S上的局部極小點(diǎn)是整體極小點(diǎn)，且極小點(diǎn)的集合為凸集。2.

凸集與凸函數(shù)定理2.14設(shè)SRn為一非空凸集，f是定義在S上的凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.5.2凸函數(shù)的判別Th2.16.設(shè)S是Rn

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

是可微的函數(shù)則

f(x)

是凸函數(shù)當(dāng)且僅當(dāng)對任意的x*S,我們有f(x)f(x*)+f(x*)(x-x*),

任意

xS.

類似的,f(x)

嚴(yán)格凸當(dāng)且僅當(dāng)對每一x*S,f(x)>

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

任意

xS.2.4.2凸函數(shù)的判別2.凸集與凸函數(shù)2.5.2凸函數(shù)的判別Th2.16.設(shè)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)Th2.16*.設(shè)S是

Rna上的非空開凸集,f(x)為S

到R上的可微函數(shù).則

f(x)

是凸函數(shù)當(dāng)且僅當(dāng)任意的x1,x2

S,有

(f(x2)-f(x1))(x2-x1)0.類似的,f

嚴(yán)格凸當(dāng)且僅當(dāng)對任意相異的x1,x2

S,(f(x2)-f(x1))(x2-x1)>0.

2.凸集與凸函數(shù)Th2.16*.設(shè)S是Rna上2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)Def2.11.設(shè)S是Rn

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

的函數(shù)則

f(x)

在點(diǎn)x*int(S)稱為二次可微的,若存在向量f(x*),和

nn

(Hessian)矩陣

H(x*),及函數(shù):Rn

R

使得對所有的

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

(x-x*)其中l(wèi)im

(x-x*)=0.2x*x*xx*Th2.17設(shè)S是

Rna上的非空開凸集,f(x)為S

到R上的二次可微函數(shù).則(1)

f(x)

是凸函數(shù)當(dāng)且僅當(dāng)S上每一點(diǎn)的Hessian矩陣是半正定的.(2)f(x)

是嚴(yán)格凸函數(shù)當(dāng)且僅當(dāng)S上每一點(diǎn)的Hessian矩陣是正定的.2.凸集與凸函數(shù)Def2.11.設(shè)S是Rn上的凸規(guī)劃2.

凸集與凸函數(shù)凸規(guī)劃2.凸集與凸函數(shù)最優(yōu)化理論與算法§2，凸分析與凸函數(shù)最優(yōu)化理論與算法2.

凸集與凸函數(shù)2.1凸集與錐2.凸集與凸函數(shù)2.1凸集與錐2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)x0xx-x0px0xx-x0p2.凸集與凸函數(shù)x0xx-x0px0xx-x0p2.

凸集與凸函數(shù)2.凸集與凸函數(shù)運(yùn)用定義不難驗(yàn)證如下命題：2.

凸集與凸函數(shù)運(yùn)用定義不難驗(yàn)證如下命題：2.凸集與凸函數(shù)2.

凸集與凸函數(shù)多面體(polyhedralset)是有限閉半空間的交.(可表為

Axb).x4x3x2x1x5xy2.凸集與凸函數(shù)多面體(polyhedralset)是有2.

凸集與凸函數(shù)2.凸集與凸函數(shù)多面集

{x|Ax0}也是凸錐，稱為多面錐。2.

凸集與凸函數(shù)由定義可知,錐關(guān)于正的數(shù)乘運(yùn)算封閉,凸錐關(guān)于加法和正的數(shù)乘封閉,一般的,對于凸集S,集合K(S)={λx|λ>0,xS}是包含S的最小凸錐.錐C稱為尖錐,若0S.尖錐稱為突出的,若它不包含一維子空間約定:非空集合S生成的凸錐,是指可以表示成S中有限個元素的非負(fù)線性組合(稱為凸錐組合)的所有點(diǎn)所構(gòu)成的集合,記為coneS.若S凸,則coneS=K(S)∪{0}多面集{x|Ax0}也是凸錐，稱為多面錐。2.凸集與凸2.

凸集與凸函數(shù)Df2.5

非空凸集中的點(diǎn)

x

稱為極點(diǎn),若

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

S,則x=x1=x2.換言之,x不能表示成S中兩個不同點(diǎn)的凸組合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一點(diǎn)都可表成極點(diǎn)的凸組合.2.凸集與凸函數(shù)Df2.5非空凸集中的點(diǎn)x稱為極2.

凸集與凸函數(shù)Def2.6.設(shè)非空凸集SRn,Rn中向量d0

稱為S的一個回收方向(方向),

若對每一

xS,

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

}S.S的所有方向構(gòu)成的尖錐稱為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.凸集與凸函數(shù)Def2.6.設(shè)非空凸集SRn,R2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)表示定理Th2.4

若多面體P={xRn|Axb},r(A)=n則:(1)P的極點(diǎn)集是非空的有限集合,記為{x}kkK則j(2)記P的極方向集為teqaar5jJ(約定P不存在極方向時J=)(3)指標(biāo)集J是空集當(dāng)且僅當(dāng)P是有界集合,即多胞形.2.凸集與凸函數(shù)表示定理Th2.4若多面體P={xRn2.

凸集與凸函數(shù)表示定理直觀描述:設(shè)X

為非空多面體.則存在有限個極點(diǎn)x1,…,xk,k>0.進(jìn)一步,存在有限個極方向d1,…,dl,l>0

當(dāng)且僅當(dāng)X

無界.進(jìn)而,xX

的充要條件是x

可以表為

x1,…,xk

的凸組合和d1,…,dl的非負(fù)線性組合(凸錐組合).xyx1x2x3d1d20推論2.1

若多面體S={x|Ax=b,x≥0}非空,則S必有極點(diǎn).2.凸集與凸函數(shù)表示定理直觀描述:設(shè)X為非空多面體.2.2凸集分離定理2.

凸集與凸函數(shù)2.2凸集分離定理2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)證明：令2.

凸集與凸函數(shù)證明：令2.凸集與凸函數(shù)所以為柯西列，必有極限,且由S為閉集知。此極限點(diǎn)必在S中。2.

凸集與凸函數(shù)下證明唯一性所以為柯西列，必有極限,且由S為閉集知。此極限點(diǎn)必在S中。22.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)xpX(i)(x-)(y-

)0

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

，

=pp.

Txxxyx

證明提綱2.凸集與凸函數(shù)xpXTxxxyx證明提綱由此可得2.

凸集與凸函數(shù)由此可得2.凸集與凸函數(shù)2.

凸集與凸函數(shù)Th2.7表明，S為閉凸集，yS，則y與S可分離。若令clS表示非空集合S的閉包，則當(dāng)yclS時，定理結(jié)論也真。實(shí)際上我們有下述定理2.凸集與凸函數(shù)Th2.7表明，S為閉凸集，yS，則y證明2.

凸集與凸函數(shù)證明2.凸集與凸函數(shù)推論2.2：設(shè)S為Rn

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

(x-y)02.

凸集與凸函數(shù)推論2.2：設(shè)S為Rn中的非空集合，yS,則存在非零向量2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)

作為凸集分離定理的應(yīng)用，下面介紹兩個擇一定理：Farkas定理和Gordan定理，它們在最優(yōu)化理論中是很有用的。2.

凸集與凸函數(shù)2.3擇一定理作為凸集分離定理的應(yīng)用，下面介紹兩個擇一定理：Farka2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.4凸函數(shù)Df2.10設(shè)SRn是非空凸集,函數(shù)f:SR,若對任意x1,x2∈S,和每一λ∈(0,1)都有

f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)則稱f是S上的凸函數(shù).若上面的不等式對于xy嚴(yán)格成立,則稱f是S上的嚴(yán)格凸函數(shù).

若-f是S上的凸函數(shù),則稱f是S上的凹函數(shù).若-f是S上的嚴(yán)格凸函數(shù),則稱f是S上的嚴(yán)格凹函數(shù).2.4.1基本性質(zhì)2.凸集與凸函數(shù)2.4凸函數(shù)Df2.10設(shè)SRn是2.

凸集與凸函數(shù)2.凸集與凸函數(shù)Th2.13設(shè)f是一凸函數(shù)，則對任意的xRn

和d(0)Rn，f在x處沿方向d的方向?qū)?shù)存在。2.

凸集與凸函數(shù)Th2.13設(shè)f是一凸函數(shù)，則對任意的xRn和d(2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.凸集與凸函數(shù)2.凸集與凸函數(shù)命題2.3設(shè)f是定義在凸集S上的凸函數(shù)，則(1)所有凸函數(shù)f的集合關(guān)于凸錐組合運(yùn)算是封閉的,即(a)實(shí)數(shù)0，則f也是定義在S上的凸函數(shù)(b)設(shè)f1和f2是定義在凸集S上的凸函數(shù)，則f1+f2也是定義在S上的凸函數(shù)2.

凸集與凸函數(shù)(2)函數(shù)f在開集intS內(nèi)是連續(xù)的.(3)函數(shù)f的水平集L(f,)={x|xS,f(x)

≤},R

和上鏡圖epi(f)={(x,y)|xS,yR,y≥f(x)}都是凸集命題2.3設(shè)f是定義在凸集S上的凸函數(shù)，則2.凸集與凸2.

凸集與凸函數(shù)設(shè)S為Rn中的非空凸集,則f(x)是凸的當(dāng)且僅當(dāng)上鏡圖

epif={(x,y)|x∈S,y∈R,y≥f(x)}是凸集對上鏡圖事實(shí)上我們有如下定理2.凸集與凸函數(shù)設(shè)S為Rn中的非空凸集,則f(x)是2.

凸集與凸函數(shù)2.凸集與凸函數(shù)定理2.14設(shè)SRn為一非空凸集，f是定義在S上的凸函數(shù)，則f在S上的局部極小點(diǎn)是整體極小點(diǎn)，且極小點(diǎn)的集合為凸集。2.

凸集與凸函數(shù)定理2.14設(shè)SRn為一非空凸集，f是定義在S上的凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.凸集與凸函數(shù)2.

凸集與凸函數(shù)2.5.2凸函數(shù)的判別Th2.16.設(shè)S是Rn

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

是可微的函數(shù)則

f(x)

是凸函數(shù)當(dāng)且僅當(dāng)對任意的x*S,我們有f(x)f(x*)+f(x*)(x-x*),

任意

xS.

類似的,f(x)

嚴(yán)格凸當(dāng)且僅當(dāng)對每一