对偶函数博客 机器学习算法系列(二):拉格朗日对偶性

娱乐新闻 2020-02-10122未知admin

  在约束最优化问题中,常常会利用到拉格朗日对偶性求解。在常用的机器学习算法中,支持向量机和最大熵模型都使用到该方法求最优解。因为后面将要讲到这两个算法,所以先介绍这种方法作为知识的铺垫。

  对于有约束的问题,拉格朗日对偶性是将原始问题为最优问题,通过求解对偶问题而得到原始问题的解。

  假设f(x),ci(x),hj(x)是定义在Rn上的连续可微函数,最优化原始问题为:

  因为α_i≥0,c_i≤0,h_j等于0,所以L(x,α,β)的第二项小于等于0,对偶函数第三项等于0,则可以推出:L(x,α,β)≤f(x)。

  一句话总结就是对于同一个函数L,最小化后的最大值仍然小于或等于最大化后的最小值。

  为了使得对偶问题的最优解也是原始问题的最优解,对偶函数就必须满足KKT条件,也就是说KKT条件是其充分必要条件。接下来我们将为什么要满足以下的KKT条件。

  要使得对偶问题的最优解也是原始问题的最优解就要满足d_*=p_*,首先前三个条件对各变量求偏导得到他们的极值,这也是为什么要一开始要定义三个函数连续可导。

  第四个条件是因为在前面已经提及L(x,α,β)的第二项小于等于0,要使得L等于f(x),就得让第二项等于0,因为α_i≥0,对偶函数c_i小于等于0,所以要第二项等于0,只能是每个α_i*c_i等于0。

  第五个条件和第七个条件是原始问题的约束条件,第六个问题是拉格朗日乘子法需要满足的定义。

  使用对偶问题求解是因为求解对偶问题比求解原始问题更加简单方便。比如在SVM中通过求解对偶问题能够使得求解的算法复杂度降低,方便核函数的引入等好处。具体为什么将在SVM的时候解释。返回搜狐,查看更多

原文标题:对偶函数博客 机器学习算法系列(二):拉格朗日对偶性 网址:http://www.gracefriends.com/yulexinwen/2020/0210/5659.html

Copyright © 2002-2020 后继有人新闻网 www.gracefriends.com 版权所有  

联系QQ:1352848661