Nothing dearer than the greyish song, where the wavering and precise are joined.
在空泛的梦里,确切地梦到灿烂的你。想与你做橡树和木棉,无论地下还是云里,都相依在一起。

0%

凸优化(一):凸函数判定方法的证明

刚刚起步学习凸优化的过程实在伴随着种种CH3(CH2)6COOH\rm CH_3(CH_2)_6COOH。在笔记之余,也写写自己对一些小问题的证明思路和从教材上受到的启发。这些东西整理成笔记有些麻烦,又不想忘掉,就发在博客上吧。

ps:CH3(CH2)6COOH\rm CH_3(CH_2)_6COOH是啥,各位上过高中的同学自行理解应该没问题。有问题的百度一下:P

凸函数的定义

给定凸集CRnC\in\R^n,若函数f:CRf:C\rarr\R满足

(xCyC)(λ[0,1])(f(λx+(1λ)y)λf(x)+(1λ)f(y))(\forall x\in C\forall y\in C)(\forall\lambda\in[0,1])(f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y))

则称ff是凸函数。

或者说,凸组合的函数值要不大于函数值的凸组合。低维的情况反应在图像上,就是y=f(x)y=f(x)对应图形必定在两点连线下方。




凸函数的一阶判定

一阶判定:若函数ff是可微的,则ff是凸函数当且仅当

f(y)f(x)+Tf(x)(yx)f(y)\geq f(x)+\nabla^Tf(x)(y-x)

即函数值大于等于其一阶逼近。

这个问题的证明在高维(f:RnRf:\R^n\rarr\R)的情况下比较困难,但是在一维情况下相对简单。[1]

特殊情况:f:CRRf:C\subseteq\R\rarr\R

此时一阶判定退化为

