KKT条件的推导

KKT条件第一项是说最优点必须满足所有等式及不等式限制条件，也就是说最优点必须是一个可行解，这一点自然是毋庸置疑的。第二项表明在最优点，必须是和的线性组合，和都叫做拉格朗日乘子。所不同的是不等式限制条件有方向性，所以每一个都必须大于或等于零，而等式限制条件没有方向性，所以没有符号的限制，其符号要视等式限制条件的写法而定。设想我们优化如下的目标函数：我们把这个目标函数称为原函数构造该函数的对偶函数如下：假设是原函数的一个可行点（满足原函数的约束），是对偶函数的一个可行点，因为，所以；同理。因此，我们有，对于任意的满足原函数约束的和满足对偶函数约束的有：记为原函数的一个最优点，最优值为；为对偶函数的一个最优点，最优值为。我们有：(weakduality)如果能够使得成立，则称strongduality成立，即现在假设strongduality能够成立，并且假设是原函数的最优解，为对偶函数的一个最优点，那么第一个等式是strongduality，第二行等式是对偶函数的定义，第三行不等式是inf的定义，第四行不等式是因为。s.t.是subjectto（suchthat）的缩写，受约束的意思。按中文习惯可以翻译成：使得...满足...（约束条件）因此，我们有因为对每个，所以有(Complementaryslackness)因为是使得最小的点，（注意上面的第三行等式成立）所以关于的导数在处为0，即：综上所述我们得到了的条件：