Convex functions

说完了凸集，下一个要将的肯定就是凸函数啦~

凸函数的相关性质在优化中的地位不言而喻~！

凸函数

$f: \mathrm{R}^n \to \mathrm{R}$ 是凸函数，如果 $f$ 的定义域是凸集，并且 $\forall x, y, \theta \in [0, 1]$ 成立： $f(\theta x+(1-\theta )y) \leq \theta f(x) + (1-\theta) f(y)$

如果 $\theta \in (0, 1), x\neq y$ 时上面的不等号严格成立，那么就说这个函数是严格凸的。

几何上看，凸函数要求 $(x, f(x))$ 和 $(y, f(y))$ 这条线段位于函数图形的上方。

对应的，我们还有定义“凹函数”，当 $-f$ 是凸函数时， $f$ 被称为凹函数。

对于仿射函数，它是既凸又凹的。同时，既凸又凹的函数只有仿射函数。

如果 $f$ 是凸函数，那么 $g(t)=f(x+tv)$ 也是凸函数，反过来的结论也成立。这说明，凸函数限制在任何一条直线上都是凸！凸函数的概念完全可以从欧式空间推广到一般的线性空间，在一般的线性空间上，这条性质成为我们判断凸函数的重要依据。

凸函数还具有良好的分析性质，比如，凸函数在它定义域的相对内点集上是连续的；凸函数的不连续点只可能出现在它的相对边界上。

凸函数定义域延拓

