拉格朗日对偶性
在约束最优化问题中，常用拉格朗日对偶性将原始问题转换为对偶问题求解。
广义拉格朗日函数
称最优化问题
$\begin{equation} \begin{array}{lcl} \min\limits_{x\in R^n} f(x)\\ \begin{aligned} \text{s.t.}\;\;&c_i(x) \le 0,\;\;i=1,2,…,k \\ &h_j(x)=0,\;\;j=1,2,…,l \end{aligned} \end{array} \end {equation}$
为原始最优化问题。使用以上优化问题构造广义拉格朗日函数：
$L(x,\alpha,\beta) = f(x)+\sum\limits_{i=1}^k\alpha_ic_i(x)+\sum\limits_{j=1}^l\beta_jh_j(x)$
其中$\alpha_i\ge 0,\beta_j\in R$是拉格朗日乘子。可以发现，对于违反原始问题约束的$x$，即存在某个$c_i(x)>0$，或某个$h_j(x)\ne 0$，有：
$\max\limits_{\alpha\ge 0,\beta}L(x,\alpha,\beta) = +\infty$
因此有：
$\begin{equation} \max\limits_{\alpha\ge 0, \beta}L(x,\alpha,\beta) = \left\{ \begin{aligned} &f(x),\;\;x满足原始条件约束\\ &+\infty,\;\;else \end{aligned} \right. \end {equation}$
因此原始问题的最优值可以表示为：
$p^* = \min\limits_{x}\max\limits_{\alpha\ge 0 , \beta}L(x,\alpha,\beta)$
从而将约束条件与待优化问题结合到了一起，称为广义拉格朗日函数的极小极大问题。
对偶问题以及KKT条件
对偶问题
将极小极大交换一下，得到
$d^* = \max\limits_{\alpha\ge 0 , \beta}\min\limits_{x}L(x,\alpha,\beta)$
即为原始问题的对偶问题的最优值。对偶问题转换为带条件的形式就是：
$\begin{aligned} &\max\limits_{\alpha,\beta}\min\limits_{x} L(x,\alpha,\beta)\\ &\;\text{s.t.}\;\;\alpha_i\ge 0, \;\; i=1,2,…,k \\ \end{aligned}$
如果原始问题与对偶问题都有最优值，$p^*$和$d^*$，则：
$d^*= \max\limits_{\alpha\ge 0 , \beta}\min\limits_{x}L(x,\alpha,\beta)\le \min\limits_{x}\max\limits_{\alpha\ge 0 , \beta}L(x,\alpha,\beta)= p^*$
这是因为，对于任意$x,\alpha,\beta$，有：
$\min\limits_{x}L(x,\alpha,\beta)\le L(x,\alpha,\beta)\le\max\limits_{\alpha\ge 0 , \beta}L(x,\alpha,\beta)$
也就是左边关于$\alpha,\beta$的函数，总是小于等于右边关于$x$的函数。所以有$d^*\le p^*$。
KKT条件
某些情况下，对偶问题与原始问题有相等的最优值，即$d^* = p^*$，这时解对偶问题可以替代原始问题，条件如下：
1、$f(x)$和$c_i(x)$是凸函数；
2、$h_j(x)$是仿射函数，即一次函数；
3、不等式约束$c_i(x)$是严格可行的，即存在$x$，对所有$i$有$c_i(x)<0$。如果不存在这样的$x$的话，实际上就是等式约束了。这是因为，每个$x$都会使某个不等式约束取等号，也就可以仅使用等式约束来表示这些$x$了。
此时有：
$p^*=d^*=L(x^*,\alpha^*,\beta^*)$
且算出$x^*,\alpha^*,\beta^*$的充要条件是（KKT条件）：
$\left\{ \begin{aligned} &\nabla_xL(x^*,\alpha^*,\beta^*) = 0 \\ &\alpha^*c_i(x^*) = 0, \;\; i=1,2,…,k \\ &c_i(x^*) \le 0, \;\; i=1,2,…,k \\ &\alpha_i^*\ge 0, \;\; i=1,2,…,k \\ &h_j(x^*) = 0, \;\; i=1,2,…,l \\ \end{aligned} \right.$
直观理解
上图显示了优化的一个情况。等高线表示的是待优化函数$f(x)$（$x$二维），越向中心，值越小，是个标准的凸函数。红圈表示不等式约束（内部），是个凸函数。蓝线表示等式约束（线上），是仿射函数。则$x$可取的值在红圈与其内部的蓝线上。可观察有如下几个符合KKT条件的事实：
1、三个白色箭头分别表示三个函数的梯度方向，此时有三个梯度的加权矢量和为0，与KKT条件中的1式吻合。
2、因为最优点在红圈上，因此不等式约束取等为0，有2式。
3、3式和5式是原本的约束条件。
4、观察三个梯度的方向，因为$f(x)$的方向不能改变（1式梯度前没系数），所以为了矢量和为0，$\alpha$必须大于0。而由于等式约束的仿射函数取反后约束不变，而梯度方向却变反了，因此$\beta$没有正负的限制。