f is convex(x,yD(f))(f(y)f(x)+f(x)(yx))f\text{ is convex}\Leftrightarrow(\forall x,y\in\mathscr{D}(f))(f(y)\geq f(x)+f'(x)(y-x))

(原书中用domf\mathrm{dom}f表示ff的前域domain of ff,我交的离散数学教材上用的是D(f)\mathscr{D}(f),意思一致)

必要性证明: 假设ff是凸函数,由凸函数定义可得

f(x+λ(yx))(1λ)f(x)+λf(y)f(x+\lambda(y-x))\leq(1-\lambda)f(x)+\lambda f(y)

限制λ>0\lambda>0,就可以将上述不等式变形为

f(y)f(x)+f(x+λ(yx))f(x)λf(y)\geq f(x)+\frac{f(x+\lambda(y-x))-f(x)}{\lambda}

再变形一下,

f(y)f(x)+f(x+λ(yx))f(x)λ(yx)(yx)f(y)\geq f(x)+\frac{f(x+\lambda(y-x))-f(x)}{\lambda(y-x)}\cdot(y-x)

两边取极限t0+t\rarr 0_+,得

f(y)f(x)+f(x)(yx)f(y)\geq f(x)+f'(x)(y-x)

充分性证明: 若一阶判定f(y)f(x)+f(x)(yx)f(y)\geq f(x)+f'(x)(y-x)成立,令z=λx+(1λ)y  (0λ1)z=\lambda x+(1-\lambda)y\;(0\leq\lambda\leq 1),则可以得到

f(x)f(z)+f(z)(xz)(1)f(x)\geq f(z)+f'(z)(x-z)\tag{1}

f(y)f(z)+f(z)(yz)(2)f(y)\geq f(z)+f'(z)(y-z)\tag{2}

(1)λ+(2)(1λ)(1)\cdot\lambda+(2)\cdot(1-\lambda),可得

λf(x)+(1λ)f(y)f(z)=f(λx+(1λ)y)\lambda f(x)+(1-\lambda)f(y)\geq f(z)=f(\lambda x+(1-\lambda)y)

这就证明了一阶判定条件(一维情况)。


一般情况:f:CRnRf:C\subseteq\R^n\rarr\R

证明高维情况时非常希望能够类比一维情况,但是一维的必要性证明中,使用了R\R上函数的导数定义——Rn\R^n上函数的导数要用2\ell_2范数来定义,这是搬不过来的!

怎么解决呢?这里原书中用了一种非常精彩的证明思路:(也许是我见识短浅啦,至少我看起来是很漂亮的)

Consider ff restricted to the line passing through them(xx and yy)

定义g(t)=f(x+t(yx))g(t)=f(x+t(y-x))作为辅助,这个函数的导数是

g(t)=f(x+t(yx))T(yx)g'(t)=\nabla f(x+t(y-x))^T(y-x)

然后利用这个函数来证明:

必要性证明: 假设ff是凸函数,那么

g(λt+(1λ)s)=f(x+(λt+(1λ)s)(yx))=f(λ(x+t(yx))+(1λ)(x+s(yx)))λf(x+t(yx))+(1λ)f(x+s(yx))=λg(t)+(1λ)g(s)\begin{aligned} &g(\lambda t+(1-\lambda)s) \\ =&f(x+(\lambda t+(1-\lambda)s)(y-x)) \\ =&f(\lambda(x+t(y-x))+(1-\lambda)(x+s(y-x))) \\ \geq &\lambda f(x+t(y-x))+(1-\lambda)f(x+s(y-x)) \\ =&\lambda g(t)+(1-\lambda)g(s) \end{aligned}

这意味着gg也是凸函数(其实g is convexg\text{ is convex}f is convexf\text{ is convex}的充要条件[2],下面会证明)

虽然我拿ff没办法,但gg是一元函数啊!根据上面已经证明的结论,g(1)g(0)+g(0)1g(1)\geq g(0)+g'(0)\cdot 1,回带到ff中,立即得到

f(y)f(x)+Tf(x)(yx)f(y)\geq f(x)+\nabla^Tf(x)(y-x)

充分性证明: 若一阶判定条件成立,则有

f(x+t(yx))f(x+s(yx))+f(x+s(yx))T(yx)(ts)f(x+t(y-x))\geq f(x+s(y-x))+\nabla f(x+s(y-x))^T(y-x)(t-s)

带入到gg中,得到gg是凸函数,这就回到了一元的情况.用两次结论可得

g(t)g(0)+g(0)t(1)g(t)\geq g(0)+g'(0)t\tag{1}

g(t)g(1)+g(1)(t1)(2)g(t)\geq g(1)+g'(1)(t-1)\tag{2}

(1)(1t)+(2)t(1)\cdot(1-t)+(2)\cdot t,回代到ff中可得

f(x+t(yx))(1t)f(x)+tf(y)f(x+t(y-x))\geq(1-t)f(x)+tf(y)

这就证明了ff是凸函数.


上面的证明主要来自Convex Optimization,我作了一点改动。

最重要的思路是

  1. 构造g(t)=f(x+t(yx))g(t)=f(x+t(y-x))来表达ff被限制在x,yx,y之间的情况,下面证明二阶判定时同样用到。
  2. ff可微,则ffgg的凸性是等价的。




凸函数的二阶判定

二阶判定:若函数ff是二阶可微的,则 ff是凸函数    (xC)(2f(x)S+n)\iff(\forall x\in C)(\nabla^2f(x)\in S_+^n)(对称半正定)

这个问题与对称性其实无关(二阶可微保证了偏导数与求导顺序无关,那么Hessian矩阵一定是对称的),问题在于证明它是半正定的。

必要性比较容易证明,主要是通过Taylor展开来引入Hessian矩阵对应的二次型:

ff是凸函数,则dRn\forall d\in\R^nf(x+td)f(x)+f(x)T(td)f(x+td)\geq f(x)+\nabla f(x)^T(td).

ffxx处作二阶Taylor展开得到带Peano余项的近似为

f(x+td)=f(x)+f(x)T(td)+12(td)T2f(x)(td)+o(td2)f(x+td)=f(x)+\nabla f(x)^T(td)+\frac{1}{2}(td)^T\nabla^2f(x)(td)+o(\|td\|^2)

然后用展开式替换一阶判定左边的f(x+td)f(x+td),尝试证明对于任意的向量dd,都有dT2f(x)d0d^T\nabla^2f(x)d\geq 0

f(x)+f(x)T(td)+12(td)T2f(x)(td)+o(td2)f(x)+f(x)T(td)12(td)T2f(x)(td)+o(td2)012dT2f(x)d+o(td2)t20limt0(12dT2f(x)d+o(td2)t2)0dT2f(x)d02f(x)S+n\begin{aligned} &f(x)+\nabla f(x)^T(td)+\frac{1}{2}(td)^T\nabla^2f(x)(td)+o(\|td\|^2)\geq f(x)+\nabla f(x)^T(td) \\ \Rightarrow &\frac{1}{2}(td)^T\nabla^2f(x)(td)+o(\|td\|^2)\geq 0 \\ \Rightarrow &\frac{1}{2}d^T\nabla^2f(x)d+\frac{o(\|td\|^2)}{t^2}\geq 0 \\ \Rightarrow &\lim_{t\rightarrow 0}\Big(\frac{1}{2}d^T\nabla^2f(x)d+\frac{o(\|td\|^2)}{t^2}\Big)\geq 0 \\ \Rightarrow &d^T\nabla^2f(x)d\geq 0 \\ \Rightarrow &\nabla^2f(x)\in S_+^n \end{aligned}

(大概也可以通过g(t)g(t)证明,但是直接用Taylor展开更简短)

充分性我是通过构造辅助函数证明的:

首先,对于一维情况f:CRRf:C\subseteq\R\rightarrow\R,Hessian矩阵退化为二阶导数.

f(x)0f''(x)\geq 0恒成立,则对任意的x1<x2(x1,x2C)x_1<x_2(x_1,x_2\in C)由Lagrange中值定理有

(ξ[x1,x2])  (f(ξ)=f(x1)f(x2)x1x2)(\exists\xi\in[x_1,x_2])\;(f'(\xi)=\frac{f(x_1)-f(x_2)}{x_1-x_2})

f(x)0f''(x)\geq 0,有f(ξ)f(x2)f'(\xi)\leq f'(x_2),即

f(x1)f(x2)f(x2)(x1x2)f(x1)f(x2)+f(x2)(x1x2)\begin{aligned} &f(x_1)-f(x_2)\geq f'(x_2)(x_1-x_2) \\ \Leftrightarrow &f(x_1)\geq f(x_2)+f'(x_2)(x_1-x_2) \end{aligned}

由一阶判定可证ff是凸函数(x1>x2x_1>x_2的情况同理).

之后,对于一般情况f:CRnRf:C\subseteq\R^n\rightarrow\R,若2f(x)S+n\nabla^2f(x)\in S_+^n恒成立,令g(t)=f(x+t(yx))g(t)=f(x+t(y-x)),则

g(t)=f(x+t(yx))T(yx)g(t)=(yx)T2f(x+t(yx))(yx)\begin{aligned} &g'(t)=\nabla f(x+t(y-x))^T(y-x) \\ &g''(t)=(y-x)^T\nabla^2f(x+t(y-x))(y-x) \end{aligned}

2f(x+t(yx))S+n\nabla^2f(x+t(y-x))\in S_+^n,有g(t)0g''(t)\geq 0恒成立,又由前述结论,可知g(t)g(t)是凸函数.而gg的凸性与ff的凸性是等价的,所以ff是凸函数.




小记

好久没有再用过微积分和线性代数的内容,什么都生疏了。就像优化方法的老师说的一样,没开学还逃过了随机点名提问的一劫:P

这篇主要的技巧是凸函数判定的一个充要条件:若ff可微,则

f is convex    g is convexf\text{ is convex}\iff g\text{ is convex}

g(t)=f(x+t(yx))org(t)=f(x+tv)g(t)=f(x+t(y-x))\qquad\text{or}\qquad g(t)=f(x+tv)




参考资料

[1]Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Page 69, 2004. Avaliable from https://web.stanford.edu/~boyd/cvxbook/

[2]Stephen Boyd, Lieven Vandenberghe, Lecture slides, Convex functions 3-5. Avaliable from https://web.stanford.edu/~boyd/cvxbook/