定理5:设H为半正定矩阵(所有特征值大于等于0)，则 二次规划问题的全局极小点当且仅当它是一个局部极小点或者K-T点。 当H为半正定矩阵，目标函数为凸函数时，该二次规划被叫做凸二次规划，它的任何K-T点都是极小点。回想我们开篇要解决的那个问题，目标函数显然是一个凸函数，所以它是一个凸二次规划问题，所以一定存在全局极小点(真好！)。 到此，我们就可以开始解决开篇的那个问题：   <img alt="y_i(+b) \geq 1" src="http://chart.apis.google.com/chart?cht=tx&chl=y_i%28%3cw%2cx_i%3e%2bb%29+%5cgeq+1"> 已经确定它是一个凸二次规划问题了，那么可以利用其拉格朗日函数：<img alt="L(w,b,\alph)=\frac{1}{2}||w||^2-\sum\limits_{i=1}^n\alph_i(y_i(+b)-1)" src="http://chart.apis.google.com/chart?cht=tx&chl=L%28w%2cb%2c%5calph%29%3d%5cfrac%7b1%7d%7b2%7d%7c%7cw%7c%7c%5e2-%5csum%5climits_%7bi%3d1%7d%5en%5calph_i%28y_i%28%3cw%2cx_i%3e%2bb%29-1%29"> 通过对 和 求偏导数后得到：   带入原始拉格朗日函数，转化为对偶问题： <img alt="L(w,b,\alph)=\frac{1}{2}||w||^2-\sum\limits_{i=1}^n\alph_i(y_i(+b)-1)" src="http://chart.apis.google.com/chart?cht=tx&chl=L%28w%2cb%2c%5calph%29%3d%5cfrac%7b1%7d%7b2%7d%7c%7cw%7c%7c%5e2-%5csum%5climits_%7bi%3d1%7d%5en%5calph_i%28y_i%28%3cw%2cx_i%3e%2bb%29-1%29"> <img alt="=\frac{1}{2}(\sum\limits_{i,j=1}^n{y_iy_j\alph_i\alph_j})-(\sum\limits_{i,j=1}^n{y_iy_j\alph_i\alph_j})+(\sum\limits_{i=1}^n{\alph_i})" src="http://chart.apis.google.com/chart?cht=tx&chl=%3d%5cfrac%7b1%7d%7b2%7d%28%5csum%5climits_%7bi%2cj%3d1%7d%5en%7by_iy_j%5calph_i%5calph_j%3cx_i%2cx_j%3e%7d%29-%28%5csum%5climits_%7bi%2cj%3d1%7d%5en%7by_iy_j%5calph_i%5calph_j%3cx_i%2cx_j%3e%7d%29%2b%28%5csum%5climits_%7bi%3d1%7d%5en%7b%5calph_i%7d%29"> <img alt="=\sum\limits_{i=1}^n{\alph_i}-\frac{1}{2}(\sum\limits_{i,j=1}^n{y_iy_j\alph_i\alph_j})" src="http://chart.apis.google.com/chart?cht=tx&chl=%3d%5csum%5climits_%7bi%3d1%7d%5en%7b%5calph_i%7d-%5cfrac%7b1%7d%7b2%7d%28%5csum%5climits_%7bi%2cj%3d1%7d%5en%7by_iy_j%5calph_i%5calph_j%3cx_i%2cx_j%3e%7d%29"> 这样就把带不等式约束的优化问题通过其对偶形式转化为只带等式约束的优化问题，即下面的最优化问题W：？？？？ <img alt="max \quad\quad\quad\quad W(\alph)=\sum\limits_{i=1}^{n}{\alph_i}-\frac{1}{2}\sum\limits_{i,j=1}^{n}{y_iy_j\alph_i\alph_j}" src="http://chart.apis.google.com/chart?cht=tx&chl=max+%5cquad%5cquad%5cquad%5cquad+W%28%5calph%29%3d%5csum%5climits_%7bi%3d1%7d%5e%7bn%7d%7b%5calph_i%7d-%5cfrac%7b1%7d%7b2%7d%5csum%5climits_%7bi%2cj%3d1%7d%5e%7bn%7d%7by_iy_j%5calph_i%5calph_j%3cx_i%2cx_j%3e%7d">   求得 后就得到了 ，它使得几何间隔 取最大值，从而得到最优分类超平面。 K-T点要满足的条件还有一个是：<img alt="\alph^*_i(y_i(+b^*)-1) =0" src="http://chart.apis.google.com/chart?cht=tx&chl=%5calph%5e*_i%28y_i%28%3cw%5e*_i%2cx_i%3e%2bb%5e*%29-1%29+%3d0">，这个式子说明了什么问题呢？ 1、显然，函数间隔不等于1的那些输入点的拉格朗日系数必为0(这些点是非积极因素)，而函数间隔恰好为1的输入点的拉格朗日系数则不为0(这些点是积极因素)，这说明确定最终分类超平面的就是这些函数间隔为1的边界点，所以这些输入点就是支持向量(Support Vector)。从这里也能看出支持向量机的抗干扰能力比较强，对非积极因素的扰动对于最优化解没有影响； 2、<img alt="y_i(+b^*)-1=0" src="http://chart.apis.google.com/chart?cht=tx&chl=y_i%28%3cw%5e*%2cx_i%3e%2bb%5e*%29-1%3d0">，其中i为支持向量，因为：<img alt="y(+b^*)=y(\sum\limits_{i \in support \quad vector}y_i\alph_i^*+b^*)=1" src="http://chart.apis.google.com/chart?cht=tx&chl=y%28%3cw%5e*%2cx_i%3e%2bb%5e*%29%3dy%28%5csum%5climits_%7bi+%5cin+support+%5cquad+vector%7dy_i%5calph_i%5e*%3cx_i%2cx%3e%2bb%5e*%29%3d1"> ，我们的目标函数<img alt="=\sum\limits_{i,j \in support \quad vector}{y_iy_j\alph_i^*\alph_j^*" src="http://chart.apis.google.com/chart?cht=tx&chl=%3cw%5e*%2cw%5e*%3e%3d%5csum%5climits_%7bi%2cj+%5cin+support+%5cquad+vector%7d%7by_iy_j%5calph_i%5e*%5calph_j%5e*%3cx_i%2cx_j%3e"> <img alt="=\sum\limits_{j \in support \quad vector}{\alph_j^*y_j}\sum\limits_{i \in support \quad vector}{y_i\alph_i^*}" src="http://chart.apis.google.com/chart?cht=tx&chl=%3d%5csum%5climits_%7bj+%5cin+support+%5cquad+vector%7d%7b%5calph_j%5e*y_j%7d%5csum%5climits_%7bi+%5cin+support+%5cquad+vector%7d%7by_i%5calph_i%5e*%3cx_i%2cx_j%3e%7d">   (注意这里 为常数，且有约束条件） 于是通过这样的对偶转化，我们得到了实现几何间隔为 的最大间隔超平面。 通过上面的推导也可以看出将二次规划转化为其对偶问题可以简化约束条件，让我们记住最优化问题W吧，这是一个很牛逼的转化，这个式子还有个特点，就是“数据仅出现在内积中”。 前面的讨论都是说输入样本是线性可分的时候怎么找到最大间隔超平面来划分两类数据，那么如果输入样本是线性不可分的，那可怎么办呀，前面的那些讨论不就成徒劳的了么？学习SVM后才知道它牛的地方，如果我们可以通过某种函数映射将输入样本映射到另外一个高维空间并使其线性可分的话，前面的讨论结果不就都可以用到了么，还记得“数据仅出现在内积中”吧，假设这个映射关系是：F" src="http://chart.apis.google.com/chart?cht=tx&chl=%5cPhi%3aX-%3eF">，这时候的内积<img alt="" src="http://chart.apis.google.com/chart?cht=tx&chl=%3cx_i%2cx_j%3e">就变成了<img alt="" src="http://chart.apis.google.com/chart?cht=tx&chl=%3c%5cPhi%28x_i%29%2c%5cPhi%28x_j%29%3e">，如果有方法能够将内积<img alt="" src="http://chart.apis.google.com/chart?cht=tx&chl=%3c%5cPhi%28x_i%29%2c%5cPhi%28x_j%29%3e">直接算出，就将把输入样本“从低维空间向高维空间映射”和“求映射后的内积”这两步合并成了一步，这样直接计算的方法就是核函数方法，下篇学习核函数吧，SVM的理论部分还是很数学的啊！ | 
