美文网首页
KKT条件

KKT条件

作者: 热爱生活的大川 | 来源:发表于2020-11-18 17:19 被阅读0次

定义

优化问题：
\begin{aligned} & \max{f(x)} \\ s.t.\quad & h_j(x)=0, \quad j=1,2...q \\ & g_i(x) \le 0, \quad i=1,2,...p \end{aligned}
的解x^*满足如下条件
\begin{aligned} & \nabla{f(x^*)}=\sum\lambda_j\nabla{h_j(x^*)}+\sum\mu_i\nabla{g_i(x^*)} \\ & \mu_i \ge 0,\quad \mu_ig_i(x^*) = 0 \end{aligned}
该条件即KKT条件。

解释

无约束条件时，局部极值点在梯度为0时取得。例如，当x^*为局部极大值点，则x^*在任一方向移动（一个任意小距离）时函数值应不增加。

有约束条件时，局部极值点的梯度需满足在可行方向内无分量。例如，当x^*为约束条件下的局部极大值点，则x^*在可行域内任一方向移动（一个任意小距离）时函数值应不增加。

总可行方向是各个约束下可行方向的交集，于是各个约束不可行方向的并集就在总可行方向上无分量。

  1. 当h_j(x^*)=0时，不可行方向为\lambda_j\nabla{h_j(x^*)}；
  2. 当g_i(x^*) \le 0时，不可行方向为\mu_i\nabla{g_i(x^*)}，\mu_i \ge 0，\mu_ig_i(x^*)=0。可由以下两种情况整合而来。
    • 当g_i(x^*)=0时，不可行方向为\mu_i\nabla{g_i(x^*)}， \mu_i \ge 0；
    • 当g_i(x^*)<0时，不可行方向为\emptyset，可表示为\mu_i\nabla{g_i(x^*)}， \mu_i=0。

于是\nabla{f(x^*)}可表示为以上两种情况的线性组合。因为是或的关系，各个不可行方向上的分量可以是0（"或"表示只要某一个不为0，就已经满足可行方向无分量；当然，全为0表示f本身取到了极值点，任意方向无分量）。

相关文章

  • KKT条件

    定义 优化问题：的解满足如下条件该条件即KKT条件。 解释 无约束条件时，局部极值点在梯度为0时取得。例如，当为局...

  • 机器学习面试001—支持向量机SVM

    1. 关于min和max交换位置满足的 d* <= p* 的条件并不是KKT条件 Ans：这里并非是KKT条件，要...

  • 机器学习——拉格朗日对偶

    拉格朗日对偶与凸优化、拉格朗日乘子、KKT条件有着密切的联系，KKT条件可以通过朗格朗日对偶推到得到。 ...

  • 给大家介绍两款超级牛逼的算法！SVM · SMO算法！和牛逼也很

    KKT 条件 先来看如何选取参数。在 SMO 算法中，我们是依次选取参数的： 选出违反 KKT 条件最严重的样本点...

  • kkt条件的推导思路以及八卦

    kkt条件的推导思路以及八卦 KKT条件是用来判断一个解是否属于一个非线性最优化问题的。 这个条件也是推导出来的 ...

  • 03 SVM - KKT条件

    02 SVM - 拉格朗日乘子法 回顾上章，原始问题与对偶问题的关系： 结论：1、对偶问题小于等于原始问题。2、当...

  • 超级简单KKT条件

    由拉格朗日可知,当我们优化有约束问题的时候，我们看最简单的例子，只有一个g(x)的时候，我们要优化的是 第一种情况...

  • 拉格朗日乘子法与KKT条件

    在求解最优化问题中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tu...

  • 拉格朗日乘子法和 KKT 条件

        这篇博文中直观上讲解了拉格朗日乘子法和 KKT 条件，对偶问题等内容。    首先从无约束的优化问题讲起，...

  • 拉格朗日乘子法和KKT条件

    拉格朗日乘子法 要解决的问题 拉格朗日乘子法要解决的就是有等式限制条件的凸优化问题。形式如下： 求解方式 例如： ...

网友评论

      本文标题：KKT条件

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|KKT条件|投稿指南|网站地图|RSS订阅|排版工具|手机版

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

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

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

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

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