学习笔记|KKT条件与拉格朗日乘子法

举报
darkpard 发表于 2021/11/14 10:11:44 2021/11/14
【摘要】 学习笔记|线性规划的标准化提到了用拉格朗日乘子法求解标准形式的线性规划,实际上拉格朗日乘子法更适用于求解非线性优化问题,而对于线性规划的求解,更加适合用单纯形法求解,不再继续展开。本篇主要讨论传说中的KKT条件与拉格朗日乘子法。KKT条件是Karush[1939],以及Kuhn和Tucker[1951]先后独立发表出來的,是确定某点为极值点的必要条件。在引入KKT条件前,让我们先回到拉格朗日...

学习笔记|线性规划的标准化提到了用拉格朗日乘子法求解标准形式的线性规划,实际上拉格朗日乘子法更适用于求解非线性优化问题,而对于线性规划的求解,更加适合用单纯形法求解,不再继续展开。本篇主要讨论传说中的KKT条件与拉格朗日乘子法。

KKT条件是Karush[1939],以及Kuhn和Tucker[1951]先后独立发表出來的,是确定某点为极值点的必要条件。在引入KKT条件前,让我们先回到拉格朗日乘子法。

1. 拉格朗日乘子法的图形解析

为了便于图形展示,我们以二维优化问题为例。

假设优化目标为

约束条件为

图片

在原优化问题中引入拉格朗日乘子λ,构造拉格朗日函数

通过偏导数法列出求解条件如下

2. KKT条件

假设最优化问题如下:

则KKT条件如下:

可以看到,在单一等式约束下KKT条件与上一节的方程组是一致的。

3. KKT条件推导

3.1. 原可行性与拉格朗日平稳性的推导

首先引入松弛变量(引入方法可参见学习笔记|线性规划的标准化),将原优化问题转化为

3.2. 互补松弛条件的推导

因此,上面的方程组可以进一步改写成:

即互补松弛条件成立。

3.3. 对偶可行性的推导

对偶可行性,即μ,必有μ

3.3.1. 单一不等式约束下对偶可行性的推导

单一不等式约束优化可表述为:

图片(图片来源于参考文献6)

则拉格朗日平稳性为

3.3.2. 对偶可行性的推导

先看两个不等式约束优化问题,它可表述如下:

拉格朗日平稳性为


完整优化问题下,拉格朗日平稳性为

由于向量乘以常数仍为向量、向量的和仍为向量,可以将其转化为两约束来考虑,同样不再赘述。

参考文献

1.https://baike.baidu.com/item/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0%E6%B3%95/8550443?fromtitle=%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E5%AD%90%E6%B3%95&fromid=1946079&fr=aladdin
2.https://baijiahao.baidu.com/s?id=1618344063706450694&wfr=spider&for=pc
3.https://blog.csdn.net/qq_36607894/article/details/89917997
4.https://zhuanlan.zhihu.com/p/26514613
5.https://blog.csdn.net/qq_36607894/article/details/89917997
6.https://blog.csdn.net/qq_36607894/article/details/89922839
7.https://www.cnblogs.com/xinchen1111/p/8804858.html

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。