2. 凸函数

# 定义与例子

1. 凸函数 Convex Function：定义在凸集 $C$ 上的函数 $f: C \to \mathbb{R}$，如果对于任意 $x_1, x_2 \in C$ 和 $\forall \lambda \in [0, 1]$，都有

   $$f(\lambda x_1 + (1 - \lambda) x_2) \leq \lambda f(x_1) + (1 - \lambda) f(x_2)$$

   则称 $f$ 是凸函数。

   • 凸函数的定义域必须是凸集
   • 凸函数的图像位于连接任意两点 $(x_1, f(x_1))$ 和 $(x_2, f(x_2))$ 的线段的下方

2. 凹函数 Concave Function：$-f$ 是凸函数

3. Jenson 不等式：对于凸函数 $f$，$p_i \geq 0, i = 1, \ldots, k$ 且 $\sum_{i=1}^k p_i = 1$，都有

   $$f\left(\sum_{i=1}^k p_i x_i\right) \leq \sum_{i=1}^k p_i f(x_i)$$

   对于凹函数 $f$，不等式方向相反

4. 常见的凸函数

   • 指数函数 $e^{ax}$、负对数函数 $- \log(ax)$
   • 仿射函数 $a^T x + b$（同时是凹函数）
   • 正定或半正定二次函数 $x^T P x + q^T x + r$，其中 $P \succeq 0$
   • 范数函数 $\|x\|_p$，其中 $p \geq 1$（可能不是处处可微的）
   • 幂函数 $x^a$、绝对值幂函数 $|x|^a$（$a \geq 1$ 为凸函数，$0 < a \leq 1$ 为凹函数）
   • log-sum-exp 函数 $f(x) = \log(\sum_{i=1}^n e^{x_i})$
   • 几何平均函数 $f(x) = (x_1 x_2 \ldots x_n)^{1/n}$，定义域为 $\mathbb{R}^n_{++}$ 是凹函数

5. 凸函数与连续性：定义在开的凸集上的凸函数在其定义域的内部处处连续（证明）

   • 推论：定义在开的凸集上的凸函数必有极小值

6. 凸函数的一阶条件：定义在凸集 $C$ 上的可微函数 $f: C \to \mathbb{R}^n$ 是凸函数的充分必要条件是对于任意 $x_1, x_2 \in C$，都有

   $$f(x_2) \geq f(x_1) + \nabla f(x_1)^T (x_2 - x_1)$$

   • 该不等式表明，凸函数在任意点处的切平面位于函数图像的下方
   • 等价描述：$[\nabla f(x_2) - \nabla f(x_1)]^T (x_2 - x_1) \geq 0$

7. 凸函数的二阶条件：定义在开凸集 $C$ 上的二次可微函数 $f: C \to \mathbb{R}^n$ 是凸函数的充分必要条件是对于任意 $x \in C$，都有 $\nabla^2 f(x) \succeq 0$

8. 多元凸函数的一维刻画：多元函数 $f: \mathbb{R}^n \to \mathbb{R}$ 是凸函数的充分必要条件是对于任意 $x \in \mathbb{R}^n$ 和任意方向 $v \in \mathbb{R}^n$，一元函数 $g(t) = f(x + t v), t \in \mathbb{R}$ 是凸函数

# 强凸

1. 强凸定义：若函数 $f(x) - \frac{\mu}{2} \|x\|^2$ 是凸函数，其中 $\mu > 0$，则称 $f$ 是度量为 $\mu$ 的强凸函数

2. 强凸的判定：以下性质等价

   • $f$ 是度量为 $\mu$ 的强凸函数
   • 对于任意 $x_1, x_2 \in C$，有 $(\nabla f(x_2) - \nabla f(x_1))^T (x_2 - x_1) \geq \mu \|x_2 - x_1\|^2$
   • 对于任意 $x \in C$，有 $\nabla^2 f(x) \succeq \mu I$
   • 对于任意 $x_1, x_2 \in C$，有
     $f(x_2) \geq f(x_1) + \nabla f(x_1)^T (x_2 - x_1) + \frac{\mu}{2} \|x_2 - x_1\|^2$

