凸函数、Jensen不等式、凸集和凸优化

记录凸函数、凸集和凸优化的一些问题。
在一些算法优化中要用到。

凸函数

定义

用简单的一元函数来说，如果对于任意均满足：，则称f(x)为凸函数(convex function)

如果对于任意tϵ(0,1)均满足：

直观上理解，凸函数的隔线在曲线下方。

上述可以推广到多元函数。

如果优化函数是凸函数，那么，局部最小就是全局最小，不会陷入局部最优里。
SVM的目标函数就是一个凸函数

判断凸函数

• 一元函数：求二阶导数的符号来判断，如果非负，就是凸函数
• 多元函数：通过Hessian矩阵的正定性判断，如果Hessian矩阵是半正定矩阵，那就是凸函数

性质：Jensen不等式

凸函数满足Jensen不等式：

一元情况：对于任意均满足：

推广：

如果 f 是凸函数，X是随机变量，那么,

如果把看成是的概率，那么就可以理解成下面的一般式子：

如果是凹函数，那么很容易想到，应该把不等号反过来，原理相同。

在EM算法中，收敛性证明部分就是用到的凹函数Jensen不等式，而不是凸函数。

简言之：

• 凸函数：函数的期望，大于等于，期望的函数
• 凹函数：函数的期望，小于等于，期望的函数

凸集

定义

如果集合 C 为凸集，那么对于任意的，与仿射集的区别在于仿射集并没有的要求，例如一条线段是凸集，而一条直线是仿射集。

扩展到多维的情况，如果有，则称具有形式的点为的凸组合。

称由集合中点的所有凸组合所组成的集合为C的凸包：

与仿射包同样，凸包也是包含 C 的最小的凸集，在一般情况下，设是凸集，x 是随机变量，并且的概率为1，那么

重要的凸集

任意的仿射集和子空间都是凸集，一些比较简单的例如空集，单点集{x0}，全空间，直线/射线/线段都是凸的。

还有一些比较重要的凸集如下：

1. 超平面和半空间
2. Euclid球
3. 椭球$$ \xi ={x|(x−x_c)^T P^(−1) (x−x_c) \le 1}
4. 范数球R^n $$中的范数
5. 范数锥
6. 多面体，即为有限个半空间和超平面的交集，单纯形也为凸集，是一种特殊的多面体半正定锥，即为半正定对称矩阵的集合_

凸优化问题

在优化问题中，凸优化问题由于具有优良的性质（局部最优解即是全局最优解），受到广泛研究。
主要作用是，将有约束条件的转换成无约束条件的。

对于一个含约束的优化问题：
$$
\left{

\right.
$$
其中，f(x) 为一个凸函数，变量x 的可行域C 是一个凸集，那么这个优化问题称为一个凸优化问题。
将上面的约束条件的形式更加明确一点，一个凸优化问题可以写成：

$$
\left{

\right.
$$

其中，f(x) 当然仍然为一个凸函数，但对约束条件有一定要求：是凸函数；为仿射函数。这样的要求当然是为了保证可行域是一个凸集。

不等式约束中为凸函数，而凸函数的水平截集h_i(x)=0
\left{

\right.
$$

要使得满足条件的x 组成的集合为凸集，就要求既是一个凸函数，又是一个凹函数，这样hi(x)便只能是仿射函数了。

以上便是凸优化问题的一般形式。常见的线性规划、二次规划、二次约束二次规划等优化问题都是凸优化问题。