判斷函數(shù)凸性的若干方法

吳菁菁，朱永貴

(中國(guó)傳媒大學(xué)數(shù)據(jù)科學(xué)與智能媒體學(xué)院，北京100024)

1 引言

凸函數(shù)是一類基本函數(shù)，具有非常好的分析學(xué)性質(zhì)，在極值研究、不等式證明、數(shù)學(xué)規(guī)劃、逼近論、變分學(xué)、最優(yōu)控制理論、對(duì)策論等領(lǐng)域有著廣泛的應(yīng)用。本文介紹了判斷多元二次函數(shù)凸性的方法。

2 基本概念

定義1.2.1 凸函數(shù)：設(shè)函數(shù)f：D?Rn→R，其中D為凸集，對(duì)任意的x，y∈D及任意的實(shí)數(shù)λ∈[0，1]都有f(λx+(1-λ)y)≤λf(x)+(1-λ)f(y)，稱f為D上的凸函數(shù)。

定義1.2.2 嚴(yán)格凸函數(shù)：設(shè)函數(shù)f：D?Rn→R，其中D為凸集，對(duì)任意的x，y∈D，x≠y及任意的實(shí)數(shù)λ∈[0，1]都有f(λx+(1-λ)y)<λf(x)+(1-λ)f(y)，稱f為D上的嚴(yán)格凸函數(shù)。

3 定理

定理1.3.1 設(shè)f在凸集D?Rn上一階連續(xù)可微，則f在D上為凸函數(shù)的充要條件是f(x)≥f(x*)+?f(x*)T(x-x*)，?x*，x∈D

證明：

必要性：設(shè)f(x)為凸函數(shù)，根據(jù)凸函數(shù)的定義，對(duì)任意的x*，x∈S及每個(gè)數(shù)λ∈(0，1)，有f(λx+(1-λ)x*)≤λf(x)+(1-λ)f(x*)

從而得出D+f(x*；x-x*)≤f(x)-f(x*)

由于f(x)可微，根據(jù)上述式子，則有?f(x*)T(x-x*)≤f(x)-f(x*)

即f(x)≥f(x*)+?f(x*)T(x-x*)

充分性：設(shè)對(duì)任意的x*，x∈S，有f(x)≥f(x*)+?f(x*)T(x-x*)，令y是x*與x連線上某一點(diǎn)，即對(duì)某一個(gè)λ∈(0，1)，有y=λx+(1-λ)x*。由于S為凸集，則y∈S，根據(jù)假設(shè)，對(duì)于點(diǎn)x*，x，y∈S，下列兩式成立：

f(x*)≥f(y)+?f(y)T(x*-y)，f(x)≥f(y)+?f(y)T(x-y)，合并化簡(jiǎn)得到：

(1-λ)f(x*)+λf(x)≥f(y)+?f(y)T[(1-λ)(x*-y)+λ(x-y)]

=f(y)+?f(y)T[λx+(1-λ)x*-y]

=f(y)

即f(y)≤λf(x)+(1-λ)f(x*)

上式即f(λx+(1-λ)x*)≤λf(x)+(1-λ)f(x*)

由凸函數(shù)的定義知f(x)是凸函數(shù)。[2]

定理1.3.2 設(shè)f在凸集D?Rn上一階連續(xù)可微，則f在D上為嚴(yán)格凸函數(shù)的充要條件是當(dāng)x≠y時(shí)成立f(x)>f(x*)+?f(x*)T(x-x*)，?x*，x∈D

證明：

必要條件：設(shè)f(x)是嚴(yán)格凸函數(shù)，自然f(x)也是凸函數(shù)，對(duì)于任意兩個(gè)不同點(diǎn)x*，x∈S，

經(jīng)整理得出：f(x)>f(x*)+?f(x*)T(x-x*)

