凸优化整理

凸集

在最优化范畴中，凸优化问题是一类比较常见的，性质很好，很多时候可以帮助我们解决非凸问题的工具。

如果一个凸函数min f(x),它的可行集x∈S，S是一个凸集合，如此一般来说我们就认为这是一个凸优化的问题。

假如有两个函数都写成min f(x)，x∈[a,b)，它们的函数图像如下

在第一个函数图形中找最小点，那么这个点是一个平稳点(导数为0)；但是在第二个函数图形中，我们可以找到3个平稳点，第一个平稳点在它的邻域(非整个a、b区间)中目标函数值是最小的，我们会称该点为局部最优解。第三个平稳点是全局最优解。

这样我们就发现，在第一个函数中找到的最优解一定是全局最优解，并且就是这个平稳点；而第二个函数中有多个平稳点，但是只有一个是全局最优解。产生这个的情况的原因是由函数本身的性质决定的，第一个函数是一个凸函数，第二个函数是一个非凸函数。

现在我们再来看一个多元函数的情况，min (x_1^2)+(x_2^2)，x∈S，这里S是两个不同的区域

首先该二元函数的图像是这个样子的，是一个立体的形状

S的两个不同区域也是三维空间中的不规则区域，我们现在只是使用它们的剖面图。

无论图1还是图2的虚线部分是该二元函数曲面的不同等高线。我们令(x^*)是一个最优解，在图1中，我们知道(x^*)是S的边界跟弧线的切点，从该点沿着目标函数的负梯度方向作图，它会垂直于该等高线的切线。我们在S内任意找一个点x，总会满足

-(\nabla)f((x^*)^T)(x-(x^*))(\le)0，(\forall　)x∈S

它的意思是在S中任取一点与(x^*)负梯度方向的夹角总是大于等于(90^∘)的。公式本身是两个向量的内积小于等于0。此处可以参考线性代数整理 中的向量点乘的应用。

在图2中满足这个条件的点并不是唯一的，它有两个点都满足，但只有一个最优解，也就是(x^*)。这里是由S集本身的性质决定的，图1的S集是一个凸集，图2的S集是一个非凸集。

如果一个目标函数是一个凸函数，其可行集也是一个凸集，那么我们找到的最优解就是全局解，我们找到的平稳点就是最优解。

基本定义：凸集

凸集(convex set):对于任意的x,y∈C与任意的λ∈0,1有

λx+(1-λ)y ∈ C

其几何意义就是集合中两点的连线仍属于此集合。

上图中第一个图形是一个圆，它是一个凸集；第二个图形是一个多面体，它也是一个凸集；第三个图形是一个非凸集，这个很容易判断。

• 凸组合

凸组合(convex combination):有k个点(x^1),(x^2),(x^3)...(x^k)

当(λ_1x^1)+(λ_2x^2)+(λ_3x^3)+...+(λ_kx^k)，

其中(λ_1),(λ_2),(λ_3),...,(λ_k)(\ge)0，(\sum_{i=1}^k)(λ_i)=1

这个就是 (x^1),(x^2),(x^3)...(x^k)的凸组合。

关于组合，(λ_1x^1)+(λ_2x^2)+(λ_3x^3)+...+(λ_kx^k)本身就是一个线性组合。具体可以参考线性代数整理 中的线性组合。

• 凸包

凸包(convex hull of set C):由任意一个集合C(不一定是凸集)中点的凸组合构成

在上图中的左图中离散的点是集合C，我们任取一些点来做凸组合，最终会形成外面的五点的五边形。

在右图中的集合C是

蓝色曲线连接的区域，任取一些点来做凸组合

这里我们会发现因为凸包是凸组合构成的，所以它一定是凸集。对于一个非凸集来说，如果对该集合产生一个凸包，那么就会将该非凸集转化成一个凸集。

凸包的作用主要用于解非凸优化问题的时候，会对一个非凸的问题进行凸化的作用。

常见凸集

超平面(hyperplane):H={x|(a^T)x=b}   (a

0)

半空间(halfspace):(H^+) ={x|(a^T)x(\ge)b}   (a

0)；(H^-) ={x|(a^T)x(\le)b}   (a

0)，它就是超平面分开的两个空间，它们都是凸集。

多面体(polyhedra):多个线性不等式所刻画的集合。