本文主要是介绍漫步凸分析四——凸函数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
令函数 f 的值域是实数或
叫做 f 的上境图(epigraph),用epi
凸函数
这是 Rn 中的一个凸集,因为它是凸集epi f 在线性变换下的像(定理3.4)。它的维数就是
我们不想只考虑有效定义域为某个确定值
本文选择第二种方法,因此当提到凸函数时,除非特别说明,否则这就意味着这个凸函数是定义在整个 Rn 空间上的,并且可能取无穷大。这个方法有个好处,那就是可以压制有效定义域带来的麻烦,例如当凸函数 f 已经通过某种形式构造出来后,同样的形式可以用于有效定义域上,因为他们指定了
然而,这里采用的方法会产生涉及
组合 ∞−∞,−∞+∞ 没有定义,应该避免,在这些法则下,下面熟悉的算数法则依然成立:
当然前提是 α+β 没有一个会产生 ∞−∞ (或者 −∞+∞ )。
避免 ∞−∞ 自然要求我们要留心,像避免除数出现零。实际中,根据假设给定的计算通常自动排除了无穷大的情况,所以不会出现复杂的情况。
对于凸函数 f ,如果它的上境图是非空的并且不包含垂线,即至少有一个点
不是正常的凸函数就是不正常的(improper)。正常凸函数使我们要研究的对象,但是在许多情况下,正常函数会产生不正常函数并且接纳他们比费力地排除他们要更简便。这里给出一个定义在 R 上不正常凸函数的例子
凸函数有一个重要的插值属性,根据定义, f 是
属于epi f 。换句话说,当
这个条件可以用几种不同的方式表达,下面两种变形是非常有用的。
定理4.1 令 f 是从
成立时,函数 f 在
定理4.2 令 f 是从
成立时,函数 f 在是凸的,其中
另一个有用的变形通过在上境图上应用定理2.2推出来。
定理4.3 (Jensen’s Inequality)令 f 是从
成立时, f 是凸的。
当然,在同样的假设下,凹函数满足反向的不等式,仿射函数满足上面的等式,因此
定理4.1中的不等式经常用来作为从凸集
从下面的定理中我们可以得到一些实数轴上凸函数的经典实例。
定理4.4 令 f 是开区间
证明:首先假设
因为 z−x=λ(y−x),y−z=(1−λ)(y−z) ,所以我们有
上面两个不等式两边分别乘以 (1−λ),λ ,然后相加可得
左边仅仅是 f(z)=f((1−λ)x+λy) ,所以根据定理4.1这就证明了 f 在
因此
因此 f 在
定理4.4将在定理24.1和24.2中进行推广。
下面列举一些 R 上的函数,他们的凸性从定理4.4中可以退出来。
f(x)=eαx,where −∞<α<∞ - f(x)=xp if x≥0,f(x)=∞ if x<0,where 1≤p<∞
- f(x)=−xp if x≥0,f(x)=∞ if x<0,where 0≤p≤1
- f(x)=xp if x>0,f(x)=∞ if x≤0,where−∞<p≤0
- f(x)=(α2−x2)(−1/2) if |x|<α,f(x)=∞ if |x|≥α,where α>0
- f(x)=−logx if x>0,f(x)=∞ if x≤0
对于多维的情况,根据定理4.1可得所有形如
f(x)=⟨x,a⟩+α,a∈Rn,α∈R的函数在 Rn 上是凸的,事实上是仿射的。每个 Rn 上的仿射函数实际上都有这种形式(定理1.5),二次函数
f(x)=12⟨x,Qx⟩+⟨x,a⟩+α其中 Q 是
n×n 的对称矩阵,要想是 Rn 上的凸函数,当且仅当 Q 是半正定的即
⟨z,Qz⟩≤0 for every z∈Rn 下面关于定理4.4的多维版本可以直接得出
定理4.5 令 f 是
Rn 中开集 C 上的二阶连续可导实值函数,那么当且仅当Hessian矩阵
Qx=(qij(x)),qij(x)=∂2f∂ξi∂ξj(ξ1,…,ξn) 对所有 x∈C 是半正定时, f 是凸的。
证明:
f 在 C 上的凸性等价于f 在 C 中每条线段上的凸性,这和函数g(λ)=f(y+λz) 在开实数区间 {λ|y+λz∈C} 的凸性是一样的,其中 y∈C,z∈Rn 。通过简单的计算就得出
g′′(λ)=⟨z,Qxz⟩,x=y+λz因此根据定理4.4得,对于每个 x∈C,z∈Rn ,当且仅当 ⟨z,Qxz⟩≥0 时, g 对于每个
y∈C,z∈Rn 是凸的。 ||在 Rn 上有一个非常有趣的函数,它的凸性可以用定理4.5证明,那就是几何平均的负:
f(x)=f(ξ1,…,ξn){−(ξ1ξ2⋯ξn)1/n+∞ otherwise if ξ1≥0,…,ξn≥0直接计算得
⟨z,Qxz⟩=n−2f(x)[(Σnj=1ζj/ξj)2−nΣnj=1(ζj/ξj)2]
其中 z=(ζ1,…,ζn),x=(ξ1,…,ξn),ξ1>0,…,ξn>0 。 这个量是非负的,因为 f(x)<0 并且对于任意实数 αj
(α1+⋯+αn)2≤n(α21+⋯+α2n)(因为 2αjαk≤α2j+α2k )
Rn 上一个最重要的凸函数时欧几里得范数
|x|=⟨x,x⟩1/2=(ξ21+⋯+ξ2n)1/2当然,在 n=1 时这就是绝对值函数。欧几里得范数的凸性由下面的法则得到
|x+y|≤|x|+|y|,|λx|=λ|x|forλ≥0凸集和凸函数之间有几个非常有用的对应关系,最简单的就是将 Rn 中的每个集合 C 和
C 的指示函数(indicator function) δ(⋅|C) 联系起来,其中
δ(x|C)={0 +∞ if x∈Cif x∉C指示函数的上境图是横截面为 C 的半圆柱,很明显当且仅当
δ(⋅|C) 是 Rn 上的凸函数时, C 才是凸集,指示函数在凸分析中扮演着非常基础的角色,跟其他分析中集合的特征函数一样。Rn 上凸集 C 的支撑函数(support function)δ∗(⋅|C) 定义为
δ∗(x|C)=sup{⟨x,y⟩|y∈C}gauge γ(⋅|C) 定义为
γ(x|C)=inf{λ≥0|x∈λC},C≠∅(欧几里得)距离函数 d(⋅,C) 定义为
d(x,C)=inf{|x−y||y∈C}这些 Rn 上函数的凸性现在可以直接证明,
凸函数通过一种重要的方法可以产生凸集。
定理4.6 对于任意凸函数 f 和任意
α∈[−∞,+∞] ,水平集 {x|f(x)<α} 和 {x|f(x)≤α} 是凸的。证明:对于严格不等式的情况,上述结果可以利用定理4.2,令 β=x 直接得出。 {x|f(x)≤α} 的凸性可以从下面的事实得出,它是所有 μα 的凸集 {x|f(x)<μ} 之交,从几何观点来看就是 {x|f(x)≤α} 是epi f 和
Rn+1 上水平超平面 {(x,μ)|μ=α} 的交集在 Rn 上的投影,所以 {x|f(x)≤α} 可以看成epi f 的水平横截面。|| 推论4.6.1 令 fi 是 Rn 上的凸集并且对于所有 i∈I,αi 是实数,其中 I 是一个任意索引集,那么
C={x|fi(x)≤αi,∀i∈I} 是凸集。
证明:像推论2.1.1。 ||
取 f 为定理4.6中的二次凸函数,我们可以得出满足下面二次不等式
12⟨x,Qx⟩+⟨x,a⟩+α≤0 的点集在 Q 是半正定的时候是凸的(定理4.5),这种形式的集合包括所有实心椭圆体和抛物体,以及像
⟨x,x⟩≤1 的球。定理4.6和推论4.6.1对于非线性不等式组理论非常重要,但是凸性也进入到不等式其他方面的分析,因为各种各样经典的不等式可以看成定理4.3的特殊情况,例如取 f 为
R 上的负对数,如上面的例6。对于正数 x1,…,xm 的凸组合,根据定理4.3我们有
−log(λ1x1+⋯+λmxm)≤−λ1logx1−⋯−λmlogxm两边乘以-1然后取指数得
λ1x1+⋯+λmxm≥xλ11⋯xλmm特别地,当 λ1=⋯=λm=1/m 时,
(x1+⋯+xm)/m≥(x1⋯xm)1/m这就是著名正数的算术平均和几何平均不等式。
有时通过变量的非线性变换,可以将非凸函数变成凸函数,一个非常棒的例子就是 Rn 正象限上的(正)代数函数,它是如下形式的和
g(x)=g(ξ1,⋯,ξn)=βξα1⋯αn1其中 β>0 并且指数 αj 是任意实数。(在30节末尾中一个很重要的应用会出现这种函数)这类的一个特定函数是
f(ξ1,ξ2)=ξ−21+(ξ1ξ2)1/3+2ξ42,ξ1>0,ξ2>0变量代换 ζj=logξj 将通常的形式 g 变成
h(z)=h(ζ1,…,ζn)=βeα1ζ1⋯eαnζn=βe⟨a,z⟩ 其中 a=(α1,…,αn) ,在下一节将会看到 h 以及任何形如
h 函数的和是凸的,注意同样的变量变化可以将集合 {x|g(x)=α} 变成超平面
{z|h(z)=α}={z|⟨a,z⟩=log(α/β)}Rn 上的函数 f ,如果对每个
x ,我们都有
f(λx)=λf(x),0<λ<∞那么就称函数是正齐次的(positively homogeneous)(of degree 1),很明显,正齐次的等价于上境图是 Rn+1 上的锥,除了线性函数外,正齐次图函数的一个例子是 f(x)=|x| 。
定理4.7 从 Rn 到 (−∞,+∞] 的正齐次函数 f 是凸函数,当且仅当对于每个
x∈Rn,y∈Rn ,不等式
f(x+y)≤f(x)+f(y)成立。
证明:根据定理2.6就可得出此结果,因为 f 上的次可加性条件等价于epi
f 对加法是封闭的。 ||推论4.7.1 如果 f 是正齐次正常凸函数,那么当
λ1>0,…,λm>0 时,下式
f(λ1x1+⋯+λmxm)≤λ1f(x1)+⋯+λmf(xm)成立。
推论4.7.2 如果 f 是正齐次正常凸函数,那么对所有
x ,不等式 f(−x)≥−f(x) 成立。证明: f(x)+f(−x)≥f(x−x)=f(0)≥0 。 ||
定理4.8 正齐次正常凸函数 f 在子空间
L 上是线性的,当且仅当对于每个 x∈L ,等式 f(−x)=−f(x) 成立。如果对于 L 中一组基b1,…,bm 的所有向量,等式 f(−bi)=−f(bi) 成立,那么结论依然成立。证明:假设后者成立,那么对于每个 λi∈R ,不仅仅是 λi>0 ,等式 f(λibi)=λif(bi) 成立。对于任意 x=λ1b1+⋯+λmbm∈L ,我们有
f(λ1b1)+⋯+f(λmbm)≥f(x)≥−f(−x)≥−(f(−λ1b1)+⋯+f(−λmbm))=f(λ1b1)+⋯+f(λmbm)(定理4.7和推论4.7.2)那么
f(x)=f(λ1b1)+⋯+f(λmbm)=λ1f(b1)+⋯+λmf(bm)因此 f 在
L 上是线性的并且特别地对于 x∈L,f(−x)=−f(x) 。 ||在13节,某些正齐次凸函数将会表征为凸集的支撑函数,而在15节会表征为凸集(包括范数)的gauge函数,次数 p>1 的正齐次凸函数将会在推论15.3.1和15.3.2中提到。
附:文章PDF版本http://pan.baidu.com/s/1pKGHemJ
这篇关于漫步凸分析四——凸函数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!