基本性质

定义

如果 $\mathrm{dom}f$ 是凸集，且对于任意的 $x,y\in \mathrm{dom}f$ 和任意的 $0⩽\theta ⩽1$，若有

$$f(\theta x+(1-\theta )y)⩽\theta f(x)+(1-\theta )f(y)$$

则称函数 $f:{\mathbf{R}}^n\to \mathbf{R}$ 是凸的。

例子

• 仿射函数：$a^{\mathrm{\top }}x+b$ 既是凸的也是凹的。
• 二次函数：$f(x)=\frac{1}{2}{x}^{\mathrm{\top }}Px+q^{\mathrm{\top }}x+r$，当 $P⪰0$ 时是凸的。
• 最小二乘目标：$f(x)=\parallel Ax-b{\parallel }_2^2$（即 $x^{\mathrm{\top }}{A}^{\mathrm{\top }}Ax-2b^{\mathrm{\top }}Ax+b^{\mathrm{\top }}b$）是凸的。
• 对数障碍（log-barrier）：$f(x)=-\sum _{i=1}^m\log (b_i-a_i^{\mathrm{\top }}x)$，定义域为 $\{x\mid a_i^{\mathrm{\top }}x<b_i\}$，是凸的。
• 分段线性函数：$f(x)=max\{0,x\}$ 或一般的 $f(x)=max\{a_1^{\mathrm{\top }}x+b_1,\cdots ,a_L^{\mathrm{\top }}x+b_L\}$ 是凸的。

从几何意义上看，上述不等式意味着点 $(x,f(x))$ 和点 $(y,f(y))$ 之间的线段，即从 $x$ 到 $y$ 的弦，在函数 $f$ 图像的上方。如果不等式中当 $x\ne y$ 时 $0⩽\theta ⩽1$ 严格成立，则称函数 $f$ 是严格凸的。

扩展值延伸

通常可以定义凸函数的定义域外的值为 $\mathrm{\infty }$，从而将这个凸函数延伸至全空间 ${\mathbf{R}}^n$。我们定义凸函数 $f$ 的扩展值延伸：$\tilde{f}:{\mathbf{R}}^n\to \mathbf{R}\cup \{\mathrm{\infty }\}$ 如下：

$$\tilde{f}(x)=\{\begin{array}{ll}f(x)& x\in \mathrm{dom}f\\ \mathrm{\infty }& x\notin \mathrm{dom}f\end{array}$$

一阶条件

假设 $f$ 可微（即其梯度 $\mathrm{\nabla }f$ 在开集 $\mathrm{dom}f$ 内处处存在），则函数 $f$ 是凸函数的充要条件是 $\mathrm{dom}f$ 是凸集，且对于任意的 $x,y\in \mathrm{dom}f$，有

$$f(y)⩾f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}(y-x)$$

由此得出的仿射函数 $y$ 即为函数 $f$ 在点 $x$ 附近的 Taylor 近似。上面的不等式表明，对于一个凸函数，其一阶 Taylor 近似实质上是原函数的一个全局下估计。反之，如果某个函数的一阶 Taylor 近似总是其全局下估计，那么这个函数是凸的。

同理，可以定义凹函数及其一阶条件。

二阶条件

现在假设函数 $f$ 二阶可微（即对于开集 $\mathrm{dom}f$ 内的任意一点，它的 Hessian 矩阵或者二阶导数 ${\mathrm{\nabla }}^{2}f$ 存在），则函数 $f$ 是凸函数的充要条件是，其 Hessian 矩阵是半正定矩阵，即对所有的 $x\in \mathrm{dom}f$，有

$${\mathrm{\nabla }}^{2}f(x)⪰0$$

下水平集

函数 $f:{\mathbf{R}}^n\to \mathbf{R}$ 的 α-下水平集定义为

$$C_{\alpha }=\{x\in \mathrm{dom}f\mid f(x)⩽\alpha \}$$

