首页 > 代码库 > MapReduce----并行支持向量机(PSVM)第二部分之原始对偶内点法

MapReduce----并行支持向量机(PSVM)第二部分之原始对偶内点法

纠错张智威老师关于并行支持向量机的文章:

《PSVM:Parallelizing Support Vector Machines on Distributed Computers》,

在并行原始对偶内点算法中,迭代步长的符号非常混乱,所以,我这里又重新解了一遍。

—————————————————————————————————————————————————————

支持向量机的原问题的对偶问题模型:

     

       

其中:

我们把上述模型,变成用原始对偶问题求解凸二次规划问题的标准形式:


            



下面给出上述模型的Lagrange函数:

然后,我们给出上述最优化问题最优解满足的kuhn-Tucker条件:

其中:


下面给出扰动的Kuhn_Tucker条件:

原始对偶内点法就是用Newton法解上面的扰动的Kuhn_Tucker条件,通过下式求解迭代步长

第一步求解,通过第三式求解:

第二步求解,通过第四式求解:

第三步求解,通过第一式求解:

通过第二式得到,即:,又根据得:

我们令:

则可简化为:

则:

第四步求解,通过第一式求解:

利用上面的表示方法,我们得到:


至此,我们计算出了迭代步长。