本博客已经迁往http://www.kemaswill.com/, 博客园这边也会继续更新, 欢迎关注~
在机器学习中, 很多情况下我们都需要求得一个 问题的全局最优值(global optimum). 大多数的全局最优值很难求得, 但是对于凸问题, 我们可以比较高效的找到其全局最优值, 这是由凸问题的性质决定的.我们将逐步的介绍凸集, 凸函数, 凸问题等.
1. 凸集(convex set)
对于一个集合\(C\), 如果对于任意两个元素\(x,y \in C\), 以及任意实数\(\theta \in \mathbb{R}\)且\(0 \leq \theta \leq 1\)都满足
$$\theta x + (1-\theta)y\in C$$
那么集合\(C\)就是凸集.如下图所示:
凸集的例子包括:
- \(\mathbb{R}^n\)
- 非负象限\(\mathbb{R}_+^n\)
- 范式球(Norm Ball), 亦即\({x: \parallel x \parallel \leq 1}\), 其中\(\parallel \cdot \parallel\)是\(\mathbb{R}^n\)上的范式
- 凸集的交集
- 半正定矩阵
2. 凸函数(convex function)
如果一个函数\(f: \mathbb{R}^n \to \mathbb{R}\)的定义域\(\mathcal{D}(f)\)是凸集, 并且对于所有的\(x,y \in \mathcal{D}(f)\)和\(\theta \in \mathbb{R}, 0 \leq \theta \leq 1\)使得:
$$f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta)f(y)$$
则函数\(f(x)\)是凸函数.
如果把上述限制条件改为对于任意的\(x,y \in \mathcal{D}(f), x \neq y, 0 < \theta < 1\)
$$f(\theta x+(1-\theta)y) < \theta f(x)+(1-\theta)f(y)$$
函数\(f(x)\)是严格凸(strictly convex)的.
如果\(-f\)是凸的, 则\(f\)是凹(concave)的.
凸函数如下图所示
2.1 凸函数的一阶条件
如果一个函数\(f: \mathbb{R}^n \to \mathbb{R}\)是可微的, 那么\(f\)是凸函数当且仅当\(\mathcal{D}(f)\)是凸集, 并且对于任意的\(x,y \in \mathcal{D}(f)\):
$$f(y)>=f(x)+\nabla_x f(x)^T(y-x)$$
其中\(f(x)+\nabla_x f(x)^T(y-x)\)称为\(f\)在点\(x\)处的一阶近似. 上述性质如下图所示:
2.2 凸函数的二阶条件
函数\(f\)是凸的当且仅当\(\mathcal{D}(f)\)是凸集, 并且其Hessian矩阵是半正定的:
$$\nabla_x^2 f(x)\succeq 0$$
2.3 Jensen不等式
凸函数的定义中有
$$f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta)f(y), \hspace{2 pt} 0 \leq \theta \leq 1$$
上式可以扩展到多个点的情况:
$$f(\sum_{i=1}^k \theta_ix_i \leq \sum_{i=1}^k\theta_if(x_i)) , \sum_{i=1}^k\theta_i=1, \theta_i \geq 0$$
也可以扩展到无限多个点或者某个区间的情况:
$$f(\int p(x)xdx) \leq \int p(x)f(x)dx , \int p(x)dx=1, p(x \geq 0)$$
亦即
$$f(\mathbb{E}[x]) \leq \mathbb{E}[f(x)]$$
上式称为Jensen不等式
2.4 Sublevel集合
\(\alpha-sublevel\)集合是凸集的一种, 对于一个函数\(f: \mathbb{R}^n \to \mathbb{R}\), 以及一个实数\(\alpha \in \mathbb{R}\), \(\alpha-sublevel\)集合的定义为
$${x \in \mathcal{D}(f) : f(x) \leq \alpha}$$
可以很容易的证明上述集合是凸集, 对于\(x,y \in \mathcal{D}(f)\)使得\(f(x) \leq \alpha, f(y) \leq \alpha\):
$$f(\theta x + (1-\theta)y) \leq \theta f(x)+(1-\theta)f(y) \leq \theta \alpha + (1-\theta)\alpha =\alpha$$
2.5 凸函数例子
- 指数函数: \(f: \mathbb{R} \to \mathbb{R}, f(x)=e^{\alpha x}\)
- 负对数:\(f: \mathbb{R} \to \mathbb{R}, f(x)=-log x\)
- 仿射函数: \(f: \mathbb{R} \to \mathbb{R}, f(x)=b^T x + c\)
- 二次函数: \(f: \mathbb{R} \to \mathbb{R}, f(x)=\frac{1}{2}x^TAx + b^Tx + c\)
- 范式: \(f: \mathbb{R} \to \mathbb{R}, f(x)=\parallel x \parallel\)
- 凸函数的非负加权和:
$$f(x)=\sum_{i=1}^k w_if_i(x)$$其中\(f_1,f_2,...,f_k\)是凸函数
3. 凸优化问题
凸优化问题的形式如下:
$$minimize \hspace{2 pt} f(x)$$
$$subject \hspace{2 pt} to \hspace{2 pt} x \in C$$
其中\(f\)是凸函数,\(C\)凸集, \(x\)是待优化的变量, 我们通常可以把其写成
$$minimize \hspace{2 pt} f(x)$$
$$subject \hspace{2 pt} to \hspace{2 pt} g_i(x) \leq 0, i=1,...,m$$
$$h_i(x) = 0, i=1,...,p$$
其中\(f\)和\(g_i\)是凸函数,\(h_i\)是仿射函数.
\(g_i\)必须小于等于0, 这样得到的\(x\)的可行域(feasible region)才是凸的(因为\(g_i(x) \leq 0\)定义了一个\(\alpha-sublevel\)集)
3.1 凸问题中的全局最优
凸问题的一个很好地特性是其局部最优解也是全局最优解.推导如下
首先定义局部最优解: 当\(x\)是可行的(亦即位于可行域内), 而且存在\(R > 0\), 使得对于所有\(\parallel x-z \parallel_2 \leq R\)的位于可行点\(z\),使得\(f(x) \leq f(z)\).
然后定义全局最优解: 如果\(x\)是可行的, 且对于其他所有的可行点\(z\)都有\(f(x) \leq f(z)\)
凸问题中的全局最优解等同于局部最优解, 证明如下:
令\(x\)是一个局部最优解, 但不是全局最优解, 所以存在一个可行的点\(y\)使得\(f(x) > f(y)\).根据局部最优解的定义, 没有一个可行点\(z\)满足\(\parallel x-z \parallel_2 \leq R, f(z) < f(x)\). 但是, 我们可以选择$$z=\theta y + (1-\theta)x, \theta=\frac{R}{2\parallel x-y \parallel_2}$$
那么
$$\parallel x-z \parallel_2=\parallel x=(\frac{R}{2\parallel x - y \parallel_2}y+(1-\frac{R}{2\parallel x - y \parallel_2})x)\parallel_2$$
$$=\parallel \frac{R}{2\parallel x - y\parallel_2}(x-y)\parallel_2$$
$$=R/2 \leq R$$
另外, 因为\(f\)是凸函数, 所以
$$f(z)=f(\theta y + (1-\theta)x) \leq \theta f(y) + (1-\theta)f(x) < f(x)$$
因为可行域是凸集,\(x\), \(y\)都是可行的, 所以\(z=\theta y + (1-\theta)x\)也是可行的, 且\(\parallel x-z \parallel_2 < R, f(z) < f(x)\), 假设不成立，所以\(x\) 是全局最优解.
3.2 凸问题的例子
- 线性规划(LP, Linear Programming):
$$minimize \hspace{2 pt} c^Tx+d$$
$$subject \hspace{2 pt} to \hspace{2 pt} Gx \succeq h$$
$$Ax=b$$
- 二次规划(QP, Quadratic Programming):
$$minimize \hspace{2 pt} \frac{1}{2}x^TPx+c^Tx+d$$
$$subject \hspace{2 pt} to \hspace{2 pt} Gx\succeq h$$
$$Ax=b$$
- 二次限制的二次优化(QCQP, quadratically constrained QP):
$$minimize \hspace{2 pt} \frac{1}{2}x^TPx+c^Tx+d$$
$$subject \hspace{2 pt} to \hspace{2 pt} \frac{1}{2}x^TQ_ix+r_i^Tx+s_i \leq 0, i=1,...,m$$
$$Ax=b$$
- 半定规划(Semidefinite Programming):
$$minimize \hspace{2 pt} tr(CX)$$
$$subject \hspace{2 pt} to \hspace{2 pt} tr(A_iX)=b_i, i=1,...,p$$
$$X \preceq 0$$
参考文献:
[1]. Zico Kolter, Honglak Lee. Convex Optimization Overview.
[2]. Stephen Boyd, Lieven Vandenberghe. Convex Optimization.