本文原作者：汪毅雄，经授权后发布。
导语：本文先介绍了凸优化的满足条件，然后用一个通用模型详细地推导出原始问题，再解释了为什么要引入对偶问题，以及原始问题和对偶问题的关系，之后推导了两者等价的条件，最后以SVM最大间隔问题的求解来说明其可行性。
凸优化理论广泛用于机器学习中，也是数学规划领域很重要的一个分支，当然也是很复杂的。本文总结一下我获取的资料和个人在一些难点上的理解。
当我们要求一个函数 min f(x) 的时候，如果 f(x) 可导，我们通过是通过求 f(x) 的导数来得。
但是如果函数 f(x) 带约束条件，那么问题就开始变复杂了。凸优化的目标就是解决带约束条件函数的极值问题。
凸优化解决的通用模型是：
很显然，所有的极值问题都可以转化成如上的模型。面对这个问题，凸优化理论怎么处理的呢？
1、满足条件
不是所有的极值问题都可以适用的凸优化理论的，它必须满足以下条件：
1、目标函数 f(x) 为凸函数
2、不等式约束函数 g(x) 为凸函数
3、等式约束函数 h(x) 为仿射函数
只有同时满足以上3个条件，才属于凸优化的范畴。
1.1 凸函数是什么？
可以这样理解：
1、定义域为凸集，凸集几何意义表示为：如果集合中任意2个元素连线上的点也在集合C中，则C为凸集，下图左图为凸集，右图为非凸集。
2、二阶可导，且二阶导数大于0
1.2仿射函数是什么？
一句话就是最高阶数为1的函数，如：Ax b，
可以这么理解条件3，等式约束条件 h(x)=0 可以这么写
也就是说 h(x) 和 -h(x) 都必须同时是凸函数，那么其二阶导数就必须为0，也就是说阶数不能超过1。
2、原始问题
对于凸优化的通用模型，由于其带有约束条件，很难处理，因此我们会考虑怎么用一个式子来表述那个通用模型呢？
其拉格朗日函数的max就在求min的时候就可以作为等价模型，这句话很拗口，这块也是一个难以琢磨的点，很多资料都是直接给出结果，我这边试着一步一步剖析。
我们写出模型的拉格朗日表达式
如果这么定义拉格朗日表达式，那么
就上述模型就等价于 f(x)，为什么呢？
我么可以看到这个函数是以α，β的函数，其中α必须大于等于0. 那么 g(x)、f(x)、h(x)都可以看作常量。而我们的约束条件是：
A、设想一下不满足约束条件的话：
1）假设 g(x)>0 h(x)=0，那么拉格朗日函数可表示为
这是一个线性函数，因为 g(x)>0，所以函数的最大值点肯定是在α为 ∞的时候，因此这种情况
的值为 ∞。
2）假设 g(x)<=0 h(x)!=0，那么拉格朗日函数可表示为
同理，如果h(x)>0，则函数的最大值点肯定是在β为 ∞的时候取到。如果h(x)<0，则函数的最大值点肯定是在β为-∞的时候取到。也就是无论如何，
的值依然为 ∞。
也就是说，如果不满足约束条件，
的值永远为 ∞。
B、如果满足约束条件的话，那么拉格朗日函数可表示为
由于α>=0, g(x)<=0,所以
必然为0或负数，也就是说，这时候
值就为 f(x)。
而在求min f(x)的情况下，如果不满足约束条件
的值为 ∞，只有满足才为f(x)。因此当且仅当，在求min f(x)的前提下：
所以min-max就是我们转化的原始问题！
3、对偶问题
3.1 为什么要转成对偶问题 - 个人理解？
1） 方便求解
2） 规划理论中，对于不知道有没有解的情况，可以通过对偶问题来缩小范围。
引用一个经典的由不是很恰当的例子说：
- 要证明一个人有罪，那么举出他犯罪的例子即可。
- 要证明一个人无罪呢？这是不可能的。往往很多原始问题就很类似。
所以可以通过它的对偶问题来说：
- 如果无法找到他有罪的证据，那么他就是无罪的。
这样问题就变得有可行解了。
3.2 怎么理解对偶问题？
先写出拉格朗日表达式：
把原始问题转成其对偶问题，也就是先求max转成先求min：
为什么这种转化是可行的呢？因为两者始终存在这么一个关系
且在满足kkt条件的前提下，两者是相等的！
用图来说就是
3.2.1 为什么min-max >= max-min？
1、先简单理解一下这个，对于任意的存在最小值的 f(x), 总有任意的x*，都有：
其中等式成立的条件是
也就是在x*处的导数为0.
2、min是以x为参数的函数，假设它的最优解为x*，那么原始问题的结果为：
max是以α、β为参数的函数，假设它的最优解为α*、β*，那么对偶问题的结果为：
3、那么我们都有以下推断
由于由以下关系，所以第一个大于等于号成立
由step1中所讲述的，第二个大于等于号也成立。
因此min-max >= max-min是成立的。
3.2.2 KKT条件
在本节最开始说了，我们需要的:
不是原问题 > 对偶问题，而是原问题 = 对偶问题。
因此在3.2.1推导的公式中，两个大于等于号必须取等号，这就能推导出我们的KKT条件。
在第一个大于等号中，强制其为等号，推导出的条件为：
- 条件1（著名的互补松弛定理）：
，也就是
在第二个大于等号中，强制其为等号，推导出的条件为：
- 条件2：
拉格朗日不等式约束条件：
- 条件3：
初始条件：
- 条件4：
- 条件5：
如果同时满足以上5个条件，那么原问题就可以等价于对偶问题！
凸优化与SVM
1、满足条件
回到SVM的初始模型
可以看到，
是二次函数，典型的凸函数！
而约束条件最高阶只有一阶，确实是仿射函数。
也就是说，SVM可以套用凸优化理论。
2、建模
可以很简单的写出，其拉格朗日形式为：
其对偶问题是先求以w、b为参数的min，再求以α为参数的max，这部分具体推导已经在文章
《 机器学习之SVM - 理论知识 》中做了，有兴趣可以了解。
最终得到的结果是：
3、KKT条件
如果两个问题等价，那么其KKT条件，我们也套用模型中内容，可以推导出：
令
那么有：
1、初始条件：
2、拉格朗日条件：
3、互补松弛条件：
4、参数导数为0条件：
更多优质技术文章请关注官方微信公众号：
长按/扫描关注我们更多优质技术文章请关注官方知乎机构号：
https://www.zhihu.com/org/teng-xun-zhi-neng-tai-ji-qi-xue-xi-ping-tai/activities
