凸函数相关

1.3 凸函数

凸函数是

凸集

中元素的数学特征, 体现了凸集中元素所呈现的规律性. 它被定义为某个向量空间的凸子集 $C$ 上的实值函数 $f$. 若在其定义域 $C$ 上的任意两点 $x_1,x_2$, 及 $α in [0,1]$, 均有

$$

f(αx_1 +(1-α)x_2) \leq αf(x_1) + (1-α)f(x_2)

1.3.1 凸函数的判定

1. 设 $f_1,f_2,\cdots, f_k$ 是凸集 $S$ 上的凸函数，令 $phi(x)= displaystylesum_{i=1}^k λ_if_i(x)$，其中 $∀ λ_i geq 0 $，则 $\psi(x)=\displaystyle\max_{1\leq i \leq k} f_i(x)$ 与 $\phi(x)$ 都是 $S$ 上的凸函数。
2. 设在凸集 $D \subset \mathbb{R}^n $ 上 $f(x)$ 可微, 则 $f(x)$ 在 $D$ 上的为凸函数的充要条件是对于任意的 $x,y\in D $, 都有

f(y) \geq f(x) + \nabla f(x)^T(y-x)

1. 设在开凸集 $D \subset \mathbb{R}^n $ 上 $f(x)$ 二阶可微，则 $f(x)$ 在 $D$ 上的为凸函数的充要条件是对于任意的 $x\in D$，$f(x)$ 的 Hesse 矩阵半正定。

G(x) = ∇^2 f(x) = \begin{bmatrix}

\frac{∂^2f}{∂x_1^2} & \cdots & \frac{∂^2f}{∂x_1x_n}\\

\vdots & \ddots & \vdots\\

\frac{∂^2f}{∂x_nx_1} & \cdots & \frac{∂^2f}{∂x_n^2}

\end{bmatrix}

1.3.2 常用的凸函数

• 线性函数和仿射函数都是凸函数
• 最大值函数
• 幂函数: 当 $\alpha\in [0,1]$ 时, $x^{\alpha}$ 是一个凸函数; 绝对值幂函数也是凸函数。
• 对数函数 $\log(x)$ 在 $\mathbb{R}_{++}$ 上是凸函数
• $f(x) = \log(\displaystyle\sum_{i=1}^n \exp(x_i))$ 是 $\mathbb{R}^n$ 上的凸函数
• 几何平均: $ f(x) = (displaystyle∏_{i=1}^n x_i)^{frac{1}{n}} $ 是定义在 $\mathbb{R}_{++}^n$ 上的凸函数
• 范数

1.3.3 凸函数的性质

• 任一局部极小 (大) 点也是全局极小 (大) 点，且全局极小 (大) 点的集合为凸集。
• 任一局部最优解都是它的整体最优解。

在最优化理论中，局部最优解被称为满意解，全局最优解被称为最优解。大多数传统的最优化理论和算法都只能保证找到满意解，因而人们尽可能的使用凸函数作为优化问题的目标函数。对于那些无法转换为凸函数的优化问题，只有通过穷举法来计算函数的所有值 (如果可能) 来找到全局最优解。当然针对一些特定的问题可以通过，诸如模拟退火法、隐马尔科夫链算法等随机优化方法来寻找最优解。但这不是我们讨论的要点，我们主要列举一些我认为比较重要的凸函数的相关知识点。