引言

• 非负加权和
• 复合仿射映射
• 逐点最大
• 复合运算(例如多分类中的softmax函数)
• 联合凸的部分极小化
• 透视函数(例如KL散度和相对熵)

---

非负加权和

定义（非负加权和）
凸函数$f$的非负加权和也是凸函数，利用凸函数定义即可证明。
$$f=w_1{f}_1+\cdots +w_m{f}_m,w_i\ge 0$$
可拓展至无限项：若固定任意$y\in \mathcal{A}$，$f(x,y)$是关于$x$的凸函数，且对任意$y\in \mathcal{A}$,$w(y)\ge 0$，则：
$$g(x)={\int }_{\mathcal{A}}w(y)f(x,y)dy$$
也是关于$x$的凸函数。

---

复合仿射映射

定义（复合仿射映射）
假设凸函数$f:{\mathbf{R}}^n\to \mathbf{R},A\in {\mathbf{R}}^{n\times m},b\in R^n,$
定义函数$g:R^n\to R$为：
$$g(x)=f(Ax+b)$$
则$g$也是凸函数，利用凸函数定义即可立即证明，也可借助复合函数的保凸性说明。

---

逐点最大

定义（逐点最大）
若$f_1,f_2,...,f_m$是凸函数，则f(x)=max⁡{f1(x),f2(x),...,fm(x)}f(x)=\max\{f_1(x),f_2(x),...,f_m(x)\}f(x)=max{f1​(x),f2​(x),...,fm​(x)}是凸函数。
可拓展至无限项：若对$\forall y\in \mathcal{A},f(x,y)$关于$x$是凸函数，则$g(x)=\underset{y\in \mathcal{A}}{\sup }f(x,y)$也是凸函数。

证明（m=2情形）
$\forall x,y\in \text{dom}f,0\le \theta \le 1,$有
f(θx+(1−θ)y)=max⁡{f1(θx+(1−θ)y),f2(θx+(1−θ)y)}≤max⁡{θf1(x)+(1−θ)f1(y),θf2(x)+(1−θ)f2(y)}≤θf(x)+(1−θ)f(y)\begin{aligned} f(\theta x+(1-\theta)y) &=\max\{f_1(\theta x+(1-\theta)y),f_2(\theta x+(1-\theta)y)\} \\ &\le\max\{\theta f_1(x)+(1-\theta)f_1(y),\theta f_2(x)+(1-\theta)f_2(y)\} \\ &\le \theta f(x)+(1-\theta)f(y) \end{aligned}f(θx+(1−θ)y)​=max{f1​(θx+(1−θ)y),f2​(θx+(1−θ)y)}≤max{θf1​(x)+(1−θ)f1​(y),θf2​(x)+(1−θ)f2​(y)}≤θf(x)+(1−θ)f(y)​

注
可通过例子理解：f(x)=max⁡{x2,x}f(x)=\max\{x^2,x\}f(x)=max{x2,x}，下图红线部分即为函数$f(x)$

示例（集合中最远距离）
点$x$到集合$C\subseteq R^n$的最远距离定义为：
$f(x)=\underset{y\in C}{\sup }\Vert x-y\Vert$。
$\Vert x-y\Vert$关于$x$是凸函数，而$\underset{y\in C}{\sup }\Vert x-y\Vert$是凸函数的逐点上确界，因此为凸函数。

示例（对称矩阵的最大特征值）
定义$f(X)={\lambda }_{\max }(X),\text{dom}f=S^m,$其为凸函数。
证明
$f(X)=\underset{\Vert y{\Vert }_2=1}{\sup }{y}^{T}Xy$，是满足$\Vert y{\Vert }_2=1$的$X$一族线性函数的逐点上确界。

示例（矩阵谱范数）
矩阵的谱范数：$f(X)=\Vert X{\Vert }_2,\text{dom}f=R^{p\times q}$（最大奇异值）。
证明
$f(X)=\underset{\Vert u{\Vert }_2=1,\Vert v{\Vert }_2=1}{\sup }{u}^{T}Xv$，是$X$一族线性函数的逐点上确界。

示例（加权最小二乘）
令$x_1,...,x_n\in R^m$，定义：
$$g(w)=\underset{\beta }{\inf }\sum _{i=1}^n{w}_i(x_i^T\beta -y_i{)}^2$$
$g$是关于$w$的一族线性函数的逐点下确界，是$w$的凹函数。
令$W=\text{diag}(w),X\in R^{n\times m}$，有
$$\begin{array}{rl}g(w)& =\underset{\beta }{\inf }(X\beta -y{)}^{T}W(X\beta -y)\\ & =\underset{\beta }{\inf }({\beta }^T{X}^{T}WX\beta -2y^{T}WX\beta +y^{T}Wy)\end{array}$$
当$X^{T}WX\succ 0$时，通过Schur补可得凸性。