3. Lipschitz 连续：若存在常数 $L > 0$，使得对于任意 $x_1, x_2 \in C$，都有

   $$\| \nabla f(x_2) - \nabla f(x_1) \| \leq L \|x_2 - x_1\|$$

   则称 $f$ 是 Lipschitz 连续的。

4. Lipschitz 连续的判定：以下性质等价

   • $f$ 是 Lipschitz 连续的，常数为 $L$
   • 对于任意 $x_1, x_2 \in C$，有 $[\nabla f(x_2) - \nabla f(x_1)]^T (x_2 - x_1) \leq L \|x_2 - x_1\|^2$
   • 对于任意 $x \in C$，有 $\nabla^2 f(x) \preceq L I$
   • 对于任意 $x_1, x_2 \in C$，有

     $$f(x_2) \leq f(x_1) + \nabla f(x_1)^T (x_2 - x_1) + \frac{L}{2} \|x_2 - x_1\|^2$$

5. 强凸与 Lipschitz 连续的关系：分别对凸函数 $f$ 的曲率变化的上下界进行了刻画，对于证明凸优化梯度下降算法的收敛性有重要的作用

# 保凸运算

1. 非负加权求和：$\sum_{i=1}^k w_i f_i(x)$，其中 $w_i \geq 0, i = 1, \ldots, k$

2. 与仿射变换的复合：$g(x) = f(Ax + b)$，其中 $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$

3. 逐点最大值 Pointwise maximum：$f(x) = \max\{f_1(x), f_2(x), \ldots, f_k(x)\}$

4. 逐点最大化 Pointwise supremum：$f(x) = \sup_{y \in A} f(x, y)$，其中 $A$ 是任意集合（若 $\forall y \in A$，$f(x, y)$ 关于 $x$ 是凸函数）

5. 复合函数：$f(x) = h(g(x))$

   • 若 $h$ 为凸函数且非减函数，$g$ 为凸函数，则 $f$ 为凸函数
   • 若 $h$ 为凸函数且非增函数，$g$ 为凹函数，则 $f$ 为凸函数
   • 若 $h$ 为凹函数且非减函数，$g$ 为凹函数，则 $f$ 为凹函数
   • 若 $h$ 为凹函数且非增函数，$g$ 为凸函数，则 $f$ 为凹函数

6. 向量形式的复合函数：$f(x) = h(g(x)) = h(g(x_1, x_2, \ldots, x_n))$

   • 若 $g_i$ 是凸函数，$h$ 是凸函数且对每个变量非减，则 $f$ 是凸函数
   • 若 $g_i$ 是凹函数，$h$ 是凸函数且对每个变量非增，则 $f$ 是凸函数

7. 最小化 Minimization：若 $f(x, y)$ 关于 $x$ 是凸函数，$C$ 是凸集，则 $g(x) = \inf_{y \in C} f(x, y)$ 关于 $x$ 是凸函数

8. 透射函数 perspective：$g(x, t) = t f(x/t)$，其中 $t > 0$，$f: \mathbb{R}^n \to \mathbb{R}$ 是凸函数，则 $g: \mathbb{R}^{n} \times \mathbb{R}_{++} \to \mathbb{R}$ 是凸函数

9. 凸共轭 Convex Conjugate：$f^*(y) = \sup_{x \in dom f} (y^T x - f(x))$，即使 $f$ 不是凸函数，$f^*$ 也是凸函数

# 拟凸

1. 下水平集 Sublevel Set：对于函数 $f: \mathbb{R}^n \to \mathbb{R}$ 和标量 $\alpha \in \mathbb{R}$，其下水平集定义为 $C_\alpha = \{x \in dom f | f(x) \leq \alpha\}$。

   • 凸函数的所有下水平集都是凸集（证明）
   • 反之不成立