有时候我们会把一个凸函数的定义域延拓到整个 $R^n$ 空间中：
$\tilde{f}(x)=\left\{\begin{array}{ll}f(x) & x \in \operatorname{dom} f \\ \infty & x \notin \operatorname{dom} f\end{array}\right.$

可以证明，这样延拓的凸函数也满足凸函数的定义。（在定义好关于 $\infty$ 的运算后）。这样的定义在函数表示上有一定的意义。

一阶条件（first order condition）

可微的凸函数满足一阶条件：
$f(y) \geq f(x)+\nabla f(x)^{T}(y-x)\quad\forall x,y \in \mathrm{dom}f$

这个不等式揭示了凸函数的局部特性，那就是在一点的切平面是整个函数的 global underestimate 。

如果上面的不等号严格成立，那么这个函数是严格凸的。这里的条件是充分必要的。

二阶条件（second order condition）

如果定义在开凸集上的二阶可微函数 $f$ 满足 $\nabla^2f\succeq0$ ，那么 $f$ 是凸函数。

如果 $\nabla^2f\succ0$ ，那么 $f$ 是严格凸的。

当 $f$ 严格凸时，不一定能推出 $\nabla^2f$ 正定。比如 $f(x)=x^4$ ，二阶导数在 $x=0$ 处为 $0$ 。

关于一阶条件和二阶条件的证明，要用到泰勒展开。在此从略。

凸函数的例子

指数函数、多项式函数，绝对值函数都是凸的；对数函数是凹的。
最大值函数是凸的。

对 $f(x)=\log \left(e^{x_{1}}+\cdots+e^{x_{n}}\right)$ is convex on $\mathbf{R}^{n}$ 。有估计式： $\max \left\{x_{1}, \ldots, x_{n}\right\} \leq f(x) \leq \max \left\{x_{1}, \ldots, x_{n}\right\}+\log n$ 这个函数是最大值函数的一个光滑近似。

$f(x)=(\Pi_{i=1}^n x_i)^{\frac{1}{n}},x_i>0$ 是凹函数，容易证明 $\nabla^2f$ 是半负定的。
$f(X)=\log \det X$ 是 $\mathrm{S}_{++}^n$ 上的凹函数。它是一个定义在矩阵空间上的函数。（关于它的证明，参见我的另一篇文章）

下水平集（sublevel sets）

定义 $f: \mathbf{R}^n \to \mathbf{R}$ 的 $\alpha-sublevel\;\; set$ 为：
$C_{\alpha}=\{x \in \operatorname{dom} f \mid f(x) \leq \alpha\}$ 易证 $f$ 是凸函数的时候 $C_\alpha$ 是个凸集。

从而这里给出了判断凸集的另一个方法：能被写成某个凸函数的 $\alpha$ -sublevel set 的集合是凸集。反之，一个函数的 sublevel set 是凸的，并不能反推出它是凸函数（事实上这个函数是拟凸的）。

例： $S=\{x|x^T Ax+c^T x+ b \leq 0, A\succeq 0\}$ 是凸集。

对于 $f$ 是凹函数有相应的结论： $\{x \in \operatorname{dom} f | f(x) \geq \alpha\}$ 是凸集。

Epigraph

一个函数的 $f:\mathbf{R}^n\to \mathbf{R}$ 的 epigraph 是指：
$\text { epi } f=\{(x, t) | x \in \operatorname{dom} f, f(x) \leq t\}$

$\text{epi} f$ 是 $\mathbf{R} ^{n+1}$ 的子集，是函数图形的上方。 $\text{epi} f$ 是凸集当且仅当 $f$ 是凸函数。所以epigraph 也是一种主要的判断凸函数的方法。

对应于凹函数我们定义 hypograph：
$\text { hypo } f=\{(x, t) \mid t \leq f(x)\}$ $\text{hypo} \;f$ 是凸集当且仅当 $f$ 是凹函数。

例： $f(X)=\lambda_{\max} (X), X \in \mathrm{S}_n$ 的 epigraph $\{(X, t)\mid tI - X \succeq 0\}$ 是凸集，从而 $f$ 是凸函数。类似可得 $f(X)=\lambda_{\min} (X), X \in \mathrm{S}_n$ 是凹函数。

琴生不等式（Jesen inequality）

琴生不等式是凸函数的重要性质。

对 $x_{1}, \ldots, x_{k} \in \operatorname{dom} f$ 和 $\theta_{1}, \ldots, \theta_{k} \geq 0, \theta_{1}+\cdots+\theta_{k}=1$ 成立：

$f\left(\theta_{1} x_{1}+\cdots+\theta_{k} x_{k}\right) \leq \theta_{1} f\left(x_{1}\right)+\cdots+\theta_{k} f\left(x_{k}\right)$

这是有限个点的情况。该不等式还能扩展到无限和、积分等情况。

If $p(x) \geq 0$ on $S \subseteq \operatorname{dom} f, \int_{S} p(x) \mathrm{d} x=1$ , then:
$f \left( \int _ { S } p ( x ) x \mathrm{d} x \right) \leq \int _ { S } f ( x ) p ( x ) \mathrm{d} x$

对某些凸函数应用琴生不等式可以得到许多著名的不等式：

比如Holder 不等式：
$\sum_{i=1}^{n} x_{i} y_{i} \leq\left(\sum_{i=1}^{n}\left|x_{i}\right|^{p}\right)^{1 / p}\left(\sum_{i=1}^{n}\left|y_{i}\right|^{q}\right)^{1 / q}$

保持函数凸性的操作

若干凸函数非负的加权和
在 infinite 的情况下， $f(x,y)$ 对 $x$ 是凸的，并且 $w(y)>0$ ，那么 $g(x)=\int f(x,y)w(y) \mathrm{d}y$ 是凸的。
与仿射函数的复合

凸函数的最大值（上确界）函数

在 infinite 的情况下， $f(x,y)$ 对 $x$ 是凸的，那么 $g(x) = \sup_y f(x,y)$ 也是凸的。

$\operatorname{epi} g=\bigcap_{y \in \mathcal{A}} \operatorname{epi} f(\cdot, y)$ ，凸集的交仍然是凸的，因此 $\operatorname{epi} g$ 也是凸的。

事实上，绝大多数的凸函数，都能够表示成一族仿射函数的上确界函数，这种方法也是判断凸函数最常用的方法。

一般的函数复合的情况

函数的透视

透视操作是保持凸（凹）性的。

特殊情况下的下确界函数

如果 $f(x,y)$ 对 $(x,y)$ 是凸的， $C$ 是一个非空凸集，那么 $g(x)=\inf_{y \in C} \;f(x, y)$ 是凸的。

$\begin{aligned} g\left(\theta x_{1}+(1-\theta) x_{2}\right) &=\inf _{y \in C} f\left(\theta x_{1}+(1-\theta) x_{2}, y\right) \\ & \leq f\left(\theta x_{1}+(1-\theta) x_{2}, \theta y_{1}+(1-\theta) y_{2}\right) \\ & \leq \theta f\left(x_{1}, y_{1}\right)+(1-\theta) f\left(x_{2}, y_{2}\right) \\ & \leq \theta g\left(x_{1}\right)+(1-\theta) g\left(x_{2}\right)+\epsilon \end{aligned}$

另外，也可以通过 $\mathrm{epi }\;g$ 来证明凸性。

共轭函数（Conjugate Function）

定义函数 $f(x)$ 的共轭函数为： $f^{*}(y)=\sup _{x \in \operatorname{dom} f}\left(y^{T} x-f(x)\right)$ 共轭函数是多个仿射函数的上确界，因此是一定是凸函数。共轭函数的定义域是上确界值有限的 $y$ 的值。

一些例子：

$f(x)=ax+b$ ，注意到 $xy-ax-b$ 只在 $y=a$ 时有界，因此共轭函数只在 $y=a$ 处有定义，并且 $f^*(y)=-b$
$f(x)=x^2$ ， $\sup_{x\in R} xy - x^2 = \frac{y^2}{4}=f^*(y)$
$f(x)=\frac{1}{2}x^T Qx,(Q\in \mathrm{S}^n_{++})$ 的共轭函数是 $f^*(y)=\frac{1}{2}y^T Q^{-1}y$
$f(x)=|x|$ 的共轭函数是 $f^{\star}(y)=\left\{\begin{array}{ll}0 & \text { if }|y| \leq 1 \\ \infty & \text { if }|y|>1\end{array}\right.$

共轭函数具有鲜明的几何意义：

当 $f(x)$ 是一元函数的时候，如上图所示， $f^*(y)$ 表示以 $y$ 为斜率且过原点的直线，与 $f(x)$ 的图像的最大距离（或者其负数）。

当 $f(x)$ 是 $n$ 元函数的时候， $f^*(y)$ 表示以 $(-y, 1)$ 为法向量（n+1维）且过原点的平面，与 $f(x)$ 的图像的最大距离（或者其负数）。

非空集合 $X$ 的示性函数（indicator function ） $\delta_X(x)$ 定义为： $\delta_{X}(x)=\left\{\begin{aligned} 0, &\; x \in X \\ \infty, &\; x \notin X \end{aligned}\right.$ $\delta_X(x)$ 的共轭函数是支撑函数 $\sigma_X(x)$ ： $\sigma_{X}(y)=\sup _{x \in X} y^{\prime} x$

设 $f(x)=\|x\|$ 代表 $\mathbf{R}^n$ 中的一种范数，其对偶范数为 $\|\cdot \|_*$ ，我们能得到共轭函数： $f^{*}(y)=\left\{\begin{array}{ll}0 & \|y\|_{*} \leq 1 \\ \infty & \text { otherwise }\end{array}\right.$

Fenchel’s inequality

根据共轭函数的定义，下式是显然的：
$f(x)+f^*(y)\ge x^T y$ 应用到上面的例子，还能得到： $x^{T} y \leq(1 / 2) x^{T} Q x+(1 / 2) y^{T} Q^{-1} y$

共轭函数的共轭

如果 $f$ 是凸函数，并且 $\mathbf{epi} f$ 是闭集，那么 $f^{**}=f$ 。

可微分函数的共轭

如果 $f$ 是凸函数并且一阶可微，那么根据凸函数的极值理论，容易得到，使得 $y^T x-f(x)$ 最大的 $x^*$ 满足： $y=\nabla f(x^*)$

从而我们有：
$f^{*}(y)=x^{* T} \nabla f\left(x^{*}\right)-f\left(x^{*}\right),\quad(y=\nabla f(x^*))$

欲求 $f^*(y)$ ，只需要解 $y=\nabla f(z)$ 得到向量 $z$

可微函数 $f$ 的共轭，也叫做 $f$ 的 Legendre变换。

其他性质

Scaling and composition with aﬃne transformation

如果 $f(u, v)=f_{1}(u)+f_{2}(v)$ ，且 $f_1, f_2$ 都是凸函数，那么：
$f^{*}(w, z)=f_{1}^{*}(w)+f_{2}^{*}(z)$

拟凸函数（Quasiconvex functions）

拟凸函数就是所有下水平集是凸集的函数。比如 $f(x)=\sqrt{|x|}$ 就不是凸函数，但是是拟凸的。

$R$ 上的拟凸函数，要么是单调的，要么在一个点左边单调递减，右边单调递增。

很多凸函数具有的良好性质，可以推广到拟凸函数上。

一个定义在凸集上的函数是拟凸函数，当且仅当 $\forall x, y \in \mathrm{dom} f$ , $0\le \theta \le 1$ ，成立：
$f(\theta x+(1-\theta) y) \leq \max \{f(x), f(y)\}$

这意味着，线段上的函数值，一定小于等于两个端点函数值最大的那一个。这个既可以当做拟凸函数的性质，也能当做拟凸函数的定义。（关于两种定义等价性的证明，看这里）

针对这个性质还有另一个版本：
$f(x)\le f(y) \Rightarrow f(\theta x+(1-\theta)y)\le f(y)$

一些资料上把这个当做拟凸函数的定义，并且当不等号严格成立时，称 $f$ 是严格拟凸的。

来看一些例子。

$f(x_1, x_2)=x_1x_2, (x_1, x_2 > 0)$ ，容易看到 $\nabla^2 f$ 是不定的，因此既不是凸函数也不是凹函数。但是 $\{x|x_1x_2\ge\alpha\}$ 是凸集，所以 $f$ 是拟凹函数。
线性分式函数是拟线性的。

因为 $\operatorname{rank}(X+Y) \geq \min \{\operatorname{rank} X, \operatorname{rank} Y\}$ 所以 $f(X)=\operatorname{rank}(X)$ 是 $S_+^n$ 上的拟凹函数

可微分的拟凸函数

类似于凸函数，当函数可微时，可以推导出拟凸函数需要满足的一阶条件和二阶条件。

一阶条件

该条件也有鲜明的几何意义。 $\nabla f(x)$ 导出了过点 $x$ 的对下水平集 $\{y|f(y)\le f(x)\}$ 的支撑超平面。（高维情况很难想象，不妨考虑一维情况，这时候支撑超平面就退化为一个点，下水平集是一个区间）

注意到 $\nabla f(x_0)^T(y-x_0)=0$ 对于给定的 $x_0$ ，表示的是一个平面。

虽然拟凸函数和凸函数在一阶条件上具有相似性，但是拟凸函数并不能用一阶条件来判断全局的最小值。当 $\nabla f(x)=0$ 时， $x$ 不一定是 global minimizer.

二阶条件

这个条件，意味着 $\nabla^2f$ 在 $\nabla f^{\perp}$ 是半正定的，同时 $\nabla^2f$ 至多有一个负特征值。（ $\mathrm{span}\{\nabla f\}$ 是一维的，从而 $\nabla f^{\perp}$ 是 $n-1$ 维的）

如果 $\nabla^2f$ 在 $\nabla f^{\perp}$ 是正定的，那么才能说明 $f$ 是拟凸的。

保持拟凸性的操作

拟凸函数非负加权和的最大值
这里就用之前提到过的第二种定义方式进行证明即可。同样可以推广到逐点上确界的情况。

$\lambda_{\max }(X, Y)=\sup _{u \neq 0} \frac{u^{T} X u}{u^{T} Y u}=\sup \{\lambda | \operatorname{det}(\lambda Y-X)=0\}$ ，其中 $X\in S^n, Y\in S^n_{++}$ ， $\lambda_{\max}$ 是拟凸的，叫做 $(X,Y)$ 的广义特征值。

函数复合

对数凹/对数凸函数

简单讲， $f>0$ ，并且 $\log f$ 是凹函数，那么 $f$ 就称为对数凹的。

对数凹还可以用 $f(\theta x+(1-\theta) y) \geq f(x)^{\theta} f(y)^{1-\theta}, \forall \theta \in [0, 1]$ 来定义。从这里看，凸函数可以视作一种“算术平均”，对数凸则是“几何平均”。

为什么要研究对数凸/凹函数呢？
统计学中的似然函数，是一个经常要取对数的函数，欲求参数的极大似然估计值，其实就是一个关于似然函数的优化问题，如果似然函数是对数凹的，那么求对数似然函数负值的最小值，就是一个凸优化问题！这是研究对数凹函数的目的所在。

标准正态分布的累计分布函数 $\Phi(x)$ 是对数凹的。
$\det X$ 在 $S^n_{++}$ 上是对数凹的。
多元正态概率密度函数是 $f(x)=\frac{1}{\sqrt{(2 \pi)^{n} \operatorname{det} \Sigma}} e^{-\frac{1}{2}(x-\bar{x})^{T} \Sigma^{-1}(x-\bar{x})}$ 是对数凹的。

事实上，很多常见的概率分布函数，都是对数凹的。

如果 $f$ 具有良好的光滑性，通过 $\log f$ 的凹凸性，我们可以得到一些关于 $f$ 的性质：
因为： $\nabla^{2} \log f(x)=\frac{1}{f(x)} \nabla^{2} f(x)-\frac{1}{f(x)^{2}} \nabla f(x) \nabla f(x)^{T}$
于是可以得到 $f$ 对数凹的一个充要条件： $f(x) \nabla^{2} f(x) \preceq \nabla f(x) \nabla f(x)^{T}$

在一元函数的情况，就是： $f\cdot f^{''}\leq(f^{'})^2$ 。

此外，对数凸/凹性是对乘法保持封闭的。从 $h(x)=f(x)g(x)\Rightarrow \log h(x) = \log f(x) + \log g(x)$ 容易看出。如果概率密度函数是对数凹的，那么多个密度函数相乘的结果也是对数凹的。

广义不等式下的凸性

通过前面提到的广义不等式，可以定义函数的“单调递增”和“严格单调递增”。

想想为什么 $K-\mathit{increasing}$ 的定义不使用 $x\prec_K y$

例子：

$f(X)=\mathrm{det} X$ 是 $S^n_{+}$ 上的 increasing 函数。

如果 $X$ 是半正定矩阵，那么 $|X+I|>|X|$ 。（借助特征值证明）

$f(X)=\mathrm{tr} X^{-1}$ 是 $S^n_{++}$ 上的 decreasing 函数。

单调性的梯度条件

对于这种新的单调性，我们可以用广义不等式下的梯度条件去判断。

$f$ is K-nondecreasing $\Leftrightarrow$ $\nabla f(x) \succeq_{K^{*}} 0 \quad\forall x \in \mathrm{dom} f$
$f$ is K-increasing $\Leftrightarrow$ $\nabla f(x) \succ_{K^{*}} 0\quad\forall x \in \mathrm{dom} f$

函数的梯度在对偶不等式的情况下是非负的。其实 $\nabla f(x) \succeq_{K^{*}} 0$ 这里暗指的，就是 $f$ 在 $K$ 中的每一个方向都是单调递增的。

广义不等式下的凸性

进一步，通过广义不等式还能把函数的凸性定义在一个 proper cone 上：

值得注意的是，通常我们说的凸函数，值域是 $R$ ，而K-convex 的定义上，凸函数的值域被推广到了 $R^m$ 。

凸函数的大多数性质，可以推广到K-convex 函数上。

因为值域是 $R^m$ ，一阶条件的梯度变成了 Jacobi 矩阵。

最后编辑于：2021.04.18 16:41:59

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 199,711评论 5赞 468
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 83,932评论 2赞 376
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 146,770评论 0赞 330
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 53,799评论 1赞 271
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 62,697评论 5赞 359
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,069评论 1赞 276
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,535评论 3赞 390
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,200评论 0赞 254
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,353评论 1赞 294
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,290评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,331评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,020评论 3赞 315
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,610评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,694评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,927评论 1赞 255
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,330评论 2赞 346
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 41,904评论 2赞 341

Convex functions

凸函数

凸函数定义域延拓

一阶条件（first order condition）

二阶条件（second order condition）

凸函数的例子

下水平集（sublevel sets）

Epigraph

琴生不等式（Jesen inequality）

保持函数凸性的操作

共轭函数（Conjugate Function）

Fenchel’s inequality

共轭函数的共轭

可微分函数的共轭

其他性质

拟凸函数（Quasiconvex functions）

可微分的拟凸函数

一阶条件

二阶条件

保持拟凸性的操作

对数凹/对数凸函数

广义不等式下的凸性

单调性的梯度条件

广义不等式下的凸性

推荐阅读更多精彩内容