跳转至

凸凹

ok,在了解了基础知识之后,让我们开始入门:凸函数与凹函数

凸函数与凹函数#

凸函数

函数f: \mathbb{R}^n \rightarrow \mathbb{R}是一个凸函数,如果他的取值范围\mathrm{dom} f是一个凸集,并且

f(\sum_{i=1}^n \theta_i x_i) \leq \sum_{i=1}^n f(\theta_i x_i)

对于所有x_i \in \mathrm{dom} f, \ \sum_{i=1}^n \theta_i = 1, \ \forall \theta_i, 0 \leq \theta_i \leq 1都成立

我们可以注意到,\sum_{i=1}^n \theta_i x_i其实是一个凸组合。

凸函数的几何意义

对于凸函数上任意两点x,\ y,该两点之间的连线不低于该凸函数。

所有的范数都是凸函数吗

是的

严格凸函数

函数f: \mathbb{R}^n \rightarrow \mathbb{R}是一个严格凸函数,如果他的取值范围\mathrm{dom} f是一个凸集,并且

f(\sum_{i=1}^n \theta_i x_i) \lt \sum_{i=1}^n f(\theta_i x_i)

凹函数

如果函数f是个凸函数,那么函数-f是凹函数。

如果函数f是严格凸函数,那么函数-f是严格凹函数。

凸函数的判定#

Restriction of a Convex Function to a Line

对于函数f: \mathbb{R}^n \rightarrow \mathbb{R},若该函数在每一个方向上g(t) = f(x + tv): \mathbb{R} \rightarrow \mathbb{R}都是凸的,则该函数是凸的。

这个方式通过将判定一个定义域为\mathbb{R}^n的函数的凸性的问题转换为n个定义域为\mathbb{R}的问题来降低计算量,但其不适用于多变量函数。

f(X) = \log \det x
\begin{align} g(t) &= \log \det (X = tV)\\ &= \log \det X + \log \det (I + tX^{-1/2}VX^{1/2})\\ &= \log \det X + \sum^n{i=1} \log (1 + t\lambda_i)\\ \end{align}

其中\lambda_iX^{-1/2}VX^{1/2}的特征值。

因为gt中是凹的,所以f是凹函数。

扩展值延申

函数f: \mathbb{R}^n \rightarrow \mathbb{R}的扩展值延申\tlide{f}被如下定义:

$$\tlide{f} =

$\mathbb{R}上凸函数

凸函数:

  • 仿射:ax + b
  • ^\starx^a, \ s.t. \ a \geq 1 \text{or} a \leq 0
  • 指数:e^{ax}
  • 负熵^\starx \log x

凹函数:

  • 仿射:ax + b
  • ^\starx^a, \ s.t. \ 0 \leq a \leq 1
  • 对数^\star\log x

^\starx > 0

我们可以注意到,所有的仿射函数是既凸又凹的。


最后更新: 2021-05-06 19:36:11

评论