凸函數定義

02-凸函數

02-凸函數

?錄

?、基本性質和例?

[凸函數]?個函數f:R

n

→R是凸的，如果定義域domf是凸集，并且對于所有x,y∈f,θ≤1，我們有f(θx+(1?θ)y)≤θf(x)+(1?θ)f(y).

注：如果不能理解，從?維?度去理解

?何解釋：點(x,f(x))和(y,f(y))之間的線段在f對應的圖像上?。

函數f是嚴格凸的，如果以上不等式在x≠y，且0<θ<1時也成?.

函數f是凹的，當?f是凸的，嚴格凹，當?f是嚴格凸的。

仿射函數既是凸的也是凹的，反過來，既凹?凸的函數是仿射的。

?個函數是凸的當且僅當對任意x∈domf和任意v，函數g(t)=f(x+tv)是凸的，{t|x+tv∈domf}.注：其實只是修改了?變量的表?，?由于?變量的集合是凸集，線性表?

后仍然是凸集

[擴展值]將凸函數擴展到整個R

n

，通常令它在定義域之外取∞。如果f是凸函數那么它的拓展為

?

f

:R

n

→R∪{∞},

?

f

(x)=

f(x)x∈domf

∞x?domf

[?階條件]令函數f是可微的（也就是它的梯度?f在開集domf的每個點上都存在）。那么f是凸的，當且僅當domf是凸的，并且對所有的x,y∈domf有：

f(y)≥f(x)+?f(x)T

(y?x).

注：其實同樣可以從?維?度的考慮，??就是dy，也就是函數圖像永遠在某?點的切上上，同時f(x)+?f(x)

T

(y?x)相當于f在x的?階泰勒近似，如果你對泰勒展開公式熟悉，更

好理解，因為泰勒展開是?窮階的，只不過此處做了省略

在每個點上，函數圖像都?于在該點的切線。

解釋：y的仿射函數f(x)+?f(x)

T(y?x)是f在靠近x處的?階泰勒近似。上述不等式表達了這個?階泰勒近似是函數的全局下限（global

underestimator），反過來，如果函數的?階泰勒近似總是函數的全局下限，那么這個函數是凸的。

如果?f(x)=0,那么對于所有y∈domf，有f(y)≥f(x)，也就是在x處f取到全局最?值（xisaglobalminimizeroff）。

f是嚴格凸的，當且僅當domf是凸的，且對于所有x,y∈domf,x≠y有f(y)>f(x)+?f(x)T

(y?x).

f是凹的，當且僅當domf是凸的，并且f(y)≤f(x)+?f(x)T

(y?x),?x,y∈domf.

[?階條件]設函數f是?階可微的，也就是它在開集domf的每個點上都存在?階導數?

2f。那么f是凸的，當且僅當它的?階導數是半正定的：

注：同樣在?維?度理解，?階導?于0，則?階導單調遞增，則在?階導為0的左邊是?于0的，右邊?于0的，也就是說原函數在?階導為0的左邊是單調遞減的，在右邊是

單調遞增的，凸

?x∈domf,?

2f(x)?0.

?何解釋：函數圖像在每個定義域的每個點上都有正的曲率(curvature)。

函數f是凹的，當且僅當domf是凸的，并且?

2f(x)?0,?x∈domf

如果?x∈domf,?

2f(x)?0，那么f是嚴格凸的。反過來不成?，例如f(x)=x4是嚴格凸的，但是在x=0處?階導數為0.

[例]

注：以下判斷，簡單的函數可以畫圖確定，復雜的可以通過求?階導確定

在R上：

eax

,?a∈R,在R上凸。

xa

,當a≥1或a≤0，在R

++

上凸，當0≤a≤1時凹。

|x|

p

,p≥1，在R上凸。

logx，在R

++

上凸。

負熵xlogx，在R

+

和R

++

上凸。

在R

n

上：

范數，凸

最?值函數，凸

Quadratic-over-linear函數：f(x,y)=x2/y,domf=R×R

++

={(x,y)∈R

n

|y>0}，凸。