若 $f$ 是凸函数，则其任意 $\alpha$-下水平集都是凸集：若 $f(x_1)⩽\alpha$、$f(x_2)⩽\alpha$，则 $f(\theta x_1+(1-\theta )x_2)⩽\theta f(x_1)+(1-\theta )f(x_2)⩽\alpha$。

反之不成立：下水平集全凸的函数只是拟凸函数（见下文），不一定凸。例如 $f(x)=x^3$ 不是凸函数，但它的所有下水平集 $(-\mathrm{\infty },{\alpha }^{1/3}]$ 都是凸集。

上境图

函数 $f:{\mathbf{R}}^n\to \mathbf{R}$ 的图像定义为

$$\{(x,f(x))\mid x\in \mathrm{dom}f\}$$

它是 ${\mathbf{R}}^{n+1}$ 空间的一个子集。

函数 $f:{\mathbf{R}}^n\to \mathbf{R}$ 的上镜图定义为

$$\mathrm{epi}f=\{(x,t)\mid x\in \mathrm{dom}f,f(x)⩽t\}$$

上镜图的概念很像是下水平集和函数图像二者的结合。从几何上看，上镜图即为在函数图像之上。

定义在 ${\mathbf{R}}^n$ 上的凸函数 $f$ 的上镜图是 ${\mathbf{R}}^{n+1}$ 空间的一个凸集，其支撑超平面和一阶条件有着如下图所示的联系：

TikZ 代码

\begin{tikzpicture}[line cap=round,line join=round,scale=1.0]
  % epigraph of a convex function and its supporting hyperplane
  \fill[gray!20] plot[domain=-2.4:3.2] (\x, {0.4*(\x-1)^2 + 0.3})
    -- (3.2,4.6) -- (-2.4,4.6) -- cycle;
  \draw plot[domain=-2.4:3.2] (\x, {0.4*(\x-1)^2 + 0.3});
  \node at (0,3.4) {$\mathrm{epi}\, f$};
  \draw (-0.7,-0.64) -- (3.3,1.28);
  \fill (1.6,0.436) circle (1.4pt) node[right] {$(x, f(x))$};
  \draw[->,thick] (1.6,0.436) -- (2.26,-0.38) node[right] {$(\nabla f(x), -1)$};
\end{tikzpicture}

从图中可以直观地看到，凸函数 $f$ 在点 $x$ 处的一阶 Taylor 近似即为其上镜图在 $x$ 处的支撑超平面。

Jensen 不等式及其扩展

基本不等式

$$f(\theta x+(1-\theta )y)⩽\theta f(x)+(1-\theta )f(y)$$

有时也称作 Jensen 不等式。此不等式可以很方便地扩展至更多点的凸组合：如果函数 $f$ 是凸函数，$x_1,\cdots ,x_k\in \mathrm{dom}f$，${\theta }_1,\cdots ,{\theta }_k⩾0$ 且 ${\theta }_1+\cdots +{\theta }_k=1$，则下式成立

$$f({\theta }_1{x}_1+\cdots +{\theta }_k{x}_k)⩽{\theta }_{1}f(x_1)+\cdots +{\theta }_{k}f(x_k)$$

考虑凸集时，此不等式还可以扩展至无穷项和、积分以及期望。

例如，若在 $S\subseteq \mathrm{dom}f$ 上 $p(x)⩾0$ 且 ${\int }_{S}p(x)\mathrm{d}x=1$，则

$$f({\int }_{S}p(x)x\mathrm{d}x)⩽{\int }_{S}f(x)p(x)\mathrm{d}x$$

再比如，设 $x$ 是随机变量，若函数 $f$ 是凸函数，则

$$f(\mathbf{E}x)⩽\mathbf{E}f(x)$$

INFO

我们不妨来回忆以下高中时期我们接触到的凸函数定义，如下

$$f\left({\displaystyle \frac{x+y}{2}}\right)⩽{\displaystyle \frac{f(x)+f(y)}{2}}$$

其实这就是由 Jensen 提出的最初的一个最简单的不等式。现在，我们可以称上述所有的不等式为 Jensen 不等式。