拉格朗日乘法和KKT条件

千秋摄于黄山

最近看了 《最优化理论与方法》, 学习了常见的优化问题以及解决方法。同时，之前学习 SVM 时，对拉格朗日乘法以及 KKT 条件有一些疑问，这里做一下学习笔记，便于后面复习和理解！

Notion: 同时参考了网上找到的一个PPT（见附件），觉得写的相当棒！

主要设计四种优化问题：

1. 无约束优化
2. 等式约束优化
3. 不等式约束优化
4. 等式和不等式约束优化

讨论的对象是优化问题的标准形式:

公式（1）：优化问题的标准形式

1. 无约束优化

无约束优化的标准形式为：

公式（2）：无约束优化的标准形式

假设f(x)在X上处处可导，则局部最优点 的充分必要条件为：
。
公式（3）

证明

将f(x)使用泰勒公式在处展开：

公式（4）

充分条件

必要条件

1. 若f(x) 在 处可导且取得局部最小值，则有

证明，使用反证法：

2. 若f(x) 在 处可导且取得局部最小值，且，则

证明：

则必要条件为:

2. 等式约束优化

其实一般有两种做法，拉格朗日乘法和消元法，但是消元法遇到等式约束较多时比较难以处理。因此，使用拉格朗日乘法较为方便。

转化为拉格朗日乘法:

以一个具体的例子为例：

没有加等式约束时，它的最小值时不存在的（无穷小）
而加了等式约束之后，假设当前点为, 下一点为 , 则需要有：

要保证:,

要保证: 要求：

同样由几何意义可知，

即，f(x) 取得极值的地方为: 约束g(x) = 0 与 f(x) = C （等值线）相切的地方，如上图M1,M2。
此时有：

因此可以，构造 , 并要求：

另一种理解，KKT条件

构造 , 假设在 处取得最大值，存在两种情况：

1. x 满足 , 此时
2. x 不满足 , 此时 存在

而，

此时要求条件为：

3. 不等式约束

假设局部最小值点为 , 此时存在两种情况：

在约束条件之内

此时，处理方式与无约束问题一样

在约束条件之外

此时由几何关系可知，局部最小值位于g(x) = 0 与 f(x) = C 的切线上，由等式约束可知，此时有

综合以上有:

拉格朗日乘法:

以上便是KKT条件

另一个直观的解释为:

构造 , 假设在 处取得最大值，存在两种情况：

1. x 满足 , 此时
2. x 满足 , 此时
3. x 不满足 , 此时

而，

此时要求条件为：

4. 等式和不等式约束

此时，是2，3 的综合情况，只需要构造拉格朗日乘法

若满足此条件,则有：

5. 附件📎

KKT.pdf