美文网首页
拉格朗日对偶性

拉格朗日对偶性

作者: LuckilyHaveYou | 来源:发表于2020-06-16 15:02 被阅读0次
  • 原始问题与对偶问题

    • 原始问题：
      求\underset{x\in R^n}{min}f(x)，
      s.t.c_i(x)\leq 0,i=1,2,..k
      h_j(x)=0,j=1,2..l
      拉格朗日函数
      L(x,\alpha,\beta)=f(x)+\sum_i^k\alpha_ic_i(x)+\sum_j^l\beta_jh_j(x)
      设\theta_P(x)=\underset{\alpha,\beta:\alpha\geq0}{max}L(x,\alpha,\beta)
      如果c_i(x)与h_i(x)不满足前面的条件约束，则上式就会变成正无穷
      \theta_P(x)=\begin{cases} f(x) & \\ +Inf \end{cases}
      然后再考虑最小化问题\underset{x}{min}\theta_P(x)
      则上式与f(x)极小化是等价的。这个就是极小极大问题

    • 对偶问题:

      • \theta_D(\alpha,\beta)=\underset{x}{min}L(x,\alpha,\beta)
        然后再考虑极大
        \underset{\alpha,\beta}{max}\theta_D(\alpha,\beta)
        这个就是极大极小问题

    • 原始问题与对偶问题的关系
      定理1：如果两个问题都有最优值，对偶问题会小于等于原始问题
      推论：如果可以找到x^*,\alpha^*,\beta^*是原始与对偶问题的最优解，且两者相等，则分别是原始问题与对偶问题的最优解。这样理解，因为原始问题会大于等于对偶问题，则在取等号时取到了最小值，则是最优解，反过来一样，对偶问题是找最大值。
      定理2：如果f(x)与c(x)是凸函数，h(x)是仿射函数，并且c(x)是严格可行的（存在x，使得对于所有的i有c(x)<0），则推论中的解是存在的。
      定理3:求最优解的充分必要条件是x^*,\alpha^*,\beta^*满足KKT条件
      \begin{aligned} \nabla_xL(x^*,\alpha^*,\beta^*)=0 \\ \alpha_i^*c_i(x^*)=0 \\ c_i(x^*)\leq0 \\ \alpha_i^*\geq0 \\ h_j(x^*)=0 \end{aligned}

去github

相关文章

网友评论

      本文标题：拉格朗日对偶性

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|拉格朗日对偶性|投稿指南|网站地图|RSS订阅|排版工具|手机版

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

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

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

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

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