拉格朗日乘数法中KKT条件的合理性

目标KKT条件是什么开始证明参考文献

目标

在使用拉格朗日乘数法进行优化求解的时候，会用到通过求解原始问题的对偶问题，来求得原始问题的解。在KKT条件的限制下，对偶问题的解同时也是原始问题的解。即目标是为了证明这个问题。

KKT条件是什么

假设原始待优化问题为： $minf(x)$ $s.t.g_k(x)\le 0(k=1,2,...,m)$

拉格朗日函数为： $L(x,u)=f(x)+{\sum }_{k=1}{u}_k{g}_k(x)$

上式对应的KKT条件为： $$\{\begin{array}{l}\nabla f(x)+{\sum }_{k=1}{u}_k\nabla g_k(x)=0\\ u_k{g}_k(x)=0(k=1,2,...,m)\\ g_k(x)\le 0\\ u_k\ge 0\end{array}$$

开始证明

要证明的目标公式，在极值点$x^{\ast }$处有： $\underset{x}{\min }\underset{u}{\max }L(x,u)=\underset{u}{\max }\underset{x}{\min }L(x,u)=\underset{x}{\min }f(x)=f(x^{\ast })$

证明 $\underset{x}{\min }\underset{u}{\max }L(x,u)=\underset{x}{\min }f(x)$

$\because u_k\ge 0g_k(x)\le 0==>u_k{g}_k(x)\le 0$ $\therefore \underset{u}{\max }L(x,u)=f(x)$ $\therefore \underset{x}{\min }\underset{u}{\max }L(x,u)=\underset{x}{\min }f(x)$

证明$\underset{u}{\max }\underset{x}{\min }L(x,u)=\underset{x}{\min }f(x)$

$\underset{u}{\max }\underset{x}{\min }L(x,u)=\underset{u}{\max }[\underset{x}{\min }f(x)+\underset{x}{\min }ug(x)]$ $=\underset{u}{\max }\underset{x}{\min }f(x)+\underset{u}{\max }\underset{x}{\min }ug(x)$ $=\underset{x}{\min }f(x)+\underset{u}{\max }\underset{x}{\min }ug(x)$ # 因为$f(x)$与$u$无关

$\because u_k\ge 0g_k(x)\le 0$ $\therefore$ $$\underset{x}{\min }ug(x)=\{\begin{array}{ll}0& ifu=0org(x)=0\\ -\infty & ifu>0andg(x)<0\end{array}$$

$\therefore \underset{u}{\max }\underset{x}{\min }L(x,u)=\underset{x}{\min }f(x)+\underset{u}{\max }\underset{x}{\min }ug(x)=\underset{x}{\min }f(x)$

$\therefore \underset{x}{\min }\underset{u}{\max }L(x,u)=\underset{u}{\max }\underset{x}{\min }L(x,u)$

总结 从上面证明可知，在KKT条件成立的情况下，原问题的解，对偶问题的解是相同的 在极值点处，该点既是拉格朗日函数的极值点，又是原问题的极值点。

参考文献

[Math & Algorithm] 拉格朗日乘数法