2. 上境图 Epigraph：对于函数 $f: \mathbb{R}^n \to \mathbb{R}$，其上境图定义为 $epi f = \{(x, t) | x \in dom f, t \in \mathbb{R}, t \geq f(x)\}$。

   • 凸函数的上境图是凸集（证明）
   • 反之成立

3. 拟凸函数 Quasi-Convex Function：定义在凸集 $C$ 上的函数 $f: C \to \mathbb{R}$，如果对于任意 $\alpha \in \mathbb{R}$，其下水平集 $C_\alpha = \{x \in C | f(x) \leq \alpha\}$ 是凸集，则称 $f$ 是拟凸函数。

   • 等价定义：对于任意 $x_1, x_2 \in C$ 和 $\forall \lambda \in [0, 1]$，都有

     $$f(\lambda x_1 + (1 - \lambda) x_2) \leq \max\{f(x_1), f(x_2)\}$$

   • 凸函数必是拟凸函数，反之不成立
   • 若一个函数既是拟凸函数又是拟凹函数，则该函数是拟线性（quasi-linear）函数，某种意义上具备单调性

4. 例子

   • $\sqrt{|x|}$ 是拟凸函数
   • $ceil(x) = inf\{z \in \mathbb{Z} | z \geq x\}$ 是拟线性函数
   • $\log(x)$ 是拟线性函数
   • $f(x_1, x_2) = x_1x_2$ 在 $x_1, x_2 > 0$ 时是拟凹函数
   • 线性分数函数 $f(x) = \frac{a^T x + b}{c^T x + d}$，其中 $c^T x + d > 0$ 是拟线性函数
   • 距离比例函数 $f(x) = \frac{\|x - a\|_2}{\|x - b\|_2}$，其中 $\|x - a\|_2 \leq \|x - b\|_2$ 是拟凸函数
   • 拟凸函数求和不一定是拟凸函数

5. 拟凸函数的一阶条件：定义在凸集 $C$ 上的可微函数 $f: C \to \mathbb{R}$ 是拟凸函数的充分必要条件是对于任意 $x_1, x_2 \in C$，都有

   $$f(x_2) < f(x_1) \implies \nabla f(x_1)^T (x_2 - x_1) < 0$$

6. 拟凸函数的二阶条件：没有充要条件，但有

   • 必要条件：$\forall x \in C, y \in \mathbb{R}^n$，$y^T \nabla f(x) = 0 \implies y^T \nabla^2 f(x) y \geq 0$
     • 对于一维函数，退化为 $f'(x) = 0 \implies f''(x) \geq 0$
   • 充分条件：$\forall x \in C, y \in \mathbb{R}^n, y \neq 0$，$y^T \nabla f(x) = 0 \implies y^T \nabla^2 f(x) y > 0$

7. 拟凸函数的保凸运算

   • 与仿射变换复合
   • 最大值/上确界
   • 单调凸函数与凸函数的复合
   • 下确界
   • （正权重求和与透射变换不满足保凸性）

# 对数凸

1. 定义：定义在凸集 $C$ 上的函数 $f: C \to \mathbb{R}_{++}$，如果 $\log f$ 是凸函数，则称 $f$ 是对数凸函数。

   • 等价定义：对于任意 $x_1, x_2 \in C$ 和 $\forall \lambda \in [0, 1]$，都有

     $$f(\lambda x_1 + (1 - \lambda) x_2) \leq f(x_1)^\lambda f(x_2)^{1 - \lambda}$$

   • 对数凹函数：若 $\log f$ 是凹函数，则称 $f$ 是对数凹函数

2. 例子

   • $x^a, x > 0$，当 $a \leq 0$ 时是对数凸函数，当 $a \geq 0$ 时是对数凹函数
   • 高斯函数
   • 累计高斯函数

3. 对数凸函数的保凸运算

   • 对数凸函数的乘积是对数凸函数，但求和不一定是
   • $g(x) = \int_a^b f(x, t) dt$，其中 $f(x, t)$ 关于 $x$ 是对数凸函数，则 $g(x)$ 关于 $x$ 是对数凸函数
   • 对数凸函数的卷积是对数凸函数

