一、基本性质和例子

定义

函数$f:\mathbb{R}^n \rightarrow \mathbb{R}$是凸的，如果$\textbf{dom} f$是凸集，且对于任意$x ,y \in \textbf{dom}f$和任意$0\leq \theta \leq 1$，有：

意味着点$(x, f(x))$和$(y, f(y))$之间的线段，即从$x$到$y$的弦在函数$f$的图像上方。

如果式(1)中的不等式当$x \neq y$以及$0 < \theta <1$时严格成立，则$f$是严格凸的。

如果函数$-f$是凸的，那么函数$f$是凹的。

如果函数$-f$是严格凸的，那么函数$f$是严格凹的。

对于仿射函数，由于$f(\theta x +(1 - \theta) y) = \theta f(x) +(1 - \theta)f(y)$，因此所有的仿射函数是即凸且凹的。

反之如果某个函数即是凸又是凹的，那么它是仿射函数。

性质

函数是凸的，当且仅当其在与其定义域相交的任何直线上都是凸的。换言之，函数$f$是凸的，当且仅当对于任意$x \in \textbf{dom} f$和任意向量$v$，函数$g(t) = f(x + tv)$是凸的（其定义域为$\{t | x + tv \in \textbf{dom}f\}$）。

证明：

1. 已知函数$f$是凸的，因此存在$\forall x_1, x_2 \in \textbf{dom}f$，选取一个$x_0$位于$x_1, x_2$所形成的直线上，确保$x_0 \in \textbf{dom}f$，令$v = x_2 - x_1$，则$x_1 = x_0 + t_1 v$, $x_2 = x_0 + t_2v$，有：

$$\begin{aligned} f(\theta x_1 + (1 - \theta)x_2) &= f(\theta (x_0 + t_1v) + (1 - \theta)(x_0 + t_2v))\\ &= f(x_0 + (\theta t_1 + (1 - \theta) t_2) v) = g(\theta t_1 + (1 - \theta) t_2)\\ &\leq \theta f(x_0 + t_1v) + (1 - \theta)f(x_0 + t_2v)\\ &=\theta g(t_1) + (1 - \theta)g(t_2) \end{aligned}$$

因此函数$g(t) = f(x + tv)$是凸的。

2. 已知$g(t) = f(x + tv)$是凸的，对于$\forall x_1, x_2 \in \textbf{dom}f$，取$v = x_2 - x_1$，有$f(\theta x_1 +(1- \theta)x_2) = f(x_1 +(1-\theta)(x_2 - x_1))$，令$t = 1 - \theta$。由于$g$在这条直线上是凸的，因此：

$$f(x_1 + (1 - \theta)v) \leq \theta f(x_1) + (1 - \theta)f(x_2).$$

故$f$是凸函数。

 

拓展值延伸

如果$f$是凸函数，我们定义它的拓展值延伸$\tilde{f}:\mathbb{R}^n \rightarrow \mathbb{R} \cup \{\infty\}$如下：

延伸函数$\tilde{f}$是定义在全空间$\mathbb{R}^n$上的，取值集合为$\mathbb{R} \cup \{\infty\}$。我们也可以从延伸函数$\tilde{f}$的定义中确定原函数$f$的定义域，即$\textbf{dom} f =\{x | \tilde{f}(x) < \infty\}$.

通过延伸我们可以简化符号描述，不在需要限定对于所有的$x \in \textbf{dom}f$。例如对于式（1），可以描述为：对于任意$x$和$y$，以及$0 < \theta < 1$，有：

$$\tilde{f}(\theta x +(1- \theta)y) \leq \theta \tilde{f}(x) + (1- \theta)\tilde{f}(y).$$

凸集的示性函数：设$C \subseteq \mathbb{R}^n$是一个凸集，考虑（凸）函数$I_C$，其定义域为$C$，对于所有的$x \in C$，有$I_C(x) = 0$。其拓展值延伸可以描述如下：

