Loading [MathJax]/jax/output/HTML-CSS/jax.js

凸函数与凹函数



f:SR,其中S是Rn中的非空凸集,则如果对于所有λ(0,1),都有f(λx1+(1λ)x2)λf(x1)+(1λ)f(x2),则称f(x)在S上是凸函数。

另一方面,设f:SR,其中S是Rn中的非空凸集,则如果对于所有λ(0,1),都有f(λx1+(1λ)x2)λf(x1)+(1λ)f(x2),则称f(x)在S上是凹函数。

f:SR,其中S是Rn中的非空凸集,则如果对于所有λ(0,1),都有f(λx1+(1λ)x2)<λf(x1)+(1λ)f(x2),则称f(x)在S上是严格凸函数。

f:SR,其中S是Rn中的非空凸集,则如果对于所有λ(0,1),都有f(λx1+(1λ)x2)>λf(x1)+(1λ)f(x2),则称f(x)在S上是严格凹函数。

例子

  • 线性函数既是凸函数又是凹函数。

  • f(x)=|x|是一个凸函数。

  • f(x)=1x是一个凸函数。

定理

f1,f2,...,fk:RnR是凸函数。考虑函数f(x)=kj=1αjfj(x),其中αj>0,j=1,2,...k,f(x)是一个凸函数。

证明

因为f1,f2,...fk是凸函数

所以,对于所有λ(0,1)i=1,2,....,k,都有fi(λx1+(1λ)x2)λfi(x1)+(1λ)fi(x2)

考虑函数f(x)

所以,

f(λx1+(1λ)x2)

=kj=1αjfj(λx1+(1λ)x2)kj=1αj[λfj(x1)+(1λ)fj(x2)]

f(λx1+(1λ)x2)λ(kj=1αjfj(x1))+(1λ)(kj=1αjfj(x2))

f(λx1+(1λ)x2)λf(x1)+(1λ)f(x2)

因此,f(x)是一个凸函数。

定理

f(x)Rn中凸集S上的凸函数,则f(x)在S上的局部极小值是全局极小值。

证明

ˆxf(x)的局部极小值,且ˆx不是全局极小值。

因此,存在ˉxS使得f(ˉx)<f(ˆx)

由于ˆx是局部极小值,存在邻域Nε(ˆx)使得对于所有xNε(ˆx)S,都有f(ˆx)f(x)

f(x)是S上的凸函数,因此对于λ(0,1)

我们有f(λˆx+(1λ)ˉx)λf(ˆx)+(1λ)f(ˉx)

f(λˆx+(1λ)ˉx)<λf(ˆx)+(1λ)f(ˆx)

f(λˆx+(1λ)ˉx)<f(ˆx),λ(0,1)

但是对于某个λ接近1但小于1,我们有

λˆx+(1λ)ˉxNε(ˆx)Sf(λˆx+(1λ)ˉx)<f(ˆx)

这与假设矛盾。

因此,ˆx是全局极小值。

上图

设S是Rn中的非空子集,设f:SR,则f的上图,记为epifEf,是Rn+1的一个子集,定义为Ef={(x,α):xS,αR,f(x)α}

下图

设S是Rn中的非空子集,设f:SR,则f的下图,记为hypfHf,是Rn+1的一个子集,定义为Hf={(x,α):xS,αR,f(x)α}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

定理

设S是Rn中的非空凸集,设f:SR,则f是凸函数当且仅当其上图Ef是一个凸集。

证明

设f是一个凸函数。

要证明Ef是一个凸集。

(x1,α1),(x2,α2)Ef,λ(0,1)

要证明λ(x1,α1)+(1λ)(x2,α2)Ef

[λx1+(1λ)x2,λα1+(1λ)α2]Ef

f(x1)α1,f(x2)α2

因此,f(λx1+(1λ)x2)λf(x1)+(1λ)f(x2)

f(λx1+(1λ)x2)λα1+(1λ)α2

逆命题

Ef是一个凸集。

要证明f是凸函数。

即,要证明如果x1,x2S,λ(0,1)

f(λx1+(1λ)x2)λf(x1)+(1λ)f(x2)

x1,x2S,λ(0,1),f(x1),f(x2)R

由于Ef是一个凸集,(λx1+(1λ)x2,λf(x1)+(1λ)f(x2))Ef

因此,f(λx1+(1λ)x2)λf(x1)+(1λ)f(x2)

广告