拉格朗日乘子法以及KKT条件

拉格朗日乘子法以及KKT条件

拉格朗日乘子法是一种优化算法,主要用来解决约束优化问题。他的主要思想是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有n+k个变量的无约束优化问题。

其中,利用拉格朗日乘子法主要解决的问题为:

等式的约束条件和不等式的条件约束。

 

拉格朗日乘子的背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。

等约束条件的解决方法不在赘述。

对于非等约束条件的求解,需要满足KKT条件才能进行求解。下面对于KKT条件进行分析。

不等式约束优化问题:

<span>拉格朗日乘子法以及KKT条件</span>

得到拉格朗日乘子法的求解方程:

<span>拉格朗日乘子法以及KKT条件</span>

给出KKT条件:

<span>拉格朗日乘子法以及KKT条件</span>

 

实际上,为什么要给出KKT条件?这里涉及到对偶问题。

我们引入拉格朗日函数L(x,α,β)将有约束的优化问题转换为无约束的优化问题,然后对原问题的参数求导,获得使拉格朗日函数最小的拉格朗日对偶函数g(α,β),最后使得对偶函数最大的问题则成为原问题的对偶问题。(对偶函数给出了主问题最优解的下界。那么下界最大是什么,这就是主问题的对偶问题)

因此对于上面拉格朗日乘子法问题的描述表达为:

<span>拉格朗日乘子法以及KKT条件</span>

但其实是仍然个很难解决的问题,因为我们要先解决不等式约束的max问题,然后再在x上求最小值。怎么办呢?如果能把顺序换一下,先解决关于x的最小值,在解决关于α、β的不等式约束问题就好了。即,

<span>拉格朗日乘子法以及KKT条件</span>

假设原问题为p,对偶问题为d,事实上,p和d并不完全相等,此处含有一个性质:弱对偶性

即:

<span>拉格朗日乘子法以及KKT条件</span>

而他两个的差即为对偶间隙

解释:大家想一下,函数L中最大值中最小的一个总比最小值中最大的那一个要大,也就是对偶问题提供了原问题最优值的一个下界。

但是大家想,我们是想通过对偶问题求解原问题的最优解,所以只有当二者相等时才可能将原问题转化成对偶问题进行求解。当然,当满足一定条件的情况下,便有p=d。而这个条件便是 slater条件和KTT条件

在凸优化理论中,有一个Slater定理,当这个定理满足,结合KKT条件,那么对偶间隙就会消失,就是强对偶性成立。

<span>拉格朗日乘子法以及KKT条件</span>

 

其中对于KKT条件的KKT因子为什么需要大于等于0不太好理解。

 

 <span>拉格朗日乘子法以及KKT条件</span>

我的理解:如上,只有当大于等于0的时候,L的取值才能有最大值,即:

<span>拉格朗日乘子法以及KKT条件</span>这一步才有值。

当然这个只是我个人的理解吧,理论上详细的证明参考《数值优化》-Jorge Nocedal  第12章

当然它上面的公式:

<span>拉格朗日乘子法以及KKT条件</span>

<span>拉格朗日乘子法以及KKT条件</span>

都是基于

<span>拉格朗日乘子法以及KKT条件</span>

这样一个假设,不过我们一般假设的约束条件是小于等于0,所以看上去形式有点不一样,其实道理都一样的。

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119460.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • jrtplib for android,Jrtplib Android平台编译

    jrtplib for android,Jrtplib Android平台编译??jrtplib库使用C++语言实现,封装了RTP、RTCP协议的内容,可用于发送RTP数据包和RTCP数据包。RTP、RTCP协议本身不是很复杂的协议,使用该库可以免去实现协议的细节,但是如果要用好该库,最好对RTP、RTCP协议有一个比较清晰的了解。??本文介绍如何在AndroidStudio中通过编写CMakeList.txt文件,将下载好的jlibrtp库编译成动态库。此处关键…

  • spssχ2检验_案例实践:SPSS分层卡方检验[通俗易懂]

    spssχ2检验_案例实践:SPSS分层卡方检验[通俗易懂]两个分类变量卡方检验用着爽,但有一点需要强调一下,要不要控制混杂因素的影响,也许在混杂的影响下,卡方检验的结果并不是原先的那个样子,而我们陷入自我欺骗陷阱还不自知。分层卡方检验,则是在普通卡方检验(一般是2×2)基础上增加一个控制混杂的分层变量,让我们的研究更加现实,考虑到多方面的因素,实际上已经算是一种多因素的分析手段了。案例介绍文彤老师SPSS基础教程上有一个不错的案例。某研究调查了口服避孕药…

  • linux卸载nps,Linux NPS服务部署

    linux卸载nps,Linux NPS服务部署一.安装NFS服务rpm-qa|grepnfsrpm-qa|greprpcbindyuminstallnfs-utils#如果检查的结果是没有安装,则使用该命令安装/etc/init.d/rpcbindstart/etc/init.d/nfsstart二.NFS的软件结构1.主要配置文件:/etc/exports这个档案就是NFS的主要配置文件了!…

  • 金山词霸2010牛津旗舰激活成功教程版【最完美的】的使用方案[通俗易懂]

    金山词霸2010牛津旗舰激活成功教程版【最完美的】的使用方案[通俗易懂]【可更新一年】金山词霸2010牛津旗舰激活成功教程版【最完美的】的使用方案激活成功教程的详细操作过程1.下载金山词霸2010牛津旗舰版官方版本。[url]http://download.iciba.com/Pw2010_Ultimate/PowerWord2010Oxf_Ult

  • mybatis和hibernate的以及jpa区别_hibernate sql

    mybatis和hibernate的以及jpa区别_hibernate sql1、概述hibernate和mybatis是当前流行的ORM框架。hibernate对数据库结构提供了较为完整的封装。mybatis主要着力点在于java对象与SQL之间的映射关系。2、Hibernate理解Hibernate是一个开放源代码的对象关系映射框架,它对JDBC进行了非常轻量级的对象封装,它将java对象与数据库表建立映射关系,是一个全自动的orm框架。Hibernate可以自动生成SQ

  • 智能优化算法经验谈[通俗易懂]

    智能优化算法经验谈[通俗易懂]智能优化算法、全局优化、元启发式算法、差分进化算法、遗传算法、模拟退火算法、蚁群算法、粒子群算法

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号