---

复合运算

给定$h:R^k\to R$及$g:R^n\to R^k$，定义复合$f=h\circ g$，domf={x∈domg∣g(x)∈domh}\text{dom}f=\{x\in\text{dom}g|g(x)\in \text{dom}h\}domf={x∈domg∣g(x)∈domh}。

标量复合

假设$h,g$二次可微，通过二阶条件判定凸性：
$$f^{\prime \prime }(x)=h^{\prime \prime }(g(x))g^{\prime }(x{)}^2+h^{\prime }(g(x))g^{\prime \prime }(x)\ge 0$$
$f$为凸函数的条件：

1. $h$凸且非减，$g$凸：$h^{\prime \prime }\ge 0,h^{\prime }(g(x))\ge 0,g^{\prime \prime }\ge 0$
2. $h$凸且非增，$g$凹：$h^{\prime \prime }\ge 0,h^{\prime }(g(x))\le 0,g^{\prime \prime }\le 0$

$f$为凹函数的条件：

1. $h$凹且非减，$g$凹：$h^{\prime \prime }\le 0,h^{\prime }(g(x))\ge 0,g^{\prime \prime }\le 0$
2. $h$凹且非增，$g$凸：$h^{\prime \prime }\le 0,h^{\prime }(g(x))\le 0,g^{\prime \prime }\ge 0$

注
当$g$是仿射函数时，若$h$凸则$f$必凸。

矢量复合

$f(x)=h(g_1(x),\dots ,g_k(x))$，二阶条件：
$$f^{\prime \prime }(x)=g^{\prime }(x{)}^T{\nabla }^{2}h(g(x))g^{\prime }(x)+\nabla h(g(x){)}^T{g}^{\prime \prime }(x)$$
$f$为凸函数的条件：

1. $h$凸且在每维非减，$g_i$凸：${\nabla }^{2}h⪰0,\nabla h⪰0,g^{\prime \prime }\ge 0$
2. $h$凸且在每维非增，$g_i$凹：${\nabla }^{2}h⪰0,\nabla h⪯0,g^{\prime \prime }\le 0$

示例（指数对数和，softmax函数）
$$g(x)=\log \left(\sum _{i=1}^k{e}^{a_i^{T}x+b_i}\right)$$
仅需说明$f(x)=\log ({\sum }_{i=1}^n{e}^{x_i})$是凸函数，即可根据外层与仿射函数复合运算说明$g(x)$是凸函数。
证明其凸性
梯度分量：${\nabla }_{i}f(x)=\frac{e^{x_i}}{{\sum }_{\ell =1}^n{e}^{x_{\ell }}}$
Hessian矩阵：${\nabla }^{2}f(x)=\text{diag}(z)-z{z}^T(z_i=e^{x_i}/\sum e^{x_{\ell }})$
对任意$v\in R^n$：
$$\begin{array}{rl}{v}^T{\nabla }^{2}fv& =\sum z_i{v}_i^2-{\left(\sum v_i{z}_i\right)}^2\\ & =\text{Var}(v)\ge 0\end{array}$$
故${\nabla }^{2}f(x)⪰0$，$f$为凸函数。

---

联合凸的部分最小化

若$f$关于$(x,y)$是联合凸函数，$C$是非空凸集，定义：
$$g(x)=\underset{y\in C}{\inf }f(x,y)$$
若存在$x$使$g(x)>-\infty$，则$g$关于$x$是凸函数。

示例（点到集合距离）
$$\text{dist}(x,S)=\underset{y\in S}{\inf }\Vert x-y\Vert$$
若$S$是非空凸集，则$\text{dist}(x,S)$是关于$x$的凸函数。
注
对比逐点最大：逐点最大不要求$S$是凸集。

示例（Schur补）
考虑二次函数：
$$f(x,y)=x^{T}Ax+2x^{T}By+y^{T}Cy,\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right]⪰0$$
则：
$$g(x)=\underset{y}{\inf }f(x,y)=x^T(A-B{C}^{-1}{B}^T)x$$
由部分最小化保凸性，得$A-B{C}^{-1}{B}^T⪰0$。

---

透视函数