凸函数$\tilde{I}_C(x)$被称作集合$C$的示性函数。

作用：函数$f + \tilde{I}_C$等价于定义在集合$C$上的函数$f$

注：对于凹函数可以利用$-\infty$进行同样的定义。

二、一阶条件

假设$f$可微（即其梯度$\nabla f$在开集$\textbf{dom}f$内处处存在），则函数$f$是凸函数的充要条件是$\textbf{dom} f$是凸集且对于任意$x, y \in \textbf{dom} f$，下式成立：

由$f(x) + \nabla f(x)^T(y-x)$得出的仿射函数$y$即为函数$f$在点$x$附近的 Taylor 近似。

不等式（5）表明，对于一个凸函数，其一阶 Taylor 近似实质上是原函数的一个全局下估计。

反之如果某个函数的一阶 Taylor 近似总是其全局下估计，那么这个函数是凸的。

对于$f$，在$y$处的一阶 Taylor 展开为$L(y) = f(x) + \nabla f(x)^T(y- x) + o(\|y-x\|)$

对于凸函数而言，函数与一阶 Taylor 展开有着固定的不等式关系：$f(y) \geq L(y) \Rightarrow f(y) \geq f(x) +\nabla f(x)^T(y-x)$

全局下估计：

• 全局：指不管$\|y-x\|$有多大，都有该不等式成立，$y$是全局任意取值的。
• 下估计：$L(y) \leq f(y)$对所有$y$都成立。

如果式（5）中的不等号换成$>$，则为函数$f$严格凸的充要条件。

对于函数$f$，其为凹函数的充要条件是$\textbf{dom} f$是凸集且对于任意$x ,y \in \textbf{dom}f$，下式成立：

证明：

先考虑$n=1$的情况，我们证明可微函数$f:\mathbb{R} \rightarrow \mathbb{R}$是凸函数的充要条件是对于$\textbf{dom}f$内的任意$x$和$y$，有

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

首先假设$f$是凸函数，且$x, y \in \textbf{dom} f$。因为$\textbf{dom}f$是凸集（某个区间），对于任意$0 <t \leq 1$，我们有$x+t(y-x) \in \textbf{dom} f$，由函数$f$的凸性可得：

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

将上式两端同除$t$可得：

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

当$t \rightarrow 0$，可以得到不等式 （7）.

为了证明充分性，假设对$\textbf{dom}f$（某个区间）内的任意$x$和$y$，函数满足不等式（7）。选择任意$x \neq y, 0 \leq \theta \leq 1$，令$z=\theta x +(1- \theta)y$。两次应用不等式（7）可得：

$$f(x) \geq f(z) + f'(z)(x-z) \quad f(y) \geq f(z) +f'(z)(y - z).$$

将第一个不等式乘以$\theta$，第二个不等式乘以$1 - \theta$，并将二者相加可得：

$$\theta f(x) + (1 - \theta)f(y) \geq f(z).$$

从而说明了函数$f$是凸的。

现在来证明一般情况，即$f:\mathbb{R} \rightarrow \mathbb{R}$。设$x, y \in \mathbb{R}$，考虑过这两点的直线上的函数$f$，即函数$g(t) = f((1- t)x + ty)$，此函数对$t$求导可得：$g'(t) = \nabla f((1-t)x +ty)^T(y - x)$。

首先假设函数$f$是凸的，则函数$g$是凸的，由前面可知，有$g(1) \geq g(0) + g'(0)$，即：

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

再假设此不等式对于任意$x$和$y$均成立，因此若$ty +(1-t)x \in \textbf{dom}f$以及$\tilde{t}y+(1 - \tilde{t})x \in \textbf{dom} f$，我们有：

$$f(ty+(1-t)x) \geq f(\tilde{t}y + (1-\tilde{t})x) + \nabla f(\tilde{t}y + (1- \tilde{t})x)^T(y-x)(t-\tilde{t}),$$

