【通俗理解】凸优化

注：以下内容参考了Shu-Cherng Fang教授2009年在清华的夏季学期课程《Global Optimization with Applications》讲义。

今天介绍一点凸优化方面的知识～内容可能有点无聊，看懂了这篇文章，会对求极值和收敛有进一步理解，比如：

1. 了解为什么向量机（SVM）等的推导中，求极值时可以把约束条件加在目标函数后面来变成一个无约束的优化问题。
2. 理解EM算法（聚类，GMM等）为什么收敛。

之前文章有介绍过，一个算法有效至少要满足两个条件：1）极值存在，2）收敛。极值不存在说明模型无效，算法无意义。算法不能收敛意味着找不到极值，也没有价值。这两个问题凸优化都可以帮我们回答。

在开始之前，我们先来回顾一下支持向量机（SVM）的推导过程。

SVM的任务就是寻找这样一个超平面H把样本无误地分割成两部分，并且使H1和H2的距离最大。要找到这样的超平面，只需最大化间隔Margin，也就是最小化w^2。

然后直接告诉你：对于不等式约束的条件极值问题，可以用拉格朗日方法求解。而拉格朗日方程的构造规则是：用约束方程乘以非负的拉格朗日系数，然后再从目标函数中减去。于是得到拉格朗日方程如下：

为什么可以这样做？看完本文你就能理解了。

凸集合与凸函数：在前面一篇《党给我智慧给我胆，梯度给我努力的方向》中，已经说明了梯度的作用，并指出个人的行为都自觉或无意地顺着梯度方向。

这不难理解。如果让一个蒙上眼睛的人去山顶，他自然会选择海拔升高的方向行走。至于最后能不能到达，要看地形。要是一个土丘（凸函数）那没问题，如果要是连绵不断的群山（非凸函数），只能保证到达一个小山峰（极值），而这个不一定是所有山峰中最高的（最值）。

由于凸函数的极值点就是最值点，相对于非凸函数，我们更喜欢凸函数。这里不但要求目标函数是凸的，其定义的空间也必须是凸的集合。正如要求地形是凸的，能走的路构成的集合也必须是凸的。

凸凸凸，到底啥是凸集合，啥是凸函数？？？

凸集合：满足集合内任意两点的连线也在这个集合里的就是凸集合。凸集合有个有趣的separating性质，以二维空间为例，任意一点y不属于这个凸集合，则一定存在一条直线把这个点和凸集合分开。

凸函数：下面两个图画出了凸函数，也给出了凸函数的两个性质：

1. 两点永远太高；如下面第一个图，用凸函数两点之间的连线上的一点R来估计函数值L，永远有R>L。

1. 一点永远太低；如下面第二个图，用凸函数的切线上的一点R来估计函数值L，永远有R<L。写出

上面的第一个性质“两点永远太高”也可以扩展到多个点的线性组合，写起来就是Jensen不等式的形式

其中a_i取值0~1，a_i的和为1。

根据第二个性质“一点永远太高”，很容易证明党给我智慧给我胆，梯度给我努力的方向里提到的凸函数极值点的一个性质：

根据上面性质“一点永远太高”的公式，有：

上面公式可以从两个层面来理解。一方面x*是极值，即任取定义域内一点得到的f(y)>f(x*)；另一方面定义域任选一点y沿着y-x*的方向一定能达到x*。找到x*之前是不知道方向y-x*的，通常用梯度。

上镜图：为了把凸函数（convex function）和凸集合（convex set）一起讨论，要介绍一下上镜图（epigraph）的概念，如下图所示就是函数f上方的所有点构成的集合。

分割定理和支撑定理：显然，凸函数对应的上镜图是一个凸集合。这样可以和上面的第二个性质“一点永远太低”联系起来了。稍微扩展一下到多维空间，二维空间的直线对应着多维空间的超平面（hyperplane）。第二个性质扩展到多维空间就是：存在一个超平面可以支撑起这个函数对应的上镜图，而且这个超平面和函数有一个交点。这个超平面叫做“支撑超平面”（supporting hyperplane）。

现在可以总结一下凸集合的两个重要性质了：

1. separating：即凸集合可以被一个超平面把凸集合和凸集合外的一点区分开（separating hyperplane存在）；
2. supporting：凸集合边缘上任意一点都对应一个和凸集合相切的超平面（把整个空间分成含有凸集合和不含凸集合两部分）（supporting hyperplane存在）。

其中supporting定理通过函数上镜图的概念和凸函数联系起来了，这构成了凸优化中对偶性duality的基石。在凸优化中的对偶，和信号处理里的傅里叶变换一样重要。

对偶：对偶性，是通过对偶变换（conjugate transform）把原函数变成了另一个函数（一定是凸的）。对函数y=f(x)来说，其对偶函数是以切线斜率k为自变量，以切线和y轴交点y*为值的函数。对应到多维函数，其对偶函数是以其支撑超平面（切平面）的正交方向向量，函数值是这个超平面和函数值对应坐标轴的交点。写出来是这个样子的：

