3. 凸函数

3.1.1 定义

函数 $f: R^n \to R$ 是凸的。

条件：

如果 $\text{dom} \ f$ 是凸集，
对于任意 $x, y \in \text{dom} \ f$ 且 $0 \leq \theta \leq 1$，有： $f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y) \tag{3.1}$

补充：

当 $\leq$ 改为 $<$ 时，$f$ 为严格凸函数
定义 $f$ 为凹的，条件：$-f$ 为凸函数
定义 $f$ 为严格凹的，条件：$-f$ 为严格凸函数
某函数是仿射函数 $\iff$ 某函数既凸也凹
$f$ 是凸的 $\iff$ 任意 $x \in \text{dom} \ f$ 和任意向量 $v$，函数 $g(t) = f(x + tv)$ 是凸的（其定义域为 ${t | x + tv \in \text{dom} \ f}$）

3.1.2 扩展值延伸

条件：

$\bar{f}(x) = \begin{cases} f(x) & x \in \text{dom} \ f \\\\ \infty & x \notin \text{dom} \ f \end{cases}$

定义：$\bar{f}: R^n \to R \cup {\infty}$ 对扩展值延伸。

函数延伸由确定 $f$ 的定义域：$\text{dom} \ f = {x | \bar{f}(x) < \infty}$。
对于任意 $x$ 和 $y$，$0 < \theta < 1$，有： $\bar{f}(\theta x + (1-\theta)y) \leq \theta \bar{f}(x) + (1-\theta)\bar{f}(y)$
同理可定义凹函数定义域外部为−∞对其进行延伸。

3.1.3 一阶条件：

大前提：在开集 $\text{dom} \ f$ 可微，
有性质：函数是凸函数 $\iff \text{dom} \ f$ 是凸集且任意 $x, y \in \text{dom} \ f$，下式成立：

$f(y) \geq f(x) + \nabla f(x)^T (y - x) \tag{3.2}$

补充：

全局下估计：
由 $f(x) + \nabla f(x)^T (y - x)$ 得出的仿射函数 $y$ 即为函数 $f$ 在点 $x$ 附近的 Taylor 近似。不等式 (3.2) 表明，对于一个凸函数，其一阶 Taylor 近似实际上是原函数的一个全局下估计。反之，如果某个函数的一阶 Taylor 近似总是其全局下估计，那么这个函数是凸的。

不等式 (3.2) 说明从一个凸函数的局部信息（即它在某点处的函数值及导数），我们可以得到一些全局信息（如它的全局下估计）。这也许是凸函数的最重要的信息，因此对解释凸性函数以及凸优化问题的绝非常重要的性质。

示例：
下面是一个简单的例子，由不等式 (3.2) 可以知道，如果 $f(x)$ 在 $x_0$ 处对所有 $y \in \text{dom} \ f$，存在 $f(y) \geq f(x_0)$，即 $x_0$ 是函数 $f$ 的全局极小点。
关于严格凸，凸函数的一阶条件：类似于定义中的做法。

图例：

原不等式的几何解释如下：

函数 $f(x)$ 是凸的 $\iff$ $f(x) + \nabla f(x)^T (y - x)$ 是函数值 $f(y)$ 的下估计。

一阶条件的证明：

为了证明式 (3.2)，先考虑 $n=1$ 的情况。我们证明可微函数 $f: R \to R$ 是凸函数的充要条件是对于 $\text{dom} \ f$ 内的任意 $x$ 和 $y$，有：

$f(y) \geq f(x) + f'(x)(y - x). \tag{3.4}$

