一、凸函数

1. 凸函数的相关定义

• **【凸函数的定义】**对于凸集 $D \subset \R^N$ 上的函数 $f: D\to \R$，如果 $\forall \boldsymbol x, \boldsymbol y \in D, \forall \lambda \in [0, 1]$，有：

  $$ f(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \lambda f(\boldsymbol x) + (1-\lambda) f(\boldsymbol y) $$

  称 $f$ 为 $D$ 上的下凸函数（另因英语为 convex funcion 又称凸函数）；

  • 这一定义可称为：所有弦都在曲线之上。

  

  • 如果 $[0, 1]$ 换成 $(0, 1)$、增加条件 $\boldsymbol x \neq \boldsymbol y$、$\le$ 换为 $<$，称为严格下凸函数。
  • 如果 $\le$ 换为 $\ge$，称为上凸函数（另因英语为 concave funcion 又称凹函数）。严格上凸函数同理。
    • 显然，如果 $f(\boldsymbol x)$ 是下凸函数，$-f(\boldsymbol x)$ 就是上凸函数。

• **【强下凸函数的定义】**如果存在常数 $m > 0$ 使得 $g(\boldsymbol x )= f(\boldsymbol x ) - \frac m 2 \| \boldsymbol x \|^2$ 为下凸函数。那么 $f$ 是强下凸函数，$m$ 为强凸参数。

  • **【强下凸函数的等价定义】**如果存在常数 $m > 0$ 使得 $\forall \boldsymbol x, \boldsymbol y \in D, \, \forall \lambda \in [0, 1]$，有：

    $$ f(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \lambda f(\boldsymbol x) + (1-\lambda) f(\boldsymbol y) - \frac m 2 \lambda (1-\lambda) \| \boldsymbol x - \boldsymbol y \|^2 $$

    那么 $f$ 是强下凸函数，$m$ 为强凸参数。

• 【拟/准 (quasic-) 下凸函数的定义】：对于凸集 $D \subset \R^N$ 上的函数 $f: D\to \R$，如果 $\forall \boldsymbol x, \boldsymbol y \in D, \forall \lambda \in [0, 1]$，有：

  $$ f(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \max \{ f(\boldsymbol x), f(\boldsymbol y) \} $$

  • 拟下凸函数的弦只需要始终比较高的端点要低即可。

    

  • 一元情况下，所有单调函数都同时是拟上凸函数与拟下凸函数。

• **【强凸、凸、拟凸的关系】**强凸函数一定是凸函数；凸函数一定是拟凸函数。

  证明（凸 → 拟凸）

  $$ f(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \lambda f(\boldsymbol x) + (1-\lambda) f(\boldsymbol y) \le \max \{ f(\boldsymbol x), f(\boldsymbol y) \} $$

2. 一些常见的凸函数

• 常见的一元凸函数

  • $y={\rm e}^{a x}$（$a, x \in \R$）
  • $y=x^\alpha$（$x > 0$，且 $\alpha \ge 1$ 或 $\alpha \le 0$）
  • $y = x \ln x$（$x > 0$）

• 任何线性函数 $f(\boldsymbol x; \boldsymbol a) = \boldsymbol a^{\rm T} \boldsymbol x$ 既是 $\R^N$ 上的下凸函数，也是上凸函数。

  这是因为 $\forall \boldsymbol x, \boldsymbol y \in \R^N, \forall \lambda \in [0, 1], \, f(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) = \lambda f(\boldsymbol x) + (1-\lambda) f(\boldsymbol y)$。

  • 当然 $f(\boldsymbol x) = \boldsymbol a^{\rm T} \boldsymbol x + \boldsymbol b$ 也是。

• 所有范数都是凸函数（通过三角不等式可证）。

• $y = {\rm tr} (\boldsymbol A^{\rm T} \boldsymbol X)$（矩阵的 F-内积）是凸函数。

• 任何二次函数 $f(\boldsymbol x; \boldsymbol G, \boldsymbol b) = \frac 12 \boldsymbol x^{\rm T} \boldsymbol G \boldsymbol x + \boldsymbol b^{\rm T} \boldsymbol x$ 是 $\R^N$ 上的严格下凸函数，当且仅当 $\boldsymbol G$ 是正定矩阵。

  • 顺带一提，记得夹心糖式（二次型）$\boldsymbol x^{\rm T} \boldsymbol G \boldsymbol x=\sum_{i=1}^{N} \sum_{j=1}^{N} g_{ij}x_i x_j$。

  证明

  必要性：

  • $\forall \boldsymbol x, \, \boldsymbol y \in \R^N, \boldsymbol x \neq \boldsymbol y, \, \forall \lambda \in (0, 1), \, f(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) < \lambda f(\boldsymbol x) + (1-\lambda) f(\boldsymbol y)$ 可推出 $(\boldsymbol x - \boldsymbol y)^{\rm T} \boldsymbol G (\boldsymbol x - \boldsymbol y) > 0$，过程如下图。

    

  • 因为 $\boldsymbol x \neq \boldsymbol y$，作 $\boldsymbol z = \boldsymbol x - \boldsymbol y$ 可取遍 $\R^N / \{ \boldsymbol 0 \}$，因而有：$\forall \boldsymbol z \in \R^N / \{ \boldsymbol 0 \}, \ \boldsymbol z^{\rm T} \boldsymbol G \boldsymbol z > 0$，这说明 $\boldsymbol G$ 是正定矩阵。

  充分性：

  • $\boldsymbol G$ 是正定矩阵，因而 $\forall \boldsymbol z \in \R^N / \{ \boldsymbol 0 \}, \ \boldsymbol z^{\rm T} \boldsymbol G \boldsymbol z > 0$，因而 $\forall \boldsymbol x, \boldsymbol y \in \R^N, \, \boldsymbol x \neq \boldsymbol y, \, \boldsymbol x - \boldsymbol y \neq \boldsymbol 0, \, (\boldsymbol x - \boldsymbol y)^{\rm T} \boldsymbol G (\boldsymbol x - \boldsymbol y) > 0$。过程沿着上图逆着推一次，即证明函数的下凸性。

  • 类似地：
    • $\boldsymbol G$ 为半正定矩阵 $\Rightarrow$ $f$ 为下凸函数。
    • $\boldsymbol G$ 为负定矩阵 $\Rightarrow$ $f$ 为严格上凸函数。
    • $\boldsymbol G$ 为半负定矩阵 $\Rightarrow$ $f$ 为上凸函数。

• $f(\boldsymbol X) = -\ln \det \boldsymbol X$（$\boldsymbol X \in {\mathcal S_{++}^n}$，即定义域是全体实对称正定矩阵）是凸函数。

  证明（未完成）

  • 下面也把 ${\rm det} (\cdot)$ 记为 $| \cdot |$。

  • 任取 $\boldsymbol X \in {\mathcal S_{++}^n}$ 和 $\boldsymbol V \in {\mathcal S}^n$（任意实对称矩阵），作 $g(t) = -\ln \det(\boldsymbol X + t \boldsymbol V)$。

  • 有如下变换（全忘光是怎么回事了）

    $$ \begin{align*}

    |\boldsymbol X + t \boldsymbol V | &= |\boldsymbol X| \cdot \left|\boldsymbol I + t \boldsymbol X^{-\frac12} \boldsymbol V \boldsymbol X^{-\frac12} \right| \\

    &= | \boldsymbol X | \cdot\prod_{i=1}^n (1 + t \lambda_i)

    \end{align*} $$

    • 其中 $\lambda_i$ 是 $\boldsymbol X^{-\frac12} \boldsymbol V \boldsymbol X^{-\frac12}$ 的第 $i$ 个特征值。

  • 因而：

    $$ \begin{align*}

    g(t) &= -\ln |\boldsymbol X + t \boldsymbol V | \\

    &= -\ln \left( | \boldsymbol X | \cdot\prod_{i=1}^n (1 + t \lambda_i) \right) \\

    &= -\ln |\boldsymbol X| - \sum_{i=1}^n \ln (1 + t \lambda_i)

    \end{align*} $$

  • 可知 $g$ 关于 $t$ 是凸的，根据下文的「凸函数的直线截取充要条件」可以知道 $f$ 关于 $\boldsymbol X$ 是凸的。

3. 凸函数的性质

i. 凸函数的连续性和可导性

• **【连续性】**凸函数在其定义域的所有内点处都是连续的。
• **【可导性】**设 $f : \R^n \to \R$ 是凸函数，对于任意的 $\boldsymbol x \in \R^n$ 和方向向量 $\boldsymbol d \in \R^n, \, \boldsymbol d \neq \boldsymbol 0$，$f$ 在 $\boldsymbol x$ 处沿方向 $\boldsymbol d$ 的方向导数存在。

ii. 凸函数的变换或组合性质

• 如果 $f, f_1, f_2, \cdots, f_M: D \to \R$ 均是定义在凸集 $D \subset \R^N$ 上的下凸函数：

  1. 给定 $\alpha \ge 0$，$\alpha f(\boldsymbol x)$ 也是下凸函数。
  2. $f_1(\boldsymbol x) + f_2(\boldsymbol x)$ 也是下凸函数。
     • 因而凸函数的非负线性组合（凸锥组合）还是凸函数。
  3. $\max_{i=1}^{M} | f_i(\boldsymbol x) |$ 也是下凸函数。

  1. 的证明

  • $\forall \boldsymbol x, \boldsymbol y \in D, \forall \lambda \in [0, 1], \, f(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \lambda f(\boldsymbol x) + (1-\lambda) f(\boldsymbol y)$ 可推：

    $$ \alpha f(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \lambda \alpha f(\boldsymbol x) + (1-\lambda) \alpha f(\boldsymbol y) $$

  2. 的证明

  • $\forall \boldsymbol x, \boldsymbol y \in D, \, \forall \lambda \in [0, 1]$：

    • $f_1(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \lambda f_1(\boldsymbol x) + (1-\lambda) f_1(\boldsymbol y)$；
    • $f_2(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \lambda f_2(\boldsymbol x) + (1-\lambda) f_2(\boldsymbol y)$。

  • 两式求和得到：

    $$ (f_1+f_2)(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \lambda (f_1+f_2)(\boldsymbol x) + (1-\lambda) (f_1+f_2)(\boldsymbol y) $$

  3. 的证明：需要下水平集的定义。