凸优化（一）：凸函数判定方法的证明

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

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

凸函数的定义

给定凸集$C\in\R^n$，若函数$f:C\rarr\R$满足

$$(\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))$$

则称$f$是凸函数。

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

凸函数的一阶判定

一阶判定：若函数$f$是可微的，则$f$是凸函数当且仅当

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

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

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

特殊情况：$f:C\subseteq\R\rarr\R$

此时一阶判定退化为

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

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

必要性证明： 假设$f$是凸函数，由凸函数定义可得

$$f(x+\lambda(y-x))\leq(1-\lambda)f(x)+\lambda f(y)$$

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

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

再变形一下，

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

两边取极限$t\rarr 0_+$，得

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

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

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

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

$(1)\cdot\lambda+(2)\cdot(1-\lambda)$，可得

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

这就证明了一阶判定条件（一维情况）。

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

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

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

Consider $f$ restricted to the line passing through them($x$ and $y$)

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

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

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

必要性证明： 假设$f$是凸函数，那么

$$\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}$$

这意味着$g$也是凸函数（其实$g\text{ is convex}$是$f\text{ is convex}$的充要条件[2]，下面会证明）

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

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

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

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

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

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

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

$(1)\cdot(1-t)+(2)\cdot t$，回代到$f$中可得

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

这就证明了$f$是凸函数.

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

最重要的思路是

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

凸函数的二阶判定

二阶判定：若函数$f$是二阶可微的，则 $f$是凸函数$\iff(\forall x\in C)(\nabla^2f(x)\in S_+^n)$（对称半正定）

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

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

若$f$是凸函数，则$\forall d\in\R^n$，$f(x+td)\geq f(x)+\nabla f(x)^T(td)$.

对$f$在$x$处作二阶Taylor展开得到带Peano余项的近似为

$$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)$，尝试证明对于任意的向量$d$，都有$d^T\nabla^2f(x)d\geq 0$

$$\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)$证明，但是直接用Taylor展开更简短）

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

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

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

$$(\exists\xi\in[x_1,x_2])\;(f'(\xi)=\frac{f(x_1)-f(x_2)}{x_1-x_2})$$

由$f''(x)\geq 0$，有$f'(\xi)\leq f'(x_2)$，即

$$\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}$$

由一阶判定可证$f$是凸函数（$x_1>x_2$的情况同理）.

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

$$\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}$$

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

小记

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

这篇主要的技巧是凸函数判定的一个充要条件：若$f$可微，则

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

$$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/