美文网首页
对偶问题推导

对偶问题推导

作者: Greyish | 来源:发表于2020-04-13 23:27 被阅读0次

原问题和对偶问题

每一个线性优化问题，都可以表示为一个对偶问题。

原问题：\begin{equation} \begin{aligned} \text { Minimize } z &=\mathbf{c}^{\mathrm{T}} \mathbf{x} \\ \text {s.t.} & \mathbf{A x} \geq \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \end{aligned} \end{equation}          

对偶问题：\begin{equation} \begin{aligned} \text {Maxmize } z &=\mathbf{b}^{\mathbf{T}} \mathbf{y} \\ \text {s.t.} & \mathbf{A^{T} x} \leq \mathbf{c} \\ & \mathbf{y} \geq \mathbf{0} \end{aligned} \end{equation}

原问题不等式（Ax \geq b）的数量为对偶问题中变量的数量。

原问题变量(x \geq 0)的数量为对偶问题中不等式的数量。

如何推导？

原问题和对偶问题推导对应表

首先要明确上表中variable和constraints的区别，拿上面提到的例子来讲，原问题不等式（Ax \geq b）即为不等式约束，原问题变量（x \geq 0）即为变量的约束，两者都是约束，但是分为不等式约束和变量约束。

推导对偶问题时，首先对原问题的每一个不等式约束列写对偶问题的变量，然后对原问题的每一个变量列写对偶问题的不等式约束，该约束的正负号（或等号）与该变量相关。最后，对原问题的每一个非变量约束列写对偶问题的变量约束，该约束的正负号（或等号）与该约束相关。

相关文章

  • 对偶问题推导

    原问题和对偶问题 每一个线性优化问题，都可以表示为一个对偶问题。 原问题： 对偶问题： 原问题不等式（）的...

  • 算法基本功：SVM part4 SVM与对偶问题 2019-03

    上章讲了对偶问题一般情况，引入到SVM中。 SVM 对偶问题表达式推导： 由上一章节知道： # 直白讲即： 原问题...

  • 2019-01-25

    写出 svm 原始问题转换至其对偶问题的数学推导过程： 1 导包： from sklearn import svm...

  • 2019-01-24

    写出 svm 原始问题转换至其对偶问题的数学推导过程： 1 对于训练样本是非线性可分的 : 可将样本从原始空间映射...

  • 多元函数的方向导数（n元函数的方向导数）

    机器学习中的支持向量机（SVM）的推导涉及到了一个重要数学问题：约束最优化问题（对偶问题、拉格朗日、凸函数等）。在...

  • 2019-01-23

    写出 svm 原始问题转换至其对偶问题的数学推导过程： 1 基于训练集在样本空间找到一个超平面 将不同类别的样本分...

  • 对偶问题

  • SVM原问题与对偶问题

    序 本次记录：原问题与对偶问题的关系；强对偶与弱对偶；引入KKT的原因； 原问题与对偶问题的关系 定义一个原问题：...

  • 线性规划与单纯形法

    对偶问题的基本性质 无界性：原问题为无界解，则其对偶问题无可行解 对偶定理：若原问题有最优解，那么对偶问题也有最优...

  • 拉格朗日对偶性

    在约束最优化问题中，拉格朗日对偶性将原始问题转换为对偶问题，通过解对偶问题而得到原始问题的解。该方法在统计学习方法...

网友评论

      本文标题：对偶问题推导

      本文链接：https://www.haomeiwen.com/subject/peaomhtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|对偶问题推导|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！