拉格朗日乘子法以及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)


相关推荐

  • C6000系列DSP的EMIFA接口

    C6000系列DSP的EMIFA接口DSP6455的EMIFA模块之前介绍了DSP6455的GPIO和中断部分。今天,继续介绍EMIFA模块。关于C6000系列的GPIO,请参考:C6000系列DSP的GPIO模块关于C6000系列的中断系统,请参考:C6000系列DSP的中断系统——————————————–华丽分割—–

  • 序列化和反序列化的详解[通俗易懂]

    序列化和反序列化的详解[通俗易懂]一、基本概念1、序列化和反序列化的定义:  (1)Java序列化就是指把Java对象转换为字节序列的过程    Java反序列化就是指把字节序列恢复为Java对象的过程。  (2)序列化最重要的作用:在传递和保存对象时.保证对象的完整性和可传递性。对象转换为有序字节流,以便在网络上传输或者保存在本地文件中。    反序列化的最重要的作用:根据字节流中保存的对…

  • 手把手教程——自制ARM仿真器Jlink-OB-072,原来这么简单

    使用的软件:AltiumDesigner使用的硬件:STM32F072C8T6全套设计资料:PCB工程;Jlink固件;Jlink驱动仿真器特点: 支持SWD模式,下载时仅需连接DIO、CLK、GND三个引脚 支持串口TTL 采用Micro_USB接口+延长线的设计,优雅的下载程序和Debug 无外置晶振,降低成本,节省空间 提供全部开发设…

  • php源码 网页聊天_php即时在线网页聊天源码-响应式设计自适应手机端[通俗易懂]

    php源码 网页聊天_php即时在线网页聊天源码-响应式设计自适应手机端[通俗易懂]基于PHPWebSocket即时通讯开发的在线聊天源码,使用高效优雅的Laravel框架进行非通讯部分开发。前台与后台自适应PC与移动端,支持一对多交流,可以自由创建新的房间与解散创建的房间,集成签到功能,等级功能,房间创建者可以对用户进行禁言、拉黑处理,房间可以由房间创建者自由设置进入密码,房间内支持常规的文字消息、表情、支持自定义图片消息、图片可用本地或者图片外链。php环境配置需求P…

  • JScript内置对象Array中元素的删除问题

    JScript内置对象Array中元素的删除问题

  • ups不间断电源介绍_ups不间断电源设备有哪几部分组成

    ups不间断电源介绍_ups不间断电源设备有哪几部分组成本文简单介绍UPS(不间断电源)的相关知识。1概述UPS(UninterruptedPowerSupply),即不间断电源,是将蓄电池与主机相连接,通过主机逆变器等模块电路,将蓄电池中直流(DC,DirectCurrent)电转换成市电交流(AC,AlternatingCurrent)电的系统设备。UPS主要用于给单台计算机、计算机网络系统或其它电力电子设备如电磁阀、压力变送器…

    2022年10月27日

发表回复

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

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