凸优化（四）凸函数分析

作者: SaySei | 来源:发表于2018-12-24 00:08 被阅读0次

1. 概述

$\quad$ 之前简单介绍了凸函数的定义，相信大家对凸函数有了简单的认识，但是这是远远不够的，这次通过一些详细的函数讲解来介绍一下部分常见凸函数的特点。

2. 凸函数的四个定义：

（1）第一个定义：如果X为在实数向量空间的凸集。并且有映射 $f:X\rightarrow R$ ，如果 $f$ 被称为凸，则有 $\forall x_1,x_2\in X,\forall t\in[0,1]: f(tx_1+(1-t)x_2)\leq tf(x_1)+(1-t)f(x_2).$ 如果F被称为严格凸，那么有： $\forall x_1\ne x_2\in X,\forall t\in(0,1): f(tx_1+(1-t)x_2)\ngeq tf(x_1)+(1-t)f(x_2).$

（2）第二个定义：有映射 $f:R^n\rightarrow R为凸\leftrightarrow dom f为凸$，$\forall x,y\in dom f,\forall v为任意方向，g(t)=f(x+tv)为凸$ ， $dom g=\{t|x+tv\in dom f\}$

（3）第三个定义：若 $f$ 可微，对 $\forall x,y\in dom f,f(y)\geq f(x)+\nabla^Tf(y-x)$

（4）第四个定义：二阶条件，若 $f:R^n\rightarrow R$ 二阶可微，则 $f为凸$\leftrightarrow dom f为凸，\nabla^2f(x)\geq0,\forall x\in dom f$ （这里的大于等于号是表示特征值大于等0，表示矩阵半正定）。

这四个定义在不同地方均有用处，但在判断函数是否为凸函数时最常用的是第四个。其中 $\nabla^2f(x)$ 为Hessian矩阵，表示函数的二阶偏导矩阵。

3. 常见凸函数：

（1）仿射函数： $f(x)=Ax+b$ ,显然，其二阶导函数为 $\nabla^2f(x)=0$ ，所以仿射函数为凸函数。

（2）指数函数： $f(x)=e^{ax},x\in R$ ,显然 $f^{'}(x)=ae^{ax}，f^{''}(x)=a^2e^{ax}\geq0$ ,所以指数函数是凸函数。

（3）幂函数： $f(x)=x^a，x\in R_{++}$ ,接着求导啊求导~， $f^{'}(x)=ax^{a-1}$ ， $f^{''}(x)\begin{cases} \geq 0,a\geq1 或a\leq0 （凸函数）\\ \leq 0,0\leq a\leq1 （凹函数）\end{cases}$ ，显然啦，当 $a=1、0$ 时，幂函数就成为了仿射函数，所以即凸又凹。

（4）负熵函数： $f(x)=xln{x},x\in R_{++}$ ,还是求导， $f^{'}(x)=lnx+1，f^{''}(x)=\frac{1}{x}\nleq0$ ,嗯，还是个严格凸函数。（也是个非常重要的函数！！）

（5）极大值函数（重中之重）：现在来一个比较复杂却非常常见的函数： $f(x) = max\{x_1,x_2,...,x_n\}$ 这个函数显然是不可导的，那么首先根据定义一来看一下是否为凸函数。取两值 $x,y\in dom f$ ，构造凸组合的新值 $\theta x+(1-\theta)y，f(\theta x+(1-\theta)y)=max\{\theta x_i+(1-\theta)y_i\}\leq \theta max\{x_i,i=0,1..n\}+(1-\theta)max\{y_i,i=0,1..n\}=\theta f(x)+(1-\theta)f(y)$ ,发现满足凸函数定义，所以极大值函数时凸函数。但是啊，由于其无法求导，后续处理会出现各种问题。所以，这里有一个解析逼近，就是用一个解析函数去逼近极大值函数。这个函数是这样的 $log-sum-exp:$ ： $f(x)=log(e^{x_1}+...+e^{x_n}),x\in R^n，且有性质max\{x_i\}\leq f(x)\leq max\{x_i\}+ln(n)$ $\quad$ 那么来证明一下这个函数也是凸函数吧！这里就要用到凸函数的第四个定义了，轮到Hessian矩阵出场了。对上述函数求二次偏导得到如下关系（~~公式打得累死~~）：
$\frac{\partial^2f}{\partial{x_i}\partial{y_i}}=\frac{-e^{x_i}e^{x_j}}{(e^{x_1}+...e^{x_n})^2},i\neq j, \frac{\partial^2f}{\partial{x_i}\partial{y_i}}=\frac{-e^{x_i}e^{x_i}+e^{x_i}(e^{x_1}+...e^{x_n})}{(e^{x_1}+...e^{x_n})^2},i=j\tag{1}$
这个式子看上去也很丑，那么定义列向量 $z=[e^{x_1},...,e^{x_n}]^T$ ,那么(1)式就变成了 $\frac{\partial^2f}{\partial{x_i}\partial{y_i}}=\frac{-e^{x_i}e^{x_j}}{(1^Tz)^2},i\neq j, \frac{\partial^2f}{\partial{x_i}\partial{y_i}}=\frac{-e^{x_i}e^{x_i}+e^{x_i}(1^Tz)} {(1^Tz)^2},i=j$ ,函数的Hessian矩阵可以写成 $H(x)=\frac{1}{(1^Tz)^2}((1^Tz)diag(z)-zz^T),另后项矩阵为K，diag(z)，为向量z展开的对角矩阵$ 那么大家还记得半正定矩阵如何证明么？就是 $\forall x\in R^n,x^TAx\geq0$ 成立，那么A则为半正定矩阵。好，那么开始构造！！ $V^TKV=(1^Tz)V^Tdiag(z)v-V^Tzz^TV=(\sum_iz_i)\sum_i(V_i^2z_i)-(\sum_iv_iz_i)^2\tag{2}$ 另 $a_i=v_i\sqrt{z_i},b_i=\sqrt{z_i}$ ,那么(2)式就变成了: $(b^Tb)(a^Ta)-(a^Tb)^2\geq0\tag{3}$ 此式成立，用到的性质为柯西-施瓦茨不等式,所以 $log-sum-exp$ 函数为凸函数。

（6）行列式的对数： $f(X)=\log det(X),dom f=S^n_{++}$ ，首先说明一下啊，当矩阵X只有一维时，那么原函数则为 $\log x$ ，显然是凹函数。所以我们是在已经知道其为凹函数的前提下证明它是凹函数的了~根据凸函数的第二个定义当 $\forall z\in S^n_{++}，\forall t\in R^{n \times n},z+tv\in S^n_{++}=dom f$ ，构造凸组合的函数 $g(t)=f(z+tv)=\log det(z+tv)=\log det(z^{\frac{1}{2}}(I+tv^{-\frac{1}{2}}vz^{-\frac{1}{2}})z^{\frac{1}{2}})\tag{4}$ 继续化简得到为： $\log det\{z\}+\log det\{I+tz^{-\frac{1}{2}}vz^{-\frac{1}{2}}\}=\log det\{z\}+\sum^n_i\log(1+t\lambda_i),其中\lambda_i\geq0\tag{5}$ 接着只要分析这个式子就可以，求导即可，得到： $g^{'}(t)=\sum_i\frac{\lambda_i}{1+t\lambda_i},g^{''}(t)=\sum_i\frac{-\lambda_i^2}{(1+t\lambda_i)^2}\leq0\tag{6}$ 到这里证明就结束了，原函数为凹函数得证。