即$g(t) \geq g(\tilde{t}) +g'(\tilde{t})(t- \tilde{t})$，说明了函数$g$是凸的。

三、二阶条件

现在假设$f$二阶可微，即对于开集$\textbf{dom}f$内的任意一点，它的 Hessian 矩阵或者二阶导数$\nabla^2 f$存在，则函数$f$是凸函数的充要条件是，其Hessian矩阵是半正定阵：即对于所有的$x \in \textbf{dom}f$，有：

严格凸的条件可以部分由二阶条件刻画，如果对于任意$x \in \textbf{dom} f$，有$\nabla^2f(x) \succ 0$，则函数$f$严格凸。

反过来则不一定成立：函数$f(x) = x^4$是严格凸的，但是在$x = 0$处，二阶导数为0

四、常见函数的凹凸性

凸函数：

• $\mathbb{R}$上的：

  1. 仿射函数：$\mathbb{R}$上的$f(x) = ax+b$，$\forall a, b \in \mathbb{R}$

  2. 指数函数：$\forall a \in \mathbb{R}$，函数$e^{ax}$在$\mathbb{R}$上是凸的

  3. 幂函数：$\mathbb{R}_{++}$上的$f(x) = x^a$，$\forall a \geq 1$或$a \leq 0$
  4. 绝对值幂函数：当$p \geq 1$时，函数$|x|^p$在$\mathbb{R}$上是凸函数。
  5. 负熵函数：$R_{++}$上的$f(x) = -x\log x$

•  

• $\mathbb{R}^n$上的：

  1. 范数：$\mathbb{R}^n$上的任意范数均为凸函数

  2. 最大值函数：函数$f(x) = max\{x_1, \cdots, x_n\}$在$\mathbb{R}^n$上是凸的

     直观解释：最大值函数的“上包络”会形成一条“包住所有函数曲线的上壳”，这种上壳形状天然向上弯曲，不会出现向下凹陷的部分，故保持凸性。

     证明：

     $$\begin{aligned} f(\theta x + (1 - \theta)y) &= \max(\theta x_i + (1- \theta)y_i)\\ &\leq \theta \max_ix_i + (1 - \theta) \max_i y_i\\ &= \theta f(x) + (1 - \theta)f(y) \end{aligned}$$

  3. 二次-线性分式函数：函数$f(x, y) = \frac{x^2}{y}$，其定义域为$\textbf{dom}f = \mathbb{R} \times \mathbb{R}_{++} = \{(x, y) \in R^2 |y > 0\}$，是凸函数。

     对于$y > 0$，$f_x(x, y) = 2\frac{x}{y}, f_y(x, y) = -\frac{x^2}{y^2}$。

     $f_{xx}(x, y) = \frac{2}{y}, f_{xy} = -\frac{2x}{y^2}, f_{yy}=\frac{2x^2}{y^3}$.

     因此 Hessian 矩阵为：

     $$H = \begin{bmatrix} f_{xx}(x, y) \quad f_{xy}(x,y)\\ f_{yx}(x, y) \quad f_{yy}(x,y) \end{bmatrix} = \begin{bmatrix} \frac{2}{y} \quad -\frac{2x}{y^2}\\ -\frac{2x}{y^2} \quad \frac{2x^2}{y^3} \end{bmatrix}$$

     因为$\det H = \frac{2}{y}\frac{2x^2}{y^3} - \frac{2x}{y^2}\frac{2x}{y^2} = 0$. 因此$H$是半正定的，$f(x,y)$是凸函数。

  4. 指数和的对数：函数$f(x) = \log(e^{x_1} + \cdots + e^{x_n})$在$\mathbb{R}^n$上是凸函数。

     这个函数可以看成最大值函数的可微近似，对于任意$x$，下面的不等式成立：

     $$\max \{x_1, \cdots, x_n\} \leq f(x) \leq \max\{x_1, \cdots, x_n\} + \log n.$$