首先假设 $f$ 是凸函数，且 $x, y \in \text{dom} \ f$，因为 $\text{dom} \ f$ 是凸集（某个区间），对于任意 $0 < t < 1$，我们有 $z = x + t(y - x) \in \text{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 \to 0$，可以得到不等式 (3.4)。

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

$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: R^n \to R$。设 $x, y \in R^n$，考虑过这两点的直线上的函数 $f$，即函数 $g(t) = f(ty + (1 - t)x)$，此函数对于 $t$ 求导可得 $g’(t) = \nabla f(ty + (1 - t)x)^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$ 均成立，因此若 $\tilde{t}y + (1 - \tilde{t})x \in \text{dom} \ f$ 以及 $\tilde{t}y + (1 - \tilde{t})x \in \text{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$ 是凸的。

个人思考：

先考虑一元，在考虑 $n$【利用构造函数 $g(t) = f(ty + (1 - t)x)$ 化为 1 元情况】。
利用凸函数定义取极限证明必要性。
构造 $z$ 满足凸函数定义结构证明充分性。

3.1.4 二阶条件：

大前提：在开集 $\text{dom} \ f$ 上二阶可微，
有性质：函数是凸函数 $\iff$ 其 Hessian 矩阵为半正定矩阵 $\iff$ 对于所有 $x \in \text{dom} \ f$，有：

$\nabla^2 f(x) \succeq 0.$

补充：

严格凸函数、凹函数的二阶条件也是在不等号上做文章，类似可得。

3.1.5 一些凸函数的例子：

指数函数：对任意 $a \in \mathbb{R}$，函数 $e^{ax}$ 在 $\mathbb{R}$ 上是凸的。
幂函数：当 $a \geq 1$ 或 $a \leq 0$ 时，$x^a$ 在 $\mathbb{R}{++}$ 上是凸函数；当 $0 < a \leq 1$ 时，$x^a$ 在 $\mathbb{R}{+}$ 上是凹函数。
绝对值幂函数：当 $p \geq 1$ 时，函数 $|x|^p$ 在 $\mathbb{R}$ 上是凸函数。
对数函数：函数 $\log x$ 在 $\mathbb{R}_{++}$ 上是凹函数。
负幂：函数 $x \mapsto \log x$ 在其定义域上是凸函数。（定义域为 $\mathbb{R}{++}$ 或者 $\mathbb{R}+$，当 $x = 0$ 时定义函数值为 $0$。）

范数：$\mathbb{R}^n$ 上的任意范数均为凸函数。
最大值函数：函数 $f(x) = \max{x_1, \cdots, x_n}$ 在 $\mathbb{R}^n$ 上是凸的。
二次-线性分式函数：函数 $f(x, y) = x^2 / y$，其定义域为 $\text{dom} \ f = \mathbb{R} \times \mathbb{R}_{++} = \{(x, y) \in \mathbb{R}^2 \ | \ y > 0\},$ 是凸函数（如图 3.3 所示）。
指数和的对数：函数 $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.$ （当 $x$ 的所有分量都相等时取等号。）
几何平均：几何平均函数 $f(x) = \left(\prod_{i=1}^n x_i\right)^{1/n}$ 在定义域 $\text{dom} \ f = \mathbb{R}_{++}$ 上是凹函数。
对数-行列式：函数 $f(X) = \log \det X$ 在定义域 $\text{dom} \ f = \mathbb{S}_{++}^n$ 上是凹函数。

范数

如果函数 $f : \mathbb{R}^n \to \mathbb{R}$ 是范数，任取 $0 \leq \theta \leq 1$，有：

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

上述不等式可以由三角不等式得到，当范数满足齐次性时，上述不等式取等号。

最大值函数

对任意 $0 \leq \theta \leq 1$，函数 $f(x) = \max x_i$ 满足：

$f(\theta x + (1 - \theta)y) = \max(\theta x_i + (1 - \theta)y_i) \leq \theta \max x_i + (1 - \theta) \max y_i = \theta f(x) + (1 - \theta)f(y).$

二次-线性分式函数

为了说明二次-线性分式函数 $f(x, y) = x^2 / y$ 是凸的，我们注意到，对于 $y > 0$，有：

$\nabla^2 f(x, y) = \frac{2}{y^3} \begin{bmatrix} y^2 & -xy \\\\ -xy & x^2 \end{bmatrix} = \frac{2}{y^3} \begin{bmatrix} y \\\\ -x \end{bmatrix} \begin{bmatrix} y & -x \end{bmatrix} \succeq 0.$

指数和的对数

指数和的对数函数的 Hessian 矩阵为：

$\nabla^2 f(x) = \frac{1}{(1^T z)^2} \left((1^T z) \text{diag}(z) - zz^T \right),$

其中 $z = (e^{x_1}, \cdots, e^{x_n})$。为了说明 $\nabla^2 f(x) \succeq 0$，我们证明对任意向量 $v$，有 $v^T \nabla^2 f(x) v \geq 0$，即：

$v^T \nabla^2 f(x) v = \frac{1}{(1^T z)^2} \left(\left(\sum_{i=1}^n v_i^2 z_i\right)\left(\sum_{i=1}^n z_i\right) - \left(\sum_{i=1}^n v_i z_i\right)^2\right) \geq 0.$

上述不等式可以应用 Cauchy-Schwarz 不等式 $a^T a \cdot b^T b \geq (a^T b)^2$ 得到，此时向量 $a$ 和 $b$ 的分量为 $a_i = v_i \sqrt{z_i}$，$b_i = \sqrt{z_i}$。

几何平均

类似地，我们说明，几何平均函数 $f(x) = \left(\prod{i=1}^n x_i\right)^{1/n}$ 在定义域 $\text{dom} \ f = \mathbb{R}{++}$ 上是凹的。其 Hessian 矩阵 $\nabla^2 f(x)$ 可以通过下面两个公式给出：

$\frac{\partial^2 f(x)}{\partial x_k^2} = -\frac{(n-1)\left(\prod_{i=1}^n x_i\right)^{1/n}}{n^2 x_k^2}, \quad \frac{\partial^2 f(x)}{\partial x_k \partial x_l} = \frac{\left(\prod_{i=1}^n x_i\right)^{1/n}}{n^2 x_k x_l} \quad (k \neq l).$

因此 $\nabla^2 f(x)$ 具有如下表达式：

$\nabla^2 f(x) = \frac{\prod_{i=1}^n x_i^{1/n}}{n^2} \left(n \ \text{diag}\left(1/x_1^2, \cdots, 1/x_n^2\right) - qq^T\right),$

其中 $q_i = 1/x_i$。我们只需要证明 $\nabla^2 f(x) \preceq 0$，即对于任意向量 $v$，有：

$v^T \nabla^2 f(x) v = \frac{\prod_{i=1}^n x_i^{1/n}}{n^2} \left(n \sum_{i=1}^n \frac{v_i^2}{x_i^2} - \left(\sum_{i=1}^n \frac{v_i}{x_i}\right)^2\right) \leq 0.$

这样可以应用 Cauchy-Schwarz 不等式 $(a^T a)(b^T b) \geq (a^T b)^2$ 得到，只需令向量 $a = 1$，向量 $b_i = v_i / x_i$。

对数-行列式

对于函数 $f(X) = \log \det X$，我们可以将其转化为任意直线上单变量函数来验证它是凹的。令 $X = Z + tV$，其中 $Z, V \in \mathbb{S}^n$，定义 $g(t) = f(Z + tV)$，自变量 $t$ 满足 $Z + tV \succ 0$。不失一般性，假设 $t = 0$ 满足条件，即 $Z \succ 0$。我们有：

$g(t) = \log \det(Z + tV) = \log \det(Z^{1/2}(I + tZ^{-1/2}VZ^{-1/2})Z^{1/2}),$ $= \sum_{i=1}^n \log(1 + t\lambda_i) + \log \det Z,$

其中 $\lambda_1, \cdots, \lambda_n$ 是矩阵 $Z^{-1/2}VZ^{-1/2}$ 的特征值。

因此下式成立：

$g'(t) = \sum_{i=1}^n \frac{\lambda_i}{1 + t\lambda_i}, \quad g''(t) = -\sum_{i=1}^n \frac{\lambda_i^2}{(1 + t\lambda_i)^2}.$

因为 $g’’(t) \leq 0$，函数 $g$ 是凹的。

3.1.6 下水平集

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

$C_\alpha = \{x \in \text{dom} \ f \ | \ f(x) \leq \alpha\}.$

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

证明：

由定义得：如果 $x, y \in C_\alpha$，则有 $f(x) \leq \alpha, f(y) \leq \alpha$，

因此对于任意 $0 \leq \theta \leq 1$，有 $f(\theta x + (1 - \theta)y) \leq \alpha$，

即 $\theta x + (1 - \theta)y \in C_\alpha$。

反过来不一定正确：某个函数的所有下水平集都是凸集，但这个函数可能不是凸函数。

例如，函数 $f(x) = -e^{-x}$ 在 $\mathbb{R}$ 上不是凸函数（实际上，它是严格凹函数），但是其所有下水平集均为凸集。

如果 $-f$ 是凸函数，则由 ${x \in \text{dom} \ f \ | \ f(x) > \alpha}$ 定义的 $\alpha$-上水平集也是凸集。

下水平集的性质可以用来判断集合的凸性，若某个集合可以描述为一个凸函数的下水平集，或者一个凹函数的上水平集，则其是凸集。

3.1.7 上镜图

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

$\{(x, f(x)) \ | \ x \in \text{dom} \ f\},$

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

函数 $f : \mathbb{R}^n \to \mathbb{R}$ 的上镜图定义为：

$\text{epi} \ f = \{(x, t) \ | \ x \in \text{dom} \ f, \ f(x) \leq t\}.$

它也是 $\mathbb{R}^{n+1}$ 空间的一个子集。（“Epi”是“之上的”意思，所以上镜图的英文 epigraph 是“在函数图像之上”的意思。）

凸集和凸函数的联系可以通过上掩图来建立：

一个函数是凸函数，当且仅当其上掩图是凸集。
一个函数是凹函数，当且仅当其下掩图 $\text{hypo} \ f = \{(x, t) \ | \ t \geq f(x)\},$ 是凸集。

3.1.8 Jensen 不等式及其扩展

基本不等式

$f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta)f(y),$

称作 Jensen 不等式。

可以很方便地扩展至更多点的凸组合：

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

$f(\theta_1 x_1 + \cdots + \theta_k x_k) \leq \theta_1 f(x_1) + \cdots + \theta_k f(x_k).$

考虑凸集时，此不等式可以扩展至积分项和期望。

例如，如果在 $S \subseteq \text{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.$

概率情形的扩展

扩展到更一般的情况，我们可以采用其支撑属于 $\text{dom} \ f$ 的任意概率测度。

如果 $x$ 是随机变量，事件 $x \in \text{dom} \ f$ 发生的概率为 $1$，函数 $f$ 是凸函数，且期望存在时，我们有：

$f(\mathbb{E}x) \leq \mathbb{E}f(x). \tag{3.5}$

设随机变量 $x$ 的可能取值为 ${x_1, x_2}$，相应地取值概率为 $\text{prob}(x = x_1) = \theta$，$\text{prob}(x = x_2) = 1 - \theta$，则一般形式 (3.5) 可以得到基本不等式 (3.1)。所以不等式 (3.5) 可以刻画出：如果函数 $f$ 不是凸函数，那么存在随机变量 $x, x \in \text{dom} \ f$，以概率 $1$ 发生，使得 $f(\mathbb{E}x) \geq \mathbb{E}f(x)$。

上述所有不等式均称为 Jensen 不等式。

3.1.9 不等式

考虑算术-几何平均不等式：
$\sqrt{ab} \leq \frac{a + b}{2}, \tag{3.6}$
其中 $a, b > 0$。我们可以利用凸性和 Jensen 不等式得到此不等式。函数 $-\log x$ 是凸函数：利用 Jensen 不等式，令 $\theta = 1/2$，可得：
$-\log\left(\frac{a + b}{2}\right) \leq -\frac{\log a + \log b}{2}.$
等式两边取指数即可得到式 (3.6)。
我们来证明 Hölder 不等式：对 $p > 1$，$1/p + 1/q = 1$，以及 $x, y \in \mathbb{R}^n$，有：
$\sum_{i=1}^n x_i y_i \leq \left(\sum_{i=1}^n |x_i|^p\right)^{1/p} \left(\sum_{i=1}^n |y_i|^q\right)^{1/q}.$

由于 $-\log x$ 的凸性以及 Jensen 不等式，我们可以得到更为一般的算术-几何平均不等式：

$a^\theta b^{1-\theta} \leq \theta a + (1 - \theta)b,$

其中 $a, b > 0, 0 \leq \theta \leq 1$。令：

$a = \frac{|x_i|^p}{\sum_{j=1}^n |x_j|^p}, \quad b = \frac{|y_i|^q}{\sum_{j=1}^n |y_j|^q}, \quad \theta = 1/p,$

可以得到如下不等式：

$\left(\frac{|x_i|^p}{\sum_{j=1}^n |x_j|^p}\right)^{1/p} \left(\frac{|y_i|^q}{\sum_{j=1}^n |y_j|^q}\right)^{1/q} \leq \frac{|x_i|^p}{p \sum_{j=1}^n |x_j|^p} + \frac{|y_i|^q}{q \sum_{j=1}^n |y_j|^q}.$

对 $i$ 进行求和可以得到 Hölder 不等式。

凸函数的基本定义与性质