前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BAT面试题46:解释对偶这个概念

BAT面试题46:解释对偶这个概念

作者头像
double
发布2019-03-07 10:31:59
9570
发布2019-03-07 10:31:59
举报
文章被收录于专栏:算法channel

精彩内容

一个优化问题可以从两个角度进行考察,一个是primal 问题,一个是dual 问题,就是对偶问题。

一般情况下对偶问题给出主问题最优值的下界,在强对偶性成立的情况下由对偶问题可以得到主问题的最优下界,对偶问题是凸优化问题,可以进行较好的求解。

SVM中就是将Primal问题转换为dual问题进行求解,从而进一步引入核函数的思想。

补充

每个线性规划问题都有一个与之对应的对偶问题。对偶问题是以原问题的约束条件和目标函数为基础构造而来的。对偶问题也是一个线性规划问题,因此可以采用单纯形法求解。

对偶问题的最优解也可以通过原问题的最优解得到,反之亦然。而且,在某些情况下,利用对偶理论求解线性规划问题更为简单,而且有助于深入了解待求问题的本质。

对偶线性规划的经济背景是:若原问题是利用有限资源安排最优生产方案,以获得最大总产值的线性规划问题,则它的对偶问题就是在相同资源的条件下,正确估计资源的使用价值,以达到支付最少费用的线性规划问题。简言之,若原问题为求解资源的最优配置问题,则对偶问题就是求解估价资源的使用价值问题。

参考:

https://baike.baidu.com

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-02-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员郭震zhenguo 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档