凹函数：

• $\mathbb{R}$上的：

  1. 仿射函数：$\mathbb{R}$上的$f(x) = ax+b$，$\forall a, b \in \mathbb{R}$

  2. 幂函数：$\mathbb{R}_{++}$上的$f(x) = x^a$，$0 \leq a \leq 1$

  3. 对数函数：$\mathbb{R}_{++}$上的函数$\log x$

• $\mathbb{R}^n$上的：

  1. 几何平均：几何平均函数$f(x) = \left( \prod_{i=1}^n x_i \right)^{\frac{1}{n}}$在定义域$\textbf{dom} f =\mathbb{R}_{++}^n$上是凹函数。
  2. 对数-行列式：函数$f(X)=\log \det X$在定义域$\textbf{dom} f = S^n_{++}$上是凹函数。

五、上境图

函数$f:\mathbb{R}^n \rightarrow \mathbb{R}$的图像定义为

它是$\mathbb{R}^{n+1}$空间的一个子集。函数$f:\mathbb{R}^n \rightarrow \mathbb{R}$的上境图定义为

它也是$\mathbb{R}^{n+1}$空间的一个子集。

性质

• 一个函数是凸函数，当且仅当其上境图是凸集。

• 一个函数是凹函数，当且仅当其亚图式凸集。

  亚图：$\mathbb{hypo}f = \{(x, t) | x \in \mathbf{dom} f, t \leq f(x)\}$.

例题：

矩阵分式函数$f : \mathbb{R}^n \times \mathbb{S}^n \rightarrow \mathbb{R}$，$f(x,Y) = x^TY^{-1}x$在定义域$\mathbb{dom} f = \mathbb{R}^n \times \mathbb{S}^n_{++}$上是凸的。

考虑$f(x,Y)$的上境图，$\mathbb{epi} f = \{(x,Y, t)|x \in \mathbb{dom}f, Y \succ 0, f(x, Y) \leq t\}$.即$x^TY^{-1}x \leq t$$\Rightarrow$ $t-x^TY^{-1}x \geq 0$。利用Schur补，对$Y \succ 0$与标量$t$有等价关系：

$$x^TY^{-1}x \Leftrightarrow \begin{bmatrix} Y \quad x\\ x^T \quad t \end{bmatrix} \succeq 0$$

因此$\mathbb{epi} f=\{(x, Y, t)| Y \succ 0,\begin{bmatrix} Y \quad x\\ x^T \quad t \end{bmatrix} \succeq 0 \}$.

记$M(x, Y, t) = \begin{bmatrix}Y \quad x\\ x^T \quad t \end{bmatrix}$，映射$(x, Y, t) \rightarrow M(x, Y, t)$是仿射的。

而对于半正定锥$\begin{bmatrix}Y \quad x\\ x^T \quad t \end{bmatrix}$是凸的，因此$\mathbb{epi} f$也是凸集。

故矩阵分式函数$f$是凸集。

利用上境图证明凸函数的一阶条件

要证$f(y) \geq f(x) + \nabla f(x)^T(y-x)$，对于$(y, t) \in \mathbb{epi} f$，有：

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

可以描述为：

$$(y, t) \in \mathbb{epi} f \Rightarrow \begin{bmatrix}\nabla f(x)\\-1\end{bmatrix}^T \left(\begin{bmatrix}y \\ t \end{bmatrix} - \begin{bmatrix} x\\ f(x) \end{bmatrix} \right) \leq 0.$$

这意味着法向量为$(\nabla f(x), -1)$的超平面在边界点$(x, f(x))$支撑着$\mathbb{epi} f$

六、下水平集

函数$f:\mathbb{R}^n \rightarrow \mathbb{R}$的$\alpha-$下水平集定义为

对于任意$\alpha$值，凸函数的下水平集仍然是凸集。

