转载 | 凸优化 convex optimization

**原文出自：压缩感知中的数学知识：凸优化**，简单易懂。

这里再推荐一个关于凸优化的综述Convex Optimization Overview，介绍的比较全面。

0 引言

对于任意两点x和y(x,y ∈ Rn)，则对于0<=μ<=1，关系μx+(1-μ)y表示x和y连线之间的所有点。把n简化到一维的情况，即x和y就是两个实数。证明如下：

1
2
3
4
5
6
7
假设y>x(即y-x>0)，在一维情况下，只要证明x<=μx+(1-μ)y<=y就可以了。
证明：
x-[μx+(1-μ)y]=(1-μ)x-(1-μ)y=(1-[μx+(1-μ)y]<=0(因为1-μ>=0，x-y<0)
所以x<=μx+(1-μ)y
y-[μx+(1-μ)y]=μ(y-x)>=0
所以μx+(1-μ)y<=y
得证！

虽然上面证的只是一维，但在多维时可以分解，比如二维时可以分解成横坐标x和纵坐标y，对于每一个坐标轴都是一维的，综合起来就得到了多维的结果。对应到几何关系上来看，对于0<=μ<=1，关系μx+(1-μ)y表示x和y连线之间的所有点。

1 凸集

明白了上面的基础后，这个定义就简单了：若某集合中的x和y两个点，若x和y连线之间的所有点（即0<=μ<=1，μx+(1-μ)y）仍属于这个集合，则称此集合为凸集。

直观几何表示如下：

左边的是凸集，右边的不是凸集，因为右边的集合中任意两点x和y连线之间的所有点有时不属于这个集合（右图中的连线）。

2 凸函数

对于(x)是定义在某凸集（非空的，空集也被规定为凸集）上的函数，对于凸集中的任意两点x1和x2，若f[μx1+(1-μ)x2]<=μf(x1)+(1-μ)f(x2)，则称函数f(x)为凸函数。

直观几何表示如下：

也就是说两点对应的函数值f(x1)和f(x2)的之间的连线（μf(x1)+(1-μ)f(x2)）大于等于相应的（即同一个μ值）两点之间连线（μx1+(1-μ)x2）所对应的函数值f[μx1+(1-μ)x2]，这其实应叫 下凸。

如果把上面不等式中的等号去掉，即f[μx1+(1-μ)x2]<μf(x1)+(1-μ)f(x2) ，其中0<μ<1，则称f(x)为严格凸函数。

3 凸优化（凸规划）

若对于以下优化问题：

若目标函数f(x)是凸函数且可行集R是凸集，则称这样的问题为凸优化问题。这个也可以换一种更一般的表达方式：对于以下优化问题

如果目标函数f(x)和共l个约束函数gi(x)都是凸函数，则称这样的问题为凸优化问题。实际上，可以证明，约束函数gi(x)都是凸函数则它的可行集是凸集，具体证明如下：

4 凸优化的特性（或者说有什么用）

  • 如果一个实际的问题可以被表示成凸优化问题，那么我们就可以认为其能够得到很好的解决。
  • 还有的问题不是凸优化问题，但是凸优化问题同样可以在求解该问题中发挥重要的左右。比如松弛算法和拉格朗日松弛算法，将非凸的限制条件松弛为凸限制条件。
  • 对于凸优化问题来说，局部最优解就是全局最优解。
  • 若f(x)在非空可行集R上是严格凸函数，则全局极小点是唯一的。

也就是说如果把一个非凸优化问题转化为凸优化问题（松弛算法），则若求得一个局部最优解即为得到了全局最优解（若目标函数在可行集上是严格凸函数，则此解还是唯一的），并且凸优化问题能够比较好的得解决，因此在看压缩感知的文献时经常会看到如何如何修改一下约束条件使之变为一个凸优化问题。

最后附上常用的向量范数和矩阵范数的定义

End