看不懂吧？先思考下面两个问题：

1. 前面说的“支撑切平面的正交方向向量”是个什么鬼？
2. 上面conjugate transform得到的公式h(y)，为什么是个集合的形式，会有sup/inf？（sup/inf表示所有满足条件的当中选最大/小的那个）

回顾一下前面讲supporting hyperplane前，先介绍了separating hyperplane。设想负无穷有一个点M，那么存在separating hyperplane把这个凸函数的上镜图和M区分开，这无数个separating hyperplane构成一个集合，取sup/inf就是取到和函数上镜图相切的超平面！所以对偶函数对应着原函数对所有separating hyperplane组成的集合取sup/inf，即对偶函数对应着原函数的所有supporting hyperplane的集合。

对偶函数满足对偶不等式（conjugate inequality）

当y取值对应到切平面时取等号。此时y就是“支撑切平面的正交方向向量”，即梯度！上面第一个问题你回答上来了么？

Primal problem & Dual problem：好了，现在大致对“对偶性”有一点几何理解了，但这又和求极值有什么关系？是否还记得小学“线性规划”一节，极值一定出现在两条直线的交点或某条直线上？换句话说，极值一定出现在几条直线围成的形状的边缘上，再换句话说，极值一定出现在几条直线围成的形状的切线/切平面上。

受此启发，所以对“切平面”重点研究可能是正确的方向。再看上面的对偶不等式，如果有一些约束使得<x,y>=0，则f(x)的最小值就和-h(y)的最大值相等了，这样就把求min{f(x)}问题转化成求max{-h(y)}=min{h(y)}问题。称初始求min{f(x)}的问题成为primal problem，求min{h(y)}问题称为dual problem。

好的，现在知道了，某些条件下可以通过求dual problem来间接求primal problem。但为什么有什么好处？这是因为很多情况下dual problem比primal problem好求解！

下图是一个典型的问题，求X内函数f(x)的极值。

即使f(x)是一个简单的凸函数（比如二次函数）也不太容易求解。问题的复杂性在于定义域是有约束条件（subject to some constraint）的。如果对x取值没有约束（定义域X为整个超平面），则根据凸函数极值点性质

很容易知道在极值点x*有对应的导数/梯度为0。而对偶变换后，得到的dual problem可能是一个无约束条件的问题，非常容易求解。比如要求解：

s.t.是subject to的简写，是对x的约束条件。其对应的dual problem为

是一个无约束的求极值问题，要简单多了。

注意，上面说的求到了dual problem的极值，就知道了primal problem的极值，这是有条件的：<x,y>=0。当大于零时，所谓的duality gap就出现了。搞数学的人给出了一堆各种条件的定理，指出什么条件下可以没有duality gap，这不是我们工程师所关心的，不去浪费时间探讨了。看到这里，只要了解对偶是什么回事就可以了。

拉格朗日对偶：拉格朗日乘数法（Lagrange multiplier）在中学就学过了，用来求解有约束情况下的极值问题。比如一个人从家M点到公司C点，中间要去小河边打一桶水，在小河的哪个位置打水最近？

河流的曲线方程g(x,y)就是这个问题的约束，要求的就是在这个约束条件下，到M和C点的距离和最近。直接套公式很容易求解，但相信很多人不明白为什么拉格朗日乘数法为什么起作用。这里我们把它套在duality的框架下进行讨论。

定义拉格朗日函数（lagrangian function）如下

这和conjugate transform的区别仅仅在于一个<x,y>。不继续说了，否则还要介绍鞍点（saddle point），强对偶，弱对偶，还有min-max和max-min的概念。这里只是告诉大家拉格朗日乘数法也可以归结于duality的框架中。最前面的对偶通常叫做conjugate dual或geometric dual，Fenchel's dual，后面用拉格朗日函数的叫做Lagrangian dual。

对支持向量机（SVM）熟悉的同学知道，推导时的目标函数是一个二次函数，约束条件是一个超平面把两类标记的点分开。求解这个最优化问题（quadratic programing）就用了Lagrangian dual。有人说了，好像没有看到有求所谓的h(y)啊，是不是打开方式不对？这是因为二次函数的duality还是一个二次函数……好尴尬～下图f(x)=0.5x^2，其conjugate dual是g(y)=-0.5y^2。

中学老师可没有告诉你duality，直接让你在目标函数后面把约束乘以一个拉格朗日乘子加在后面，你能理解才怪……

KKT条件：其实是对拉格朗日方法的一个扩展。一定要背下来，以后求解quadratic programing（目标函数是一个二次函数）时就套公式。很多实际问题的目标函数都是二次函数，因为二次函数可以代表欧式距离（回想距离公式x^2+y^2），可以代表能量（x^2），是一个好的error/cost function。

总结

对偶是凸优化的基石，延伸出各种优化方法。正如信号处理中时域上不好解决的问题变换到频域去解决。遇到目标函数是二次函数的，直接看看KKT条件能不能用。数学系的学生要考察并证明duality gap是否存在之类的，我们工科的学生不管这些了，直接套公式先跑起来再说～