一、定义和基本性质
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\) 为凸函数，则有：
其中 \(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》