注意,本文内容来自于吴恩达老师cs229课堂笔记的中文翻译项目:https://github.com/Kivy-CN/Stanford-CS-229-CN 中的凸优化部分的内容进行翻译学习。
3. 凸函数
凸优化的一个核心要素是凸函数的概念。
定义 3.1 我们称一个函数f:Rn→R是一个凸函数,需要满足其定义域(记作D(f))是一个凸集,同时给定任意x,y∈D(f)以及θ∈R,0≤θ≤1,满足:
f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)
(译者注:注意这里函数的凸凹性和我们本科《高等数学》上册里面微分中值定理与导数应用章节中曲线的凸凹性是相反的,不过这里定义的凸凹的方向在机器学习中更常见)
直观地,考虑这个定义的方法是如果我们在凸函数的图上取任意两点并在两点之间画一条直线,那么函数在这两点之间的部分就会在这条直线下面。这种情况如图22所示。
2 不要太担心f的定义域是凸集的要求,这个要求仅仅是在技术上保证f(θx+(1−θ)y)有定义(如果定义域D(f)不是凸集,则即使x,y∈D(f),f(θx+(1−θ)y)也有可能没有意义)
如果在定义3.1的基础上增加严格的不等的条件x̸=y和0<θ<1,则可以说一个函数是严格凸函数。如果f是凸函数则我们可以得到−f是凹函数, 同理如果f是严格凸函数则−f是严格凹函数。
3.1 凸性的一阶条件
假设函数f:Rn→R可微(即其梯度3∇xf(x)在函数f的定义域内处处存在)。则f是一个凸函数,只要满足D(f)是一个凸集,同时对所有的x,y∈D(f),有:
3 回忆一下梯度定义为∇xf(x)∈Rn,(∇xf(x))i=∂xi∂f(x)。有关梯度和海森函数的知识,请参阅前面关于线性代数的部分的章节笔记。
f(y)≥f(x)+∇xf(x)T(y−x)
函数f(x)+∇xf(x)T(y−x)称为函数f(x)在点x处的一阶近似(first-order approximation)。 直觉上来说,这个函数可以近似的认为是函数f在点x处的切线。凸性的一阶条件就是阐明了,f是凸函数当且仅当该函数的切线是一个全局下估计(global underestimator)。换句话说,如果我们根据函数的特性在任意一点绘制该函数的切线,那么这条直线上的每一点将低于函数f在相应位置的点。
与凸性的定义类似,当严格不等条件成立时f是严格凸函数,当不等式符号颠倒时f是凹函数,当颠倒的不等式的严格不等条件成立时f是严格凹函数。
3.2 凸性的二阶条件
假设函数f:Rn→R二阶可微(即其海森矩阵4∇x2f(x)在函数f的定义域内处处存在)。则f是一个凸函数,只要满足D(f)是一个凸集,同时对所有的x,y∈D(f),有:
4 回忆一下海森矩阵定义为∇x2f(x)∈Rn×n,(∇x2f(x))ij=∂xi∂xj∂2f(x)
∇x2f(x)⪰0
当符号“⪰”在这里与矩阵结合使用时,指的是正半定矩阵,而不是分量不等式(componentwise inequality)5。在一维中,这等价于二阶导数f′′(x)总是非负的(即函数始终为绝对的非负值(positive non-negative))。
5 与对称矩阵X∈Sn类似,X⪯0代表X是负定矩阵。对于向量不等式来说,有时可以用符号‘≤’和‘≥’代替符号‘⪯’和‘⪰’。尽管这里的符号类似向量的符号,但是意义非常不一样。特别的,矩阵X⪰0并不意味着对于所有矩阵的元素下标i,j都有元素Xij≥0
同样,与凸性的定义以及一阶条件类似,如果海森矩阵是正定的,则函数f是严格凸函数,如果是半负定则函数是凹函数,是负定则函数是严格凹函数。
3.3 Jensen不等式
假设我们从凸函数的基本定义中的不等式开始:
f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)其中0≤θ≤1
使用归纳法,这可以相当容易地扩展到多个点的凸组合:
f(i=1∑kθixi)≤i=1∑kθif(xi)其中i=1∑kθi=1,θi≥0∀i
事实上,这也可以推广到无穷和或积分。在后一种情况下,不等式可以写成:
f(∫p(x)xdx)≤∫p(x)f(x)dx其中∫p(x)xdx=1,p(x)≥0∀i
由于p(x)积分为1,通常把它看作概率密度,在这种情况下,前面的方程可以用期望来表示:
f(E[x])≤E[f(x)]
最后一个不等式叫做Jensen不等式,后面的课上会讲到。6
6 事实上,这四个方程有时都被称为Jensen不等式,因为它们都是等价的。但是,对于这门课,我们将使用该术语来具体指这里给出的最后一个不等式。
3.4 水平集
凸函数产生一种特别重要的凸集称为 α−sublevel集。 给出了凸函数f:Rn→R和一个实数α∈R,α−sublevel集被定义为:
{x∈D(f):f(x)≤α}
换句话说,α−sublevel集是所有满足f(x)≤α的点x的集合。
为了证明这是一个凸集,考虑任意x,y∈D(f),并且f(x)≤α,f(y)≤α,则:
f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)≤θα+(1−θ)α=α
3.5 凸函数判断的实例
我们从几个单变量凸函数的简单例子开始,然后继续讨论多元函数。
-
指数函数是凸函数。有函数f:R→R,任意a∈R使得f(x)=eax。为了证明f是凸函数,我们可以简单的考虑二阶导数f′′(x)=a2eax,对于所有x都是正的。
-
负对数函数是凸函数。函数f:R→R,f(x)=−logx,有定义域D(f)=R++(这里的R++代表严格正实数的集合{x:x>0})。则对于所有的x都满足f′′(x)=1/x2>0。
-
仿射函数。函数f:R→R,f(x)=bTx+c,满足b∈Rn,c∈R。在这种情况下对于所有的x,该函数的海森矩阵∇x2f(x)=0。应为零矩阵即是半正定也是半负定矩阵,因此函数f即是凸函数,也是凹函数。事实上,这种形式的仿射函数是唯一既凸又凹的函数。
-
二次函数。函数f:R→R,f(x)=21xTAx+bTx+c,系数的对称矩阵为A∈Sn,b∈Rn以及c∈R。在先前线性代数笔记中,我们展示了这个函数的海森函数为:
∇x2f(x)=A
因此,函数f的凸性或非凸性完全取决于A是否为半正定矩阵:如果A为半正定,则函数为凸函数(严格凸、凹、严格凹函数同样类比);如果A是不定的矩阵,那么f既不是凸函数也不是凹函数。
注意,平方欧几里得范数f(x)=∥x∥22=xTx是二次函数的一个特例,其中a=I,b=0,c=0,因此它是一个严格凸函数。
-
范数函数是凸函数。函数f:R→R为Rn上的某个范数。然后根据三角不等式和正范数的同质性,对于x,y∈Rn,0≤θ≤1,有:
f(θx+(1−θ)y)≤f(θx)+f((1−θ)y)=θf(x)+(1−θ)f(y)
这是一个凸函数的例子,由于范数不是处处可微的(例如,1范数,∥x∥1=∑i=1n∣xi∣,在任意xi=0的点上都是不可微的),因此无法根据二阶或一阶条件证明凸性。
-
凸函数的非负加权和是凸函数。令f1,f2,…,fk是凸函数,并且有w1,w2,…,wk都是非负实数,则:
f(x)=i=1∑kwifi(x)
是一个凸函数,因为:
f(θx+(1−θ)y)=i=1∑kwifi(θx+(1−θ)y)≤i=1∑kwi(θfi(x))+(1−θ)fi(y))=θi=1∑kwifi(x)+(1−θ)i=1∑kwifi(y)=θf(x)+(1−θ)f(x)
下一篇:凸优化学习(四)——凸优化问题