如果$x, y \in C_a$，有$f(x) \leq a$，$f(y) \leq a$。因为$f$是凸函数，因此：

$$f(\theta x + (1- \theta)y) \leq \theta f(x) + (1 - \theta) f(y) = a.$$

故$\theta x + (1 - \theta)y \in C_a$.

但反过来不一定成立。

如果$f$是凹函数，那么由$\{x \in \textbf{dom}f | f(x) \geq a \}$定义的$\alpha -$上水平集也是凸集。

下水平集的性质可以用来判断集合的凸性：如果某个集合可以描述为

• 一个凸函数的下水平集
• 一个凹函数的上水平集

则集合是凸集。

七、Jensen 不等式及其拓展

基本不等式

有时也称作 Jensen 不等式。此不等式可以很方便地拓展至更多点的凸组合：

如果函数$f$是凸函数，$x_1, x_2, \cdots, x_K \in \textbf{dom}f, \theta_1, \cdots, \theta_k \geq 0$ 且 $\theta_1 + \cdots + \theta_k = 1$，则下式成立

考虑凸集时，次不等式可以拓展至无穷项和、积分以及期望。例如如果$S\subseteq \textbf{dom} f$上$p(x) \geq 0$ 且$\int_S p(x)dx = 1$，则当相应的积分存在时，下式成立

$$f\left( \int_S p(x)x dx \right) \leq \int_S f(x)p(x) dx$$

即$f(E(x)) \leq E(f(x))$.

惩罚不确定性：

假设$x \in \textbf{dom} f \subseteq \mathbb{R}^n$，则$z$是$\mathbb{R}^n$中的随机变量，其均值为零，则有

因此，随机化或者扰动（即在自变量上增加一个零均值的随机变量）从平均效果上不会减小凸函数的值。

附：做题细节

1. 函数$f(x) = \frac{1}{2}x^TPx + q^Tx +r$，求$\nabla^2f$

   先求$\nabla_x f$：对于$x^TPx = \sum_{i=1}^n(\sum_{j=1}^n x_iP_{ij})x_j = \sum_{i=1}^n\sum_{j=1}^n x_iP_{ij}x_j$.

   对$x_k$求偏导，因此$\nabla_{x_k}(x_ip_{ij}x_j)=p_{ij}\nabla_{x_k}(x_ix_j) = p_{ij}(\delta_{ik}x_j + \delta_{jk}x_i)$.其中$\delta_{ij} = 1$，当$i = k$，否则$\delta_{ij} = 0$. 对所有的$i,j$求和：

   $$\begin{aligned} \frac{\partial}{\partial x_k}(x^TPx)&=\sum_i \sum_j p_{ij}(\delta_{ik}x_j + \delta_{jk}x_i)\\ &= \sum_i\sum_jp_{ij}\delta_{ik}x_j + \sum_i \sum_j p_{ij}\delta_{jk}x_i\\ &=\sum_jp_{kj}x_j + \sum_ip_{ik}x_i\\ &=(Px)_K + (P^Tx)_k \end{aligned}$$

   再对$k$求和，得到：$\nabla_x(x^TPx) = (P + P^T)x$.
   

   故$\nabla_x f(x) = \frac{1}{2}(P +P^T)x +q^T$，因为$P \in S^n_{++}$，故$P = P^T$。

   因此$\nabla_x f(x) = Px+q^T$，因此$\nabla^2 f(x) = P$.

2. Schur 补

   考虑进行一下划分的矩阵$X \in S^n$

   $$X = \begin{bmatrix} A \quad B\\ B^T \quad C \end{bmatrix},$$

   其中$A \in S^k$。如果$\mathbb{det} A \neq 0$，矩阵

   $$S = C - B^TA^{-1}B$$

   被称为$A$在$X$中的Schur补。

   性质：$\mathbb{det}X = \mathbb{det}A \mathbb{det}S$.