一、凸函数

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

二、凸规划

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. 下水平集

• 【下水平集的定义】对于函数 $f:D \to \R$，$D \subset \R^N$，其 $\alpha$ 下水平集为：$L(\alpha) = \{ \boldsymbol x \in D \, | \, f(\boldsymbol x) \le \alpha\}$。

• 【凸函数的下水平集是凸集】函数 $f$ 是凸函数的充分必要条件为：其任意 $\alpha$（$\alpha \in \R$）下水平集 $L(\alpha)$ 为凸集。

  证明

  • $\forall \boldsymbol x, \boldsymbol y \in L(\alpha)$，有 $f(\boldsymbol x) \le \alpha, \, f(\boldsymbol y) \le \alpha$；又属于凸函数性质，有 $\forall \lambda \in [0, 1]$：

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

  • 根据 $\lambda f(\boldsymbol x) \le \lambda \alpha$、$(1 - \lambda) f(\boldsymbol x) \le (1 - \lambda) \alpha$，因而 $f(\lambda \boldsymbol x + (1-\lambda) \boldsymbol y) \le \alpha$，得到 $\lambda \boldsymbol x + (1-\lambda) \boldsymbol y \in L(\alpha)$。

3. 凸函数的微分特征

• 【函数值特征】对于定义在 $\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$ 上的下凸函数。

  证略。

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

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

     $$ \forall \boldsymbol x, \boldsymbol y \in D , \, 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 , \, \boldsymbol x \neq \boldsymbol y, \, f(\boldsymbol x) + (\nabla f(\boldsymbol x))^{\rm T} (\boldsymbol y - \boldsymbol x) < f(\boldsymbol y) $$

  

  证略。