machine learning / 机器学习

对偶优化问题

对偶问题

在约束最优化问题中,常常利用拉格朗日对偶性将原始问题转换为对偶问题,通过求解对偶问题而得到原始问题的解。至于这其中的原理和推导参考文献[3]讲得非常好。大家可以参考下。这里只将对偶问题是怎么操作的。假设我们的优化问题是:

min f(x)

s.t. hi(x) = 0, i=1, 2, …,n

       这是个带等式约束的优化问题。我们引入拉格朗日乘子,得到拉格朗日函数为:

L(xα)=f(x)+α1h1(x)+ α2h2(x)+…+αnhn(x)

(拉格朗日函数将约束条件融入到表达式中,方便之后的处理)

       然后我们将拉格朗日函数对x求极值,也就是对x求导,导数为0,就可以得到α关于x的函数,然后再代入拉格朗日函数就变成:

max W(α) = L(x(α), α)

       这时候,带等式约束的优化问题就变成只有一个变量α(多个约束条件就是向量)的优化问题,这时候的求解就很简单了。同样是求导另其等于0,解出α即可。需要注意的是,我们把原始的问题叫做primal problem,转换后的形式叫做dual problem。需要注意的是,原始问题是最小化,转化为对偶问题后就变成了求最大值了。对于不等式约束,其实是同样的操作。简单地来说,通过给每一个约束条件加上一个 Lagrange multiplier(拉格朗日乘子),我们可以将约束条件融和到目标函数里去,这样求解优化问题就会更加容易。(这里其实涉及到很多蛮有趣的东西的,大家可以参考更多的博文)

本文选自于 http://www.mamicode.com/info-detail-506922.html 感谢原作者

 

Leave a Reply

Your email address will not be published. Required fields are marked *