给定$f:{\mathbf{R}}^n\to \mathbf{R}$，其透视函数$g:{\mathbf{R}}^{n+1}\to \mathbf{R}$定义为：
$$g(x,t)=tf(x/t),\text{dom}g=\{(x,t)\mid x/t\in \text{dom}f,t>0\}$$
若$f$是凸函数，则$g$也是凸函数。

证明
当$f$是凸函数，$x/t$是凸集，在学习凸集的保凸性时已经知道，当$C$是凸集，$P$是透视运算，透视运算的原像$P^{-1}(C)$也是凸集，因此$(x,t)$是凸集。结合上镜图判定，
$$\text{epi}g=\{(x,t,s)|g(x,t)\le s,t>0\}=\{(x,t,s)|tf(x/t)\le s,t>0\}=\{(x,t,s)|f(x/t)\le s/t,t>0\}$$
$$\iff \text{epi}f=\{(x/t,s/t)|f(x/t)\le s/t,t>0\}$$
由于$f$是凸函数，其$\text{epi}f$是凸集。显然$\text{epi}g$是透视映射下$\text{epi}f$的原像，因此$\text{epi}g$是凸集，$g$是凸函数。

示例（$l_2$范数平方的透视）
$R^n$上的凸函数$f(x)=x^{T}x$透视可得$g(x,t)=t(x/t{)}^T(x/t)=x^{T}x/t$，当$t>0$时，其关于$(x,t)$是凸函数。也可表述成$x^T(tI{)}^{-1}x$，借助凸函数及定义处的矩阵分式函数判定其为凸函数。还可以把该透视函数表述成${\sum }_i\frac{x_i^2}{t}$，其中每一项$x_i^2/t$都是凸函数，借用凸函数的非负加权和仍是凸函数，判定透视函数是凸函数。

示例（KL散度与相对熵）
考虑$R_{++}$上的凸函数$f(x)=-\log x$，其对应的透视函数为：
$$g(x,t)=-t\log (x/t)=t\log (t)-t\log x$$
该函数$g$称作关于$x,t$的相对熵。可见相对熵是凸函数，当$x=1$，$g$为负熵。

定义两个向量$u,v\in R_{++}^n$的相对熵：
$$\sum _{i=1}^n{u}_i\log (u_i/v_i),$$
其是一系列$u_i,v_i$相对熵的非负加权和(权为1),因此关于$(u,v)$是凸函数。

相对熵经过非负加权和的保运算可得到\textcolor{red}{KL散度:}
$$D_{\mathrm{kl}}(u,v)=\sum _{i=1}^n\left(u_i\log (u_i/v_i)-u_i+v_i\right)$$其是相对熵和线性函数之和，因此也为凸函数。

当且仅当$u=v$，$D_{\mathrm{kl}}(u,v)=0$，并且$D_{\mathrm{kl}}(u,v)\ge 0$，常用于衡量两个正向量之间的偏差。

并且值得注意的是，当$u,v$都是概率向量，有${\sum }_i{u}_i=1,{\sum }_i{v}_i=1$，此时KL散度=相对熵。

\begin{proof}[证明$D_{\mathrm{kl}}(u,v)\ge 0$]引入Bregman散度：
$$D_B(u,v)=f(u)-f(v)-{\nabla }^{T}f(v)(u-v)$$
其中$f$假设严格凸且可导，因此直观上来看，$D_B(u,v)$衡量了$f$在点$u$处，与在点$v$处线性展开的差异。并且可见，$D_B(u,v)$对$u$一定是凸函数(通过仿射保凸性和非负加权和保凸性可判断)，但对$v$不一定，因此联合不一定是凸函数。

根据凸函数$f$的一阶判定条件可知，$D_B(u,v)\ge 0$。而KL散度是Bregman散度取$f(x)={\sum }_i{x}_i\log x_i$的特例。具体${\nabla }^{T}f(x)=(1+\log x_1,1+\log x_2,...,1+\log x_d)$，
$$D_B(p,q)=\sum _i{p}_i\log p_i-\sum _i{q}_i\log q_i-\sum _i(1+\log q_i)(p_i-q_i)=D_{KL}(p,q)$$
还有一些常用的Bergman散度：

定义$f(x)=\frac{1}{2}\Vert x{\Vert }^2\Rightarrow D_f(x,y)=\frac{1}{2}\Vert x-y{\Vert }^2$，K-means距离的损失函数。

定义$f(x)=-\sum \log x_i\Rightarrow D_f(x,y)={\sum }_i(x_i/y_i-\log x_i/y_i-1)$，常用于信号处理。