KKT条件

已经解决的在等式约束条件下的求函数极值的问题,那不等式约束条件下,应该如何解决呢?这就需要引出KKT条件(Karush-Kuhn-Tucker Conditions),它是在满足一些有规则的条件下,一个非线性规划问题能有最优化解法的一个必要和充分条件。

考虑以下非线性最优化问题12:,含有 \(m\) 个不等式约束,\(l\) 个等式约束:

\[\operatorname*{min}_{x}f(x) \qquad s.t. \; g_i(x) \leqslant 0,\; h_j(x) =0\]

必要条件

假设 \(f,g_i,h_j\) 三个函数为实数集映射,再者,他们都在 \(x^\ast\) 这点连续可微 ,如果 \(x^\ast\) 是一个局部极值,那么将会存在一组称为乘子的常数 \(\lambda \geqslant 0,\mu_i \geqslant0, \nu_j\) , 令

\[ \lambda + \sum_{i=1}^m \mu_i + \sum_{j=1}^l |\nu_i| \gt 0, \\ \lambda \nabla f(x^\ast) + \sum_{i=1}^m \mu_i \nabla g_i(x^\ast) + \sum_{j=1}^l \nu_i \nabla h_j(x^\ast) = 0, \\ \mu_i g_i(x^\ast) =0 \; \text{for all} \; i=1,\ldots,m \]

这里有一些正则性条件或约束规范能保证解法不是退化的(比如\(\lambda\)为0 )。

充分条件

假设 \(f,g_i\)凸函数\(h_j\) 函数是仿射函数(平移变换),假设有一个可行点 \(x^\ast\),如果有常数 \(\mu_i \geqslant 0\)\(\nu_j\) 满足

\[ \nabla f(x^\ast) + \sum_{i=1}^m \mu_i \nabla g_i(x^\ast) + \sum_{j=1}^l \nu_i \nabla h_j(x^\ast) = 0 \\ \mu_i g_i(x^\ast) =0 \; \text{for all} \; i=1,\ldots,m \]

那么 \(x^\ast\) 就是全局极小值

谢谢鼓励,欢迎留言反馈
0%
Title - Artist
0:00