跳转至

凸凹

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_i\)\(X^{-1/2}VX^{1/2}\)的特征值。

因为\(g\)\(t\)中是凹的,所以f是凹函数。

扩展值延申

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

$$\tlide{f} =

$\mathbb{R}上凸函数

凸函数:

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

凹函数:

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

\(^\star\)\(x > 0\)

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


最后更新: 2022-04-21 15:35:43
回到页面顶部