# 广义不等式

1. 广义不等式 Generalized Inequality

   • 设 $\mathcal{K} \subseteq \mathbb{R}^n$ 是一个凸锥（cone），则可以以 $\mathcal{K}$ 给出对 $\mathbb{R}^n$ 的广义不等式：对于 $x, y \in \mathbb{R}^n$，

     $$x \preceq_{\mathcal{K}} y \iff y - x \in \mathcal{K}$$

     • 其中，$\preceq_{\mathcal{K}}$ 表示以锥 $\mathcal{K}$ 定义的广义不等式。例如：
       • 标准不等式 $x \leq y$ 可视为 $\mathbb{R}_+^n$ 锥的不等式。
       • 半正定矩阵锥 $S_+^n$ 对称矩阵的 Loewner 偏序：$X \preceq Y \iff Y - X \succeq 0$。
     • 若 $y - x \in \operatorname{int} \mathcal{K}$，则记 $x \prec_{\mathcal{K}} y$。

2. $\mathcal{K}$-凸函数（广义凸函数）

   • 设 $f: \mathbb{R}^n \to \mathbb{R}^m$，若定义域 $\operatorname{dom} f$ 是凸集，且对于任意 $x, y \in \operatorname{dom} f$ 及 $0 \leq \theta \leq 1$，

     $$f(\theta x + (1-\theta) y) \preceq_{\mathcal{K}} \theta f(x) + (1-\theta) f(y)$$

     即

     $$\theta f(x) + (1-\theta) f(y) - f(\theta x + (1-\theta) y) \in \mathcal{K}$$

     则称 $f$ 关于锥 $\mathcal{K}$ 是 $\mathcal{K}$-凸函数（或“广义凸函数”）。

   • 当 $\mathcal{K} = \mathbb{R}_+$ 时，上述退化为标量情况下的普通凸函数。

   • 当 $\mathcal{K} = S_+^m$ 时，则为“矩阵凸性”或“Loewner凸性”。

3. 例：$f : S^m \to S^m, \ f(X) = X^2$ 是 $S_+^m$-凸函数。

   • 证明：对任意 $z \in \mathbb{R}^m$，$z^T X^2 z = |Xz|^2$，该函数关于 $X$ 是凸的。即，对 $X,Y \in S^m$ 及 $0 \leq \theta \leq 1$，

     $$z^T\left(\theta X + (1-\theta) Y\right)^2 z \leq \theta z^T X^2 z + (1-\theta) z^T Y^2 z$$

     因为对所有 $z$ 均成立，故有

     $$\left(\theta X + (1-\theta) Y\right)^2 \preceq \theta X^2 + (1-\theta) Y^2$$

     即 $X^2$ 关于 $X$ 是 $S_+^m$-凸函数。

# 严格凸

1. 严格凸函数：定义在凸集 $C$ 上的函数 $f: C \to \mathbb{R}$，如果对于任意 $x_1, x_2 \in C$ 和 $\forall \lambda \in (0, 1)$，都有

   $$f(\lambda x_1 + (1 - \lambda) x_2) < \lambda f(x_1) + (1 - \lambda) f(x_2)$$

   则称 $f$ 是严格凸函数。

   • 严格凸函数的 Hessian 矩阵 $\nabla^2 f(x) \succ 0$ 是充分非必要条件
   • 严格凸函数的任意局部极小值都是其唯一的全局极小值（证明）

2. 严格凸函数的保凸运算

   • 若 $f_1, f_2$ 是严格凸函数，则 $f_1 + f_2$、$\max\{f_1, f_2\}$ 是严格凸函数
   • 若 $f, g$ 是严格凸函数，且 $g$ 递增，则 $g \circ f$ 是严格凸函数

3. 不同凸性的强度关系：强凸 $\implies$ 严格凸 $\implies$ 凸 $\implies$ 拟凸

# 不那么凸