学习笔记|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
- 点赞
- 收藏
- 关注作者
评论(0)