简单介绍拉格朗日和KKT条件。
拉格朗日对偶
优化目标：
对应的拉格朗日函数：$L(\mathrm x, \alpha, \beta)_{\alpha \ge 0} = f(\mathrm x) + \alpha_i h_i(\mathrm x) + \beta_j g_j(\mathrm x)$
考虑$\Theta_P = \max \limits_{\alpha, \beta} L(\mathrm x, \alpha, \beta)$，(关于$\mathrm x$的函数)可以推出：
所以原优化目标可变为$\min \limits_{\mathrm x} \Theta_P$,设其最优值存在且为$p^*$,
考虑对偶形式：$\Theta_D = \min \limits_{\mathrm x} L(\mathrm x, \alpha, \beta) $,求其最大值,$\max \limits_{\alpha, \beta} \Theta_D$设其最优值存在且为$d^*$,
可以很容易证明:$d^* \le p^*$,这就是弱对偶条件，当$f(\mathrm x)$为凸函数，约束为仿射函数,且存在一点严格可行时，取等号，称为强对偶条件。
证明$d^* \le p^*$：
所以$\max \Theta_D \le \min \Theta_P$,即$d^* \le p^*$。
KKT条件
一般是必要条件，当$f(\mathrm x)$为凸函数，约束为仿射函数时,KKT条件为充要条件。
最优点满足：