基于拉格朗日乘子法与 KKT 条件的 SVM 数学推导

2019-02-17 17:48:08   最后更新: 2019-02-17 17:48:58   访问数量:973




上一篇文章中,我们通过数学推导,将 SVM 模型转化为了一个有不等式约束的最优化问题

SVM 数学描述的推导

 

 

这看上去是一个非线性规划的复杂问题,在《高等数学》中,我们已经学习过这类问题如何来求解

-- KKT 条件,本文我们就来详细了解一下 KKT 的推导过程

 

 

我们首先需要了解如何处理一个有等式约束的最优化问题

 

问题描述

下图展示了直角坐标系内目标函数 z = f(x, y) 的几何曲面(粉色),以及 φ(x, y) =

0 的约束曲面(蓝色)

 

 

我们将三维曲面映射到二维直角坐标系中的等高线画出来

 

我们要找的就是红色曲线与高度最大等高线的交点,那么如何找到这个点就是我们要解决的问题

 

公式推导

 

 

当约束加上不等式之后,情况变得更加复杂起来

 

 

 

此时,极值点 (x0, y0) 有两种可能:

  1. (x0, y0) 在 g(x) < 0 的区域内
  2. (x0, y0) 在 g(x) = 0 的边界上

 

极值点在约束条件区域内

下图展示了 (x0, y0) 在 g(x) < 0 的区域内的情况:

 

无论是两图中的那种情况,最优化问题的极值点就是 f(x, y) 的极值点,也就是说约束条件失去了作用,此时我们只需要通过求导法则就可以得到 z=f(x, y) 的极值点

计算出来 f(x, y) 的极值点后,带入约束条件,如果满足则求解成功,否则说明极值点在约束条件边界上

 

极值点在约束条件边界上

在这种情况下,我们成功将不等式约束的优化问题转化为了有等式约束的优化问题,根据上面我们推导出的拉格朗日乘子法就可以计算出极值点

(x0, y0) 的取值,以及拉格朗日乘子 λ 的值

 

 

 

 

 

于是,问题转换成为:

 

 

欢迎关注微信公众号,以技术为主,涉及历史、人文等多领域的学习与感悟,每周三到七篇推文,全部原创,只有干货没有鸡汤

 

 

同济大学《高等数学》第七版

https://blog.csdn.net/the_lastest/article/details/78136692

http://www.cnblogs.com/ooon/p/5721119.html

https://www.cnblogs.com/ooon/p/5723725.html

 






技术帖      机器学习      svm      高等数学      拉格朗日乘子法      kkt      machine learning     


京ICP备15018585号