拉格朗日

拉格朗日乘子法是求解约束最优化问题的方法，其通过将原始问题转化为对偶问题来得到原始问题的最优解。SVM，最大熵模型都采用了拉格朗日方法。

原始问题

首先定义 $f(x), c_i(x), h_j(x)$ 是定义在 $R^n$ 上的连续可微函数，考虑下面的约束问题：

$\begin{align} \nonumber \min\limits_{x\in R^n}&f(x)\\ \nonumber \text{ s.t. } & c_i(x)\le 0, i=1,2,...,k\\ \nonumber & h_j(x) = 0, j=1,2,...,l \nonumber \end{align}$

然后我们可以引入拉格朗日函数：

$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\ge0$ 。

现在考虑关于 $L(x, \alpha, \beta)$ 关于 $x$ 的函数：

$\theta_P(x)=\max\limits_{\alpha\ge0;\beta}L(x, \alpha, \beta)=\max\limits_{\alpha\ge0;\beta}f(x)+\sum\limits_{i=1}^k\alpha_ic_i(x)+\sum\limits_{j=1}^l\beta_jh_j(x)$

问题来了，为什么这里是求最大值？

我们可以这么考虑：如果（1）的约束条件都满足了，即 $c_i(x)\le 0, h_j(x)=0$ ，那么当我们对（2）求极大值的时候， $\alpha_i=0$ 必定成立，所以 $\theta_P=f(x)$ 。反之，如果约束条件没有满足，假设存在一个 $c_i(x)>0$ ，那么由于极大值的存在， $\alpha_i\to\infin$ ，那么也就没有解了。所以取最大值是合理的。

然后我们就可以考虑

$\min\limits_x\theta_P(x)=\min\limits_x\max\limits_{\alpha\ge0;\beta}L(x, \alpha, \beta)$

为了表述方便，先假设存在最优值，即

$p^*=\min\limits_x\theta_P(x)$

对偶问题

原始问题是极小极大问题，对偶问题是极大极小问题。定义如下关于 $\alpha, \beta$ 的函数：

$\theta_D(\alpha, \beta)=\min\limits_xL(x, \alpha, \beta)$

然后考虑对上述问题求极大值

$\max\limits_{\alpha\ge0;\beta}\theta_D(\alpha, \beta)=\max\limits_{\alpha\ge0;\beta}\min\limits_xL(x, \alpha, \beta)$

假设对这个问题存在最优解，

$d^*=\max\limits_{\alpha\ge0;\beta}\theta_D(\alpha, \beta)$

原始问题和对偶问题的关系

那么现在我们就需要考虑原始问题和对偶问题之间存在什么关系，即我们能不能通过求解对偶问题来得到原始问题的解，或者说两者是否有同一个解。

这里就需要引入KKT条件：

对于上文中的原始问题和对偶问题，假设 $f(x), c_i(x)$ 是凸函数， $h_j(x)$ 是仿射函数，且不等式约束 $c_j(x)\le0$ 是严格可行的，那么 $x^*, \alpha^*, \beta^*$ 分别是原始问题和对偶问题的解的充分必要条件是 $x^*, \alpha^*, \beta^*$ 满足以下条件：

$\begin{align} &\nabla_xL(x^*, \alpha^*, \beta^*) = 0\\ &\alpha^*c_i(x^*)=0, i=1,2,...,k\\ &c_i(x^*)\le0, i=1,2,...,k\\ &\alpha_i^*\ge0, i1,2,...,k\\ &h_j(x^*)=0, j=1,2,...,l \end{align}$