凸函数定义

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