充分性：設(shè)對(duì)任意的x*，x∈S，有f(x)>f(x*)+?f(x*)T(x-x*)，令y是x*與x連線上某一點(diǎn)，即對(duì)某一個(gè)λ∈(0，1)，有y=λx+(1-λ)x*。由于S為凸集，則y∈S，根據(jù)假設(shè)，對(duì)于點(diǎn)x*，x，y∈S，下列兩式成立：

f(x*)>f(y)+?f(y)T(x*-y)，f(x)>f(y)+?f(y)T(x-y)，合并化簡(jiǎn)得到：

(1-λ)f(x*)+λf(x)>f(y)+?f(y)T[(1-λ)(x*-y)+λ(x-y)]

=f(y)+?f(y)T[λx+(1-λ)x*-y]

=f(y)

即f(y)<λf(x)+(1-λ)f(x*)

上式即f(λx+(1-λ)x*)<λf(x)+(1-λ)f(x*)

由凸函數(shù)的定義知f(x)是嚴(yán)格凸函數(shù)

定理1.3.3 設(shè)n元實(shí)函數(shù)f在凸集D?Rn上二階連續(xù)可微，則f在D上是凸函數(shù)的充要條件是?2f(x)對(duì)一切x∈D為半正定。

定理1.3.4 設(shè)n元實(shí)函數(shù)f在凸集D?Rn上二階連續(xù)可微，則f在D上是嚴(yán)格凸函數(shù)的充分條件是?2f(x)對(duì)一切x∈D為正定。其中?2f(x)為Hesse矩陣。

證明：

4 應(yīng)用

4.1 判斷下列函數(shù)的凸性：f(x)=x12+2x22

方法一：?x，y∈D，D∈Rn，由公式得：f(x)≥f(y)+?f(y)T(x1-y1，x2-y2)T，則

x12+2x22-y12-2y22-2x1y1+2y12-4x2y2+4y22≥0

(x1-y1)2+2(x2-y2)2≥0

因此得到f(x)為凸函數(shù)

方法二：?f(x)=[2x1，4x2]T

則λ1=2，λ2=4，可得?2f(x)為正定矩陣，因此f(x)為凸函數(shù)。

4.2 判斷下列函數(shù)的凸性：f(x)=x12+x22+…xn2

?x，y∈D，D∈Rn，由公式得：f(x)≥f(y)+?f(y)T(x1-y1，…，xn-yn)T

x12+x22+…xn2≥y12+y22+…+yn2+2x1y1-2y12+…+2xnyn-2yn2

(x1-y1)2+…+(xn-yn)2≥0

因此得到f(x)為凸函數(shù)。

4.3 判斷下列函數(shù)的凸性：f(x)=x12+2x22+5x1x2

方法一：?x，y∈D，D∈Rn，由公式得f(x)≥f(y)+?f(y)T(x1-y1，x2-y2)T，則

x12+2x22+5x1x2≥y12+2y22+5y1y2+(2y1+5y2)(x1-y1)+(4y2+5y1)(x2-y2)x12+2x22+y12+2y22+5x1x2-2x1y1-5x2y1-5x1y2-4x2y2+5y1y2≥0

當(dāng)x1=0，y1=0，x2=1，y2=-2時(shí)，代入上述不等式左端，所的值小于0，不滿足上述的不等式，因此得到f(x)為非凸函數(shù)。

方法二：?f(x)=(2x1+5x2，4x2+5x1)

4.4 判斷下列函數(shù)的凸性：

f(x)=x12+x22+…+xn2+x1x2+…+x1xn+x2x3+…+x2xn+…+xn-1xn

證明：?x，y∈D，D∈Rn，由公式得f(x)≥f(y)+?f(y)T(x1-y1，…，xn-yn)T，則

5 結(jié)論

若f(x)=ax12+bx22+…+mxn2，其中a，b，…，m∈R，n≥1，則f(x)為凸函數(shù)。

若f(x)=ax12+bx22+…+mxn2+lx1x2+…+px1xn+…+qxn-1xn

其中a，b，…，m，…，l，…，p，…，q∈R，n≥1，則f(x)為非凸函數(shù)。