不等式约束条件下求极值2| 学习笔记

开发者学堂课程【机器学习算法 ：不等式约束条件下求极值2】学习笔记，与课程紧密联系，让用户快速学习知识。

课程地址：https://developer.aliyun.com/learning/course/535/detail/7265

不等式约束条件下求极值2

内容介绍

一、不等式约束条件求极值

二、KKT 条件

三、不等式约束条件下求极值详细过程

一、不等式约束条件求极值

对拉格朗日乘子法进行推广，使得其不但能对等式约束进行求极值，还能对小于等于的不等式求极值（如果是大于等于要想办法将其转化成小于等于），即 KKT 条件(Karush-Kuhn-Tucker)。简单讲，只要满足 KKT 条件，就可以构造对应的拉格朗日函数L，求出极值所在的位置。

hi（x）其中的i存在意义是有可能有多个约束条件。同理k也是相同意义，可以有多个不等值约束条件。若满足 KKT

条件就可以构造拉格朗日函数。

二、KKT 条件

KKT 条件(Karush-Kuhn-Tucker):用来判断一个解是否属于一个非线性优化问题的最优解，主要是用于带有不等式约束条件求最优解的情况，利用 KKT 条件，把不等式约束转化为等式约束，然后再把约束条件想办法加到目标函数中，利用求导的方法求出极值。

KKT 条件主要包括：

1. l 对 x 求偏导，如果 x 所在的值，就是所求的最优值，那么这个式子等于0,对拉格朗日函数取极值时候带来的一个必要条件.

2. 求出满足极值的 x，他的等式约束为0,原有约束

3. g（x）≤0，原有约束

4. ≠0，等式约束系数

5. ≥0，不等式约束系数

6. g（x）=0，互补松弛条件，意思为二者结合在一起，会比单独要求其中一个条件松弛一些，只要其中一个等于0就可以了。

三、不等式约束条件下求极值详细过程

当全局极值落在不等式约束内时，实际上不等式约束等于没有效果，和无约束求极值是一样的。如果全局极值不满足不等式约束时，则符合条件的极值会出现在不等式约束的边界上。

1. 若中间黑色点是我们想要的极值点，白色部分是满足约束条件的区域，如果实际全局极值就落在约束条件中，就不会对求极值产生任何影响，极值满足约束条件。

2. 如果真正的极值不满足约束条件，那么要求的极值就是一个新的值，这个新的值肯定不如原来极值好，不是全局来看最优，但是是在满足约束条件下的最有值了。通常极值会出现在不等式约束的边界上。

本例中不等式约束的条件图示如下：

1. 本例不等式约束 x4<C，当 c 值较大时，极值有可能本来就满足约束条件，没影响。

2. 当 C 值较小时，白色区域变小了，有可能原来全局极值不在约束范围内，这时就对求极值有影响，需要求边界上满足当前约束条件的极值 。

回归本例：

KKT 条件为：

接下来只需要解 KKT 条件组成的方程组即可：

由①得到：2x1+ =0、2x2+ =0、2x3+ =0、2x4+ + =0，由于 x4 多了一项不等式约束条件，所以多加一个 。整理得到⑦。

代入到②后，再带到⑦中，再带到③

得到结果并整理得到

C 取值不同，极值的求法不同，所以需要对 C 进行判断，首先将 c 分成三段。

第一种情况会得出-C- <0,利用 KKT 条件求解。

第二种情况会得出-C- =0,利用 KKT 条件求解。

第三种情况会得出-C- >0,利用 KKT 条件求解。