Karush-Kuhn-Tucker(KKT) Conditions

定理

对于问题
- $min_{x}f(x)$
- $s.t. h_{i}(x)\leq0,i=1,...,m;l_{i}(x)=0,j=1,...,r$
如果该问题不是degenerate，那么最优解满足如下条件
- stationarity: $0\in\partial_{x}\left[f(x)+\sum_{i=1}^{m}u_{i}h_{i}(x)+\sum_{j=1}^{r}v_{i}l_{i}(x)\right]$
- complementary slackness: $u_{i}\cdot h_{i}=0,i=1,...,m$
- primal feasibility: $h_{i}(x)\leq0,l_{j}=0;i=1,...,m;j=1,...,r$
- dual feasibility: $u_{i}\geq0,i=1,...,m$

用途

通过构造KKT条件，如果条件中没有不等式，那就有机会直接求解优化问题的解，比如下图这种情况，我们只需要求解下面的线性方程组的解即可得到优化结果
可以拿来度量约束优化数值算法的解的精度。下面三个值是KKT残差，通过取其中的最大值，使其足够小，就可以得到精度较高的解
- - 不等式约束违背程度
- - 等式约束违背程度
- - 梯度残差

Search

欢迎添加我的微信

闷骚的程序员

Table of Contents