不等式约束优化type
status
date
slug
summary
tags
category
icon
password
Property
卡罗需-库恩-塔克条件（KKT条件）
含不等式约束的优化问题也可以利用拉格朗日乘子法进行求解
向量表示的一般形式的优化问题：
其中，
对于一个不等式约束 ，如果在 处，那么称该不等式是处的起作用的约束；如果在 处，那么称该不等式是处的不起作用的约束。按惯例，把等式约束当作总是起作用的约束。
设 满足 ，设 为起作用不等式约束下标集
如果向量
是线性无关的，则称是一个正则点。
KKT条件
局部极小点所应该满足的一阶必要条件，也称为卡罗需一库恩一塔克(Karush-Kuhn_Tucker) 条件。
设 ， 是问题的一个正则点和局部极小点，则必然存在，使得以下条件成立：
其中， 为拉格朗日乘子向量， 为KKT乘子向量，向量中的元素分别称为拉格朗日乘子和KKT乘子。
由定理 和，则条件
意味，如果 ，则 。也就是对于所有的 恒成立，即不起作用约束对应的KKT乘子 等于0；其他KKT乘子是非负的，可以等于0或者不等于0。
KKT 定理的几何解释
二维的情况，只包含不等式约束 。图中的点是一个极小点。由于约束 对 是不起作用约束，因此， 。由 KKT 定理可得：
或
， 。图中清楚地看出， 必须是向量 和 的线性组合，且系数必须是正 数。同样的， 从上面式子中也能得到相同的结论 (其中 和 是 KKT 乘子)。
KKT条件是极小点的必要条件，因此，应按照必要条件的使用方式利用KKT条件搜索满足条件的点，并把这些点作为极小点的候选对象。KKT条件由以下5部分组成：
二阶条件
与只包含等式约束的极值问题一样，对于包含不等式约束的极值问题，同样可以给出二阶充分必要条件。
定义矩阵
其中， 是 在点 处的黑塞矩阵， 表示：
表示：
是在处的黑塞矩阵
记
代表由起作用约束所定义曲面的切线空间。
二阶必要条件
设 ， 是一个正则点和局部极小点，则必然存在 ，使得以下条件成立：
- ；
- 对于所有 ，都有 。
记 其中，
二阶充分条件
设 ， 是一个可行点，存在向量 使得
- 对于所有 ，都有
则 是优化问题 的严格局部极小点。