一、定义和基本性质
1.1 定义
一个函数 $f:\mathbf{R}^n\rightarrow \mathbf{R}$ 是凸函数当且仅当 $\mathrm{dom};f$ 是凸集，且对于所有的 $x,y\in\mathrm{dom};f$ 和 $0\le\theta\le 1$，满足
$$
f\left(\theta x+(1-\theta)y\right) \leq \theta f\left(x\right)+(1-\theta) f\left(y\right)
$$
- 若 $x\ne y$ 且 $0<\theta<1$ 时上述不等式严格成立，则称函数 $f$ 严格凸。若 $f$ 为凸函数，则 $-f$ 为凹函数；若 $f$ 为严格凸函数，则 $-f$ 为严格凹函数。
- 仿射函数总是满足上述不等式，且所有的仿射函数都是既凸又凹的；所有既凸又凹的函数都是仿射函数；而凸函数不一定是仿射函数。
1.2 一阶条件
可微
若梯度
$$
\nabla f(x)=\left(\frac{\partial f(x)}{\partial x_{1}}, \frac{\partial f(x)}{\partial x_{2}}, \ldots, \frac{\partial f(x)}{\partial x_{n}}\right)
$$
在 $\mathrm{dom};f$ （开集）的每个点 $x$ 上都存在，则称 $f$ 可微。first-order conditions
假设 $f$ 可微，则 $f$ 为凸函数当且仅当 $\mathrm{dom};f$ 为凸，且对于所有的 $x,y\in\mathrm{dom};f$，满足
$$
f(y)\ge f(x)+\nabla f(x)^T(y-x)
$$
若对于所有的 $x,y\in\mathrm{dom};f$，满足
$$
f(y)> f(x)+\nabla f(x)^T(y-x)
$$
则称 $f$ 为严格凸。对于凹函数，则是： $f$ 为凹函数当且仅当 $\mathrm{dom};f$ 为凸，且对于所有的 $x,y\in\mathrm{dom};f$，满足
$$
f(y)\le f(x)+\nabla f(x)^T(y-x)
$$
1.3 二阶条件
二次可微
若 Hessian 矩阵或二阶导
$$
\nabla^{2} f(x){i j}=\frac{\partial^{2} f(x)}{\partial x{i} \partial x_{j}}, \quad i, j=1, \ldots, n
$$
在 $\mathrm{dom};f$ （开集）的每个点 $x$ 上都存在，则称 $f$ 二次可微。second-order conditions
假设 $f$ 二次可微，则 $f$ 为凸函数当且仅当 $\mathrm{dom};f$ 为凸，且对于所有的 $x\in\mathrm{dom};f$，满足
$$
\nabla^2 f(x)\ge0
$$
若对于所有的 $x\in\mathrm{dom};f$，满足
$$
\nabla^2 f(x)>0
$$
则称 $f$ 为严格凸。但反过来不成立，如函数 $f(x)=x^4$ 为严格凸的，但其二阶导在 $x=0$ 时为 0。其实二阶性质和一阶性质的本质是一样的。二阶相当于一阶性质不等式的泰勒展开式右边增加了一个二次项（都省去了余项-高阶无穷小）。二次项相当于 $(y-x)^T\nabla^2f(x) (y-x)\ge0$ ，即海森矩阵需满足半正定。
1.4 函数的凸性判别
- 基本定义（将其限制在一条直线上）
- 二阶导大于或等于海森矩阵半正定
- 证明函数是由一些简单的凸函数经过保凸运算得到
1.5 凸/凹函数实例
凸（convex）
仿射函数（线性函数）。$ax+b$
指数函数。$e^{ax},a\in\mathbf{R}$
幂函数。$x^{a},a>1; \mathrm{or};a<0$
绝对值的幂函数。$|x|^p,p\ge 1$
负熵。$x\log(x)$
其它例子：
范数（Norms）
max function。$f(x)=\max{x_1,x_2,\cdots,x_n}$
二次超线性函数。如 $f(x,y)=x^2/y$ ，其定义域为
$$
\mathrm{dom};f=\mathbf{R}\times\mathbf{R}_{++}={(x,y)\in\mathbf{R}^2|y<0}
$$log-sum-exp。$f(x)=\log(e^{x_1}+e^{x_2}+\cdots,+e^{x_n})$
几何平均。$f(x)=(\prod_{i=1}^nx_i)^{1/n},;\mathrm{dom};f=\mathbf{R}_{++}^n$
log-determinant。$f(X)=\log\det X,;\mathrm{dom};f=\mathbf{S}_{++}^n$
凹（concave）
仿射函数。$ax+b$
幂函数。$x^{a},0\le a\le1$
对数函数。$\log(x),x\in\mathbf{R}_{++}$
1.6 Epigraph and sublevel set
与凸锥类似。其实 epigraph 就是在 sublevel set 的基础上增加了一个维度，假设原来 sublevel set 指的是 sublevel 以下函数线上的点集，epigraph 指的则是 sublevel 和函数之间的面上的点集合。
1.7 Jensen 不等式
- 若 $f$ 为凸函数，则有：
$$
f\left(\theta_{1} x_{1}+\ldots+\theta_{n} x_{n}\right) \leq \theta_{1} f\left(x_{1}\right)+\ldots+\theta_{n} f\left(x_{n}\right)
$$
其中 $0\le\theta_i\le1,\theta_1+\ldots+\theta_n=1$ 。
- Jensen不等式的另外形式：（从概率论的角度看其实就是数学期望 $f[E(x)]\le E[f(x)]$）
$$
f\left(\int_{S} p(x) x d x\right) \leq \int_{S} p(x) f(x) d x
$$
二、保凸运算
非负加权和、无穷和与积分。
$$
\begin{align}
&f=w_1f_1+w_2f_2+\cdots+w_mf_m\
&g(x)=\int_\mathcal{A}w(y)f(x,y)\mathrm{d}y
\end{align}
$$仿射映射和复合（如缩放、平移、投影）
$$
g(x)=f(Ax+b)
$$逐点最大值和上确界
$$
\begin{align}
&f(x)=\max\left{f_1(x)+f_2(x)+\cdots+f_n(x)\right}\
&f(x)=\sup_{y\in\mathcal{A}}g(x,y)
\end{align}
$$复合运算
$$
\begin{align}
g:{\cal R}^n \to {\cal R},h:{\cal R^k} \to {\cal R},f:{\cal R^n} \to {\cal R}\
f(x) = h(g(x))
\end{align}
$$
规则：- $f$ 为凸。$h$ 为凸且非递减，并且 $g$ 为凸。
- $f$ 为凸。$h$ 为凸且非递增，并且 $g$ 为凹。
- $f$ 为凹。$h$ 为凹且非递减，并且 $g$ 为凹。
- $f$ 为凹。$h$ 为凹且非递增，并且 $g$ 为凸。
凸函数的透视算子
$$
g(x,t)=tf(x/t)
$$
三、共轭函数（对偶函数）
定义
假设 $f:\mathrm{R}^n\rightarrow \mathrm{R}$，则将其共轭函数定义为 $f^*:\mathrm{R}^n\rightarrow \mathrm{R}$ ，表示为
$$
f^{*}(y)=\sup _{x \in \operatorname{dom} f}\left(y^{T} x-f(x)\right)
$$
该共轭函数的定义域由 $y\in\mathrm{R}^n$ 组成，其上确界是有限的。其定义可由下图解释解释
共轭函数 $f^*$ 实际上是由一系列仿射函数的逐点上确界组成（$\sup _{x \in \operatorname{dom} f}\left(y^{T} x-f(x)\right)$ 的第一项是关于 $y$ 的线性函数，第二项无关），由于仿射函数是凸函数，而逐点上确界是保凸运算，因此 $f^*$ 是凸函数。因此无论原函数 $f$ 是否为凸，其共轭函数都是凸函数。且仅当 $f$ 为凸且闭合时，$f^{**}=f$ 。
共轭函数的意义
即便一个函数为非凸函数，也可以通过共轭运算获得一个凸函数以求得其最优解。
例子：
- $f(x)=a^Tx+b$
- $f(x)=\mathrm{e}^x$
- $f(x)=x\log(x)$
四、准凸函数
4.1 定义
设函数 $f:\mathbf{R}^n\rightarrow \mathbf{R}$ ，若函数的定义域及其任意下水平集（sublevel）
$$
S_{\alpha}={x\in\mathrm{dom};f|f(x)\le\alpha,\alpha\in\mathrm{dom};f}
$$
为凸集，则称 $f$ 为准凸函数（quasiconvex）。
- 准凸函数对应的下水平集可能是一个区间，也可能包括无穷区间。
- 实例：$\log(x),x\in\mathbf{R}_{++}$ 是准凸/准凹的，因此也是准线性的。
4.2 基本性质
凸函数的许多性质对于准凸函数来说是成立的，或者有类似的性质。
若函数 $f$ 为准凸函数，当且仅当 $\mathrm{dom};f$ 为凸集，且对于所有的 $x,y\in\mathrm{dom};f$ 和 $0\le\theta\le1$ 满足
$$
f(\theta x+(1-\theta)y)\le \max{f(x),f(y)}
$$准凸函数的一阶条件
若函数 $f$ 一阶可微，则 $f$ 为准凸函数，当且仅当 $\mathrm{dom};f$ 为凸集，且对于所有的 $x,y\in\mathrm{dom};f$ ，满足（实际和凸函数的一阶条件是一样的）
$$
f(y)\le f(x)\Longrightarrow\nabla f(x)^T(y-x)\le 0
$$凸函数与准凸函数的区别：如果 $f$ 是凸的，$\nabla f(x) = 0$，那么 $x$ 是 $f$ 的全局极小点，但对于准凸函数，此条件不成立：有可能 $\nabla f(x) =0$，但 $x$ 不是 $f$ 的全局极小点。
准凸函数的二阶条件（实际这里写的是二阶条件的部分逆）
若函数 $f$ 二阶可微，且对于所有的 $x\in\mathrm{dom};f$ 且 $y\in\mathbf{R}^n,y\ne 0$ ，满足
$$
y^T\nabla f(x)=0\Longrightarrow y^T\nabla^2 f(x)y>0
$$
则 $f$ 为准凸函数。也即要求二阶导 $\nabla^2 f(x)$ 正定。
4.3 保准凸的算子
- 非负权值函数的最大值函数、逐点上确界
- 复合
- 最小值函数
参考
- 《Convex Optimization》