掌握机器学习数学基础之凸优化理论（三）

这篇文章继续介绍关于凸优化的知识，目录如下：

仿射集,凸集和凸锥

超平面，半空间及凸集分离定理

不改变凸性的运算

凸函数及凸优化简述

无约束的优化，等式约束优化，不等式约束优化

线性规划中对偶理论

拉格朗日对偶理论

读完估计需要10min，这里主要讲解第三部分～

线性规划中对偶理论

首先，我们来说说什么是线性规划:线性规划法是解决多变量最优决策的方法,是在各种相互关联的多变量约束条件下,解决或规划一个对象的线性目标函数最优的问题,而描述线性规划问题的常用和最直观形式是标准型。

而其他类型的问题，例如极小化问题，不同形式的约束问题，和有负变量的问题，都可以改写成其等价问题的标准型。

讲完线性规划，下面讲下他的对偶理论，首先为什么要有对偶理论？

判断一个线性规划有没有解，这点很重要，因为对应一个无解线性规划问题，我们是不能简单的证明没有解的，但这个时候，找到一个跟原问题的对偶问题密切相关的问题，如果这个问题有解，原问题就没解。这样就提供了一个简单的证明原问题没解的途径。（至于其中原因比较复杂，感兴趣可自行了解）

对偶问题有时比原问题更简单，更加容易求解，而且，在求解完对偶问题之后，原问题自然可以解出。

首先：原始问题和对偶问题的标准形式如下：

式中max表示求极大值，min表示求极小值，s.t.表示“约束条件为”；z为原始问题的目标函数，w为对偶问题的目标函数；x为原始问题的决策变量列向量（n×1），y为对偶问题的决策变量行向量(1×m)；A为原始问题的系数矩阵(m×n)，b为原始问题的右端常数列向量（m×1），c为原始问题的目标函数系数行向量（1×n）。

举个例子（以下来自课程PPT）：

例子如上图，也就是说，LP1式和LP2式就是一个经典的对偶问题。下面再说一些对偶问题的重要性质和结论：

上面的知识了解就好，只是要知道对偶理论基础。

拉格朗日对偶理论

先给出之前讲过的一般优化式子：

定义函数:

容易发现：

所以可以认为是对原理优化问题中的约束条件进行了吸收，原来的约束优化问题变为无约束优化问题（相对于原来变量x无约束了），即原来的优化问题可以写成：

现在，称上式为原问题，这和最初的有约束问题是等价的。将上式中min和max交换顺序得到对偶问题：

其中

注意：这个不等式也对应着上面讲对偶理论时的弱对偶性质。

通常，对偶问题相对于原问题有比较好的形式（因为对偶函数是一系列仿射函数的逐点求极值。根据凸函数的相关性质，这样的函数必定是凸函数。故无论原问题形式如何，对偶问题都是一个凸优化问题，具体证明可自查），这样，当原问题不好求解时，可以转而求解对偶问题。问题是一般情况下有，所以求解对偶问题只能得到原问题解的下界，不能保证。

当原问题满足一些条件时，可以保证。

Slater条件：存在x ，使得不等式约束严格成立，即。

当原问题为一凸优化问题，且满足Slater条件时，有，这样就原问题和对偶问题的解一致，求解对偶问题即可。显然，Slater是凸优化问题与其对偶问题等价的一个充分条件。

注意，这里很重要，说明了我们为什么要求拉格朗日对偶，这也是SVM为什么是这样的理论的关键！

一种解释：顺其自然，我们可以引出一个重要的概念，对偶间隙，其定义为

，用文字叙述就是原问题的最优值与通过拉个郎日对偶函数获得的其最好（最大）的下界之差，而当满足Slater条件时，也使得对偶间隙变成0，这时使得

注意。这里有证明，对于凸优化问题，如果Slater条件满足了，就满足，而这种情况正是对应着上面的强对偶性质

同时，KKT条件是原问题与对偶问题等价的必要条件。考虑一般优化问题（不一定是凸优化），如果有，则：

这节算是SVM数学理论基础吧，如果觉得SVM太难理解，可以查看下这些知识！

AI遇见机器学习

mltoai