{

Processingmath:69%

f(x)=log(ex

1+...+e

x

n)，凸

?何平均f(x)=(∏

n

i=1

x

i

)1/n，在R

n

++

上凹。

f(X)=logdetX，在S

n

++

上凹。

[下?平集sublevelt]函數f:R

n

→R的?個α-下?平集是

注：下?平集其實就是對函數做了?個?平切割，或者說對定義域做了切割

C

α

={x∈domf|f(x)≤α}.

凸函數的下?平集是凸集，對于所有的α。反過來不對，例如f(x)=?e

x

在R上不是凸的，但是它的所有下?平集都是凸集。

凹函數的下?平集是凸集。

[上境圖epigraph]?個函數f:R

n

→R的圖像是{(x,f(x))|x∈domf}.它是R

n+1

的?集。定義函數f的

上境圖:epif={(x,t)|x∈domf,f(x)≤t}.

下境圖：hypof={(x,t)|t≤f(x)}.

注：上、下境圖，其實就是對函數做了?個?平切割。有可能說凸函數的下境圖是?個凸集，但是這種說法沒有意義，因為上、下境圖的?平切割是沒有固定值的

函數是凸的當且僅當它的上境圖是?個凸集。

函數是凹的當且僅當它的下境圖是?個凸集。

[Jenn不等式]基本不等式f(θx+(1?θ)y)≤θf(x)+(1?θ)f(y)有時被叫做Jenn不等式。

注：Jenn不等式其實就是凸函數的定義

它可以拓展到多個點的凸組合：

如果f是凸的，x

1

,...,x

k

∈domf,θ

1

,...,θ

k

≥0,θ

1

+...+θ

k

=1那么

f(θ

1

x

1

+...+θ

k

x

k

)≤θ

1

f(x

1

)+...+θ

k

f(x

k

).

還可以拓展到?限，積分和期望：

積分：如果p(x)≥0在S?domf上，∫

S

p(x)dx=1，那么f(∫

S

p(x)dx)≤∫

S

f(x)p(x)dx.

期望：如果x是隨機變量x∈domf，且f是凸函數，那么有f(Ex)≤Ef(x).

?、保留凸性的運算

注：以下保凸運算其實可以使?定義，也就是?Jenn不等式證明，注意保留的是凸函數的性質，?不是保留了凸集的性質，不要和凸集的概念搞混了

[?負加權和]如果f

1

,...,f

m

是凸函數，他們的集合是?個凸錐——凸函數的?負加權和f=w

1

f

1

+...+w

m

f

m

，(w

1

,...,w

m

≥0)是凸的。

注：?負加權和其實可以看做是多個做?負伸縮的凸函數進?了加和

還可以拓展到積分：如果f(x,y)對于x是凸的，對于每個y∈A，且w(y)geq0,?y∈A，那么函數g(x)=∫

A

w(y)f(x,y)dy對于x是凸的。

[與仿射函數的復合]令f:R

n

→R,A∈R

n×m

,b∈R。定義g:R

m

→R為

g(x)=f(Ax+b),domg={a|Ax+b∈domf}.

那么如果f是凸函數，g也是凸函數。

[逐點最?pointwimaximum]如果f

1

,f

2

是凸函數，那么他們的逐點最?f，定義為

f(x)=max{f

1

(x),f

2

(x)},定義域domf=domf

1

∩domf

2

也是凸集。可以拓展到多個凸函數的逐點最?。

[逐點上確界pointwisupremum]如果對于每個y∈A,f(x,y)關于x是凸的，那么函數

g(x)=

sup

y∈Af(x,y)

關于x是凸的。g的定義域是

domg={x|(x,y)∈domf,?y∈A,

sup

y∈Af(x,y)<∞}.

類似地，?組凹函數的逐點下確界是凹函數。

epig=?

y∈A

epif(?,y).

[最?化]如果f關于(x,y)是凸函數，并且C是?空凸集，那么函數

g(x)=

inf

g∈Cf(x,y)

是關于x的凸函數，對于所有的x有g(x)>?∞的定義域是domf到x軸的投影：

domg={x|(x,y)∈domf,forsomey∈C}.

[函數的透視]函數f:R

n

→R，f的透視函數為

g:Rn+1

→R，g(x,t)=tf(x/t)，

domg={(x,t)|x/t∈domf,t>0}

透視運算保存凸性：如果函數f是凸的，那么它的透視函數g也是凸的；如果f是凹的，那么g也是凹的。

三、共軛函數

[函數的共軛conjugate]令f:R

n

→R函數f?:R

n

→R定義為

f?(y)=

sup

x∈domf(y

Tx?f(x)),叫做函數f的共軛。

注：共軛函數的本質，其實就是通過?階導，對求x的最?值問題轉化為了求解截距最?值問題，如果我們把共軛函數寫成這樣g(x

0

)=?x

0

?f

?x

(x

0

)+f(x

0

),x

0

∈domf，這樣看是不是

親切很多，其實就是切線截距公式，?前?的

sup

x∈domf

就是求最?值咯

共軛函數的定義域由使得上述上確界有限的y,y∈R

n

組成。也就是說在domf上差y

Tx?f(x)是有界的。如圖：

共軛函數f

?是凸的，因為它是關于y的凸函數的逐點上確界，這?點為真不論f是否是凸的。

[Fenchel不等式]由共軛函數的定義，我們有

f(x)+f?(y)≥x

Ty,?x,y，叫做Fenchel不等式。

例如對于f(x)=(1/2)x

TQx,Q∈S

n

++

有xTy≤(1/2)xTQx+(1/2)yTQ?1y.

[共軛的共軛]如果函數f是凸且閉的，那么f

??=f.

[可微函數]可微函數f的共軛，也叫做f的Legendre變換。令f是凸且可微的，domf=R

n

，任意使y

Tx?f(x)取最?值的x?

都滿?y=?f(x

?)。

反過來如果x

?

滿?y=?f(x

?)，那么x?

使得y

Tx?f(x)最?化。因此如果y=?f(x?)我們有：

f?(y)=x?T?f(x?)?f(x?).注：這?就講到了y

T

其實就是?階導

這允許我們能為任何y通過得到f

?(y)來解出梯度?程y=?f(z)。

另?種表?，令z∈R

n

是任意的，定義y=?f(z),那么有f?(y)=z

T

?f(z)?f(z).

注：下?就是共軛函數的?些特殊性質咯

[伸縮變換，與仿射變換的復合]對于a>0,b∈R，函數g(x)=af(x)+b的共軛是

g?(y)=af?(A?1y)?bTA?Ty.定義域domg?=A

Tdomf?.

[獨?函數的和]如果f(u,v)=f

1

(u)+f

2

(v)，f

1

,f

2

都是凸函數，且有共軛f

?

1

,f?

2

，那么f

?(w,z)=f?

1

(w)+f?

2

(z).

也就是，獨?凸函數的和的共軛，是函數的共軛的和。

四、擬凸函數

[擬凸Quasiconvex]函數f:R

n

→R是擬凸的，如果它的定義域和所有下?平集S

α

={x∈domf|f(x)≤α},α∈R都是凸的。

注：這?需要注意的是下?平集是凸集，?不是凸函數，其實就是利?了下境圖的概念去理解，就很好理解，就是?個函數可能不是凸，但是它的最?值在凸的那?部分，那我做個?

平切割只要凸的那?部分就好了

?個函數是擬凹（quasiconcave）的，如果?f是擬凸的，也就是每個上?平集{x|f(x)≥α}是凸的。

如果?個函數既擬凸?擬凹，那么叫做擬線性（quasilinear）。如果?個函數是擬線性的那么它的定義域和每個下?平集{x|f(x)=α}都是凸的.

[基本性質---不等式]凸和擬凸有很多對應的性質，例如Jen不等式的擬凸版本：?個函數f是擬凸的，當且僅當domf是凸的，且對任意x，0≤θ≤1有

f(θx+(1?θ)y)≤max{f(x),f(y)}.

注：擬凸函數的Jenn不等式就是說明了函數被函數兩端的最?值控制著

也就是定義域某?段上的函數值，不超過這段兩端的函數值的最?值，如圖：

[R上的擬凸函數]考慮連續函數f:R∈R是擬凸的，當且僅當滿?以下?少?個條件：

f是?減的

f是?增的

存在?個點c∈domf使得對于t≤c(t∈domf)，f是?增的，且當t≥c(t∈domf)，f是?減的。

c是?個全局最?點：

[可微擬凸函數---?階條件]令f:R

n

→R是可微的，那么f是擬凸的當且僅當domf是凸的，并且?x,y∈domf有

f(y)≤f(x)??f(x)T

(y?x)≤0.

注：這個?階條件就是規定了y?x和?f(x)的夾?為鈍?，從下圖可以看出，也就是說y的等?線?定在x的等?線之內，也就是說明了f(y)≤f(x)

[可微擬凸函數---?階條件]令f是?次可微的，如果f是擬凸的，那么?x∈domf,y∈R

n

有

yT

?f(x)=0?y

T

?

2f(x)y≥0.

對于R上的擬凸函數f，條件簡化為f

′(x)=0?f″注：也就是說在斜率為0的坡的任意點上，?階導數都是?負的。

[保留擬凸性的運算]

?負加權最?值：f=max{w_1f_1,...,w_mf_m}，w_igeq0,f_i是擬凸函數。這個性質可以推?到逐點上確界。

復合：如果g:R^nrightarrowR是擬凸函數，h:RrightarrowR是?減的，那么f=hcircg是擬凸的。擬凸函數和仿射函數或線性-分數函數的復合也是?個擬凸函數。

最?化：f(x,y)是擬凸函數，C是?個凸集，那么函數g(x)=undert{yinC}{inf}f(x,y)是擬凸的。

[??族凸函數表?]?凸函數的不等式來表?擬凸函數f的下?平集。找?族凸函數phi_t:R^nrightarrowR,tinR滿?f(x)leqtLeftrightarrowphi_t(x)leq0.

也就是，擬凸函數f的t-下?平集是凸函數phi_t的0-下?平集。

五、對數凹/對數凸函數

注：個?理解，因為對數凸不能證明什么，對數凸只是在某些情況讓?個函數更易于進?優化，例如擬凸函數f=e^{x^2}，對數之后就是凸函數logf=-x^2，讓?個擬凸函數變成

凸函數，性質更好

[對數凹/凸log-concave/log-convex]函數f:R^nrightarrowR是對數凹的，如果f(x)>0,forallxindomf是凹的。

f是對數凸的當且僅當1/f是對數凹的。

允許f取0，log,f(x)=-infty，此時f是對數凹的，如果拓展值函數log,f是凹的。

[?不等式表?]函數f:R^nrightarrowR帶有凸定義域，并且f(x)>0,forallxindomf有：

log(f(thetax+(1-theta)y))geqlog(f(x)^{theta}f(y)^{1-theta})=f(thetax+(1-theta)y)geqlogf(x)^{theta}f(y)^{1-theta}.

注：從變異的Jenn不等式可以看出，其實對數凸就是對Jenn不等式做了對數變化

特別地，對數凹函數在兩點的中點上的值，?于等于兩點上函數值的?何平均數。

[?次可微的對數凹/對數凸函數]令f是?次可微的，domf是凸集，那么有

nabla^2logf(x)=frac{1}{f(x)}nabla^2f(x)-frac{1}{f(x)^2}nablaf(x)nablaf(x)^T.

f是對數凸的，當且僅當forallxindomf有：

f(x)nabla^2f(x)succeqnablaf(x)nablaf(x)^T.

f是對數凹的，當且僅當forallxindomf有：

f(x)nabla^2f(x)preceqnablaf(x)nablaf(x)^T.

[加法，乘法，積分]對數凸性和對數凹性對于加法和正標量乘法封閉。

如果f(x,y)對于所有的yinC關于x對數凸,那么g(x)=int_Cf(x,y)dy是對數凸的

[對數凹函數的積分]在某些特殊情況中積分保留對數凹性。如果f:R^ntimesR^mrightarrowR是對數凹的，那么g(x)=intf(x,y)dy是關于x的對數凹函數。

這說明對數凹性在卷積下封閉，也就是如果f,g是R^n上的對數凹函數，那么卷積(f*g)(x)=intf(x-y)g(y)dy也是對數凹函數。

六、關于?義不等關系的凸性

注：?義不等式的凸性，其實就是把Jenn不等式擴展到錐上定義了

單調性和凸性的推?。

[單調性]令KsubteqR^n是?個正常錐(propercone)，有對應的?義不等關系preceq_K。

?個函數f:R^nrightarrowR叫做K-?減的，如果

xpreceq_KyRightarrowf(x)leqf(y).

f是K-增的，如果

xprec_Ky,xneyRightarrowf(x)

類似可以定義K-?增函數，和K-減函數。

[單調性的梯度條件]?個定義域是凸集的可微函數f，是K-?增的，當且僅當對于所有的xindomf有nablaf(x)succeq_{K^*}0.

更嚴格的情況，如果nablaf(x)succ_{K^*}0對于所有xindomf成?，那么說f是K-增的。

[凸性]令KsubteqR^m是?個正常錐，有對應的?義不等關系preceq_K。

函數f:R^nrightarrowR^m是K-凸的，當且僅當對于所有x,y,0leqthetaleq1有

f(thetax+(1-theta)y)preceq_Kthetaf(x)+(1-theta)f(y).

函數f是嚴格K-凸的，如果對于所有xney,0

f(thetax+(1-theta)y)prec_Kthetaf(x)+(1-theta)f(y).

[K-凸的對偶刻畫]?個函數f是K-凸的當且僅當對于每個wsucceq_{K^*}0，實值函數w^Tf是凸的。f是嚴格K-凸的當且僅當對于每個?零wsucceq_{K^*}0函數w^Tf

是嚴格凸的。

[可微K-凸函數]?個可微函數f是K-凸的當且僅當它的定義域是凸集，并且對于所有的x,yindomf有

f(y)succeq_Kf(x)+Df(x)(y-x).

此處Df(x)inR^{mtimesn}是函數f關于x的導數或Jacobian矩陣。

函數f是嚴格K-凸的，當且僅當對于所有x,yindomf,xney有

f(y)succ_Kf(x)+Df(x)(y-x).

[復合定理compositiontheorem]凸函數的?減凸函數是凸的。如果g:R^nrightarrowR^p是K-凸的，h:R^prightarrowR是凸的，且h的值拓展widetilde{h}是K-?

減的，那么hcircg是凸的。

參考?獻：StephenBoyd,LievenVandenberghe:ConvexOptimization