一、凸函数

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)$ 就是上凸函数。

2. 一些常见的凸函数

• 任何线性函数 $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 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$ 为上凸函数。

3. 凸函数的性质

i. 凸函数的基本变换性质

• 如果 $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. 的证明：需要下水平集的定义。

ii. 凸函数的仿射变换不变性

• 对于 $\R^N \to \R$ 上的凸函数 $z = f(\boldsymbol y)$ 和 $\R^M \to \R^N$ 上的仿射变换 $\boldsymbol y = \boldsymbol A \boldsymbol x + \boldsymbol b$， $g(\boldsymbol x) = f(\boldsymbol A \boldsymbol x + \boldsymbol b)$ 也是凸函数。

  证明

  因为 $f(\boldsymbol y)$ 的凸性，对于 $\forall \boldsymbol y_1, \boldsymbol y_2 \in \R^N$ 和 $\forall \lambda \in \R$ 有：

  $$ f(\lambda \boldsymbol y_1 + (1-\lambda) \boldsymbol y_2) \le \lambda f(\boldsymbol y_1) + (1-\lambda) f(\boldsymbol y_2) $$

  要证明的是对于 $\forall \boldsymbol x_1, \boldsymbol x_2 \in \R^N$ 和 $\forall \lambda \in \R$ ：

  $$ f(\boldsymbol A (\lambda \boldsymbol x_1 + (1-\lambda) \boldsymbol x_2) + \boldsymbol b) \le \lambda f(\boldsymbol A \boldsymbol x_1 + \boldsymbol b) + (1-\lambda) f(\boldsymbol A \boldsymbol x_2 + \boldsymbol b) $$

  可以这样推导就得证了：

  $$ \begin{align*}

  f(\boldsymbol A (\lambda \boldsymbol x_1 + (1-\lambda) \boldsymbol x_2) + \boldsymbol b)

  &= f(\lambda ( \boldsymbol A \boldsymbol x_1 + \boldsymbol b) + (1-\lambda) (\boldsymbol A \boldsymbol x_2 + \boldsymbol b)) \\

  &\le \lambda f( \boldsymbol A \boldsymbol x_1 + \boldsymbol b) + (1-\lambda) f (\boldsymbol A \boldsymbol x_2 + \boldsymbol b)

  \end{align*} $$

二、凸规划

1. 凸规划问题及其性质

• 【凸规划问题的定义】可行域是凸集、目标函数是下凸函数的最优化问题称为下凸规划问题。

• 【凸规划的最优解性质】设 $\boldsymbol x^*$ 为下凸规划问题（可行域为 $D \subset \R^N$，目标函数为 $f: \R^N \to \R$）的一个局部最优解：

  1. $\boldsymbol x^*$ 为全局最优解。
  2. 如果目标函数严格下凸，那么 $\boldsymbol x^*$ 是唯一的全局最优解。

  1. 的证明：反证法。

  • 如果 $\boldsymbol x^$ 不是全局最优，说明存在另一可行点 $\boldsymbol y$ 满足 $f(\boldsymbol y) < f(\boldsymbol x^)$。

  • 因为可行域的凸性，$\forall \lambda \in (0, 1)$，点 $(\lambda \boldsymbol x^* + (1-\lambda) \boldsymbol y)$ 也是可行点。

  • 因为目标函数的下凸性：

    $$ \begin{align*}

    f(\lambda \boldsymbol x^* + (1-\lambda) \boldsymbol y) &\le \lambda f(\boldsymbol x^*) + (1-\lambda) f(\boldsymbol y) \\

    &< \lambda f(\boldsymbol x^) + (1-\lambda) f(\boldsymbol x^) = f(\boldsymbol x^*)

    \end{align*} $$

  • 即 $f(\lambda \boldsymbol x^* + (1-\lambda) \boldsymbol y) < f(\boldsymbol x^)$。由于 $\lambda$ 可以无限趋近 $1$，这说明在 $\boldsymbol x^$ 无限小邻域内存在比其函数值更小的点，因而 $\boldsymbol x^*$ 不是局部最优解。

  2. 的证明：反证法。

  • 设 $\boldsymbol x^, \boldsymbol y^$ 都是全局最优解，有 $f(\boldsymbol x^) = f(\boldsymbol y^)$。

  • 因为目标函数的严格下凸性：

    $$ \begin{align*}

    f(\lambda \boldsymbol x^* + (1-\lambda) \boldsymbol y^) &< \lambda f(\boldsymbol x^) + (1-\lambda) f(\boldsymbol y^*) \\

    &= \lambda f(\boldsymbol x^) + (1-\lambda) f(\boldsymbol x^) = f(\boldsymbol x^*)

    \end{align*} $$

  • 即 $f(\lambda \boldsymbol x^* + (1-\lambda) \boldsymbol y^) < f(\boldsymbol x^)$。这与 $\boldsymbol x^*$ 是全局最优解矛盾。

2. 凸函数的微分特征

• 【函数值特征】对于定义在 $\R^N$ 上的函数 $f: \R^N \to \R$，其为 $\R^N$ 上的下凸函数的充要条件为：$\forall \boldsymbol p, \boldsymbol q \in \R^N, \ \forall \alpha \in \R$，单变量函数 $\phi(\alpha; \boldsymbol p, \boldsymbol q) = f(\boldsymbol p + \alpha \boldsymbol q)$ 都是 $\R$ 上的下凸函数。

  证略，几何直观非常明显。

• 【泰勒展开】回顾 $f: \R^N \to \R$ 在 $\boldsymbol x$ 处的泰勒展开式：

  $$ \begin{align*}

  f(\boldsymbol y) = f(\boldsymbol x) + (\nabla f(\boldsymbol x))^{\rm T} (\boldsymbol y - \boldsymbol x) + \frac 12 (\boldsymbol y - \boldsymbol x)^{\rm T} \nabla^2 f(\boldsymbol x) (\boldsymbol y - \boldsymbol x) + o(\| \boldsymbol y - \boldsymbol x \|^2)

  \end{align*} $$

• 【一阶微分特征】对于定义在非空开凸集 $D_{\rm o} \subset \R^N$ 上的可微函数 $f : D_{\rm o} \to \R$，则关于其一阶导矢 $\nabla f(\boldsymbol x)$：

  1. $f$ 为下凸函数的充要条件为：

     $$ \forall \boldsymbol x, \boldsymbol y \in D_{\rm o} , \, f(\boldsymbol x) + (\nabla f(\boldsymbol x))^{\rm T} (\boldsymbol y - \boldsymbol x) \le f(\boldsymbol y) $$

     • 可记为「所有切线都是对函数值的低估」。

  2. $f$ 为严格下凸函数的充要条件为：

     $$ \forall \boldsymbol x, \boldsymbol y \in D_{\rm o} , \, \boldsymbol x \neq \boldsymbol y, \, f(\boldsymbol x) + (\nabla f(\boldsymbol x))^{\rm T} (\boldsymbol y - \boldsymbol x) < f(\boldsymbol y) $$

  

  证略。可参见袁亚湘、孙文瑜（1997）。