拉格朗日乘数法(method of Lagrange multipliers)的目的，其实来解决下面这样一个约束最优化问题。

$$ \begin{aligned} min_w \quad & f(w)& \\ s.t. \quad &h_i(w) =0,\quad i=1,...,l\\ \end{aligned} $$

其定义了一个拉格朗日函数(Lagrangian)：

$$ L(w,\beta)=f(w)+\sum^l_{i=1}\beta_i h_i(w) $$

其中，$\beta_i$就叫做拉格朗日乘数(Lagrange multipliers)。 接着让 $L$对$w$与$\beta$ 取偏导数，使其为零：

$$ \frac{\partial L }{\partial w_i} =0; \quad \frac{\partial L }{\partial \beta_i} =0; $$

就可以解出对应的$w$与$\beta$了。

将上面的约束最优化问题扩展到同时包含等式与不等式的约束，则其问题为：

$$ \begin{aligned} min_w \quad & f(w)&\text(1) \\ s.t. \quad & g_i(w) \le 0,\quad i=1,...,k&\text(2)\\ & h_i(w) =0,\quad i=1,...,l&\text(3)\\ \end{aligned} $$

要解决这个问题，需要定义广义拉格朗日函数(generalized Lagrangian function)：

$$ \begin{aligned} L(w,\alpha,\beta)=f(w)+\sum^k_{i=1}\alpha_ig_i(w)+\sum^l_{i=1}\beta_ih_i(w)&&(4) \end{aligned} $$

上面的式子中， $\alpha_i$ 和 $\beta_i$ 都是拉格朗日乘数(Lagrange multipliers)。$\alpha_i\ge 0$。考虑$w$的函数：

$$ \begin{aligned} \theta_{P}(w)=\max_{\alpha,\beta:\alpha_i \geq 0}L(w,\alpha,\beta)&&\text(5) \end{aligned} $$

这里$P$是指原始问题(Primal Problem)。

假设给定某个$w$，如果$w$违反了原始问题的约束条件，也就是存在$g_i(w)>0$或者$h_j(w)\neq 0$，那么可以使$\alpha_i\rightarrow +\infty$ 或$\beta_j h_j(w)\rightarrow +\infty$ ，导致$\theta_{P}(w)$等于正无穷：

$$ \begin{aligned} \theta_P(w)&=\max_{\alpha,\beta:\alpha_i \geq 0} f(w)+\sum^k_{i=1}\alpha_ig_i(w)+\sum^l_{i=1}\beta_ih_i(w) = +\infty&\text(6)\\ \end{aligned} $$

如果$w​$满足约束条件(2)和(3)，则由(4)和(5)可以推出$\theta_P(w)=f(w)​$，因此：

$$ \theta_P(w)= \begin{cases} f(w) & x\text {满足原始问题约束} \\ +\infty & \text{其他} \end{cases} $$

$$ \min_w \theta_P(w)=\min_w \max_{\alpha,\beta:\alpha_i\geq0} L(w,\alpha,\beta) $$

它是与原始问题(1)~(3)等价的，也就是说他们有相同的解。这个问题$\min_w \max_{\alpha,\beta:\alpha_i\geq0} L(w,\alpha,\beta)$也称为广义拉格朗日函数的绩效极大问题。为了方便，定义原始问题的最优解为$p ^\ast = \min_w \theta_P (w)$

对偶问题

定义

$$ \theta_D(\alpha,\beta)=\min_w L(w,\alpha,\beta) $$

上面的式子中，$“D”$ 是 “dual” 的缩写。这里要注意，在对$\theta_P$ 的定义中，之前是对 $\alpha$, $\beta$ 进行优化(max)，这里则是找 $w$ 的最小值(min)。

再考虑极大化$\theta_D(\alpha,\beta)=L(w,\alpha,\beta)$，也就是

$$ \max_{\alpha,\beta:\alpha_i\geq 0} \theta_D(\alpha,\beta) = \max_{\alpha,\beta:\alpha_i\geq 0} \min_w L(w,\alpha,\beta) $$

可以看出，它与之前的问题$\min_w \theta_P(w)=\min_w \max_{\alpha,\beta:\alpha_i\geq0} L(w,\alpha,\beta)​$，是把max和min换了位置。之前是先求极大后求极小，现在是先求极小后求极大。他们两个的关系如下：

$$ d^\ast = \max_{\alpha,\beta:\alpha_i\geq 0}\min_w L(w,\alpha,\beta) \leq \min_w \max_{\alpha,\beta:\alpha_i\geq 0}L(w,\alpha,\beta) =p^\ast $$

也就是说，对偶问题(max min)，是原始问题(min max)的下限。

不过在特定情况下，他们是相等的，也就是

$$ d^*=p^* $$

他们不相等的时候，叫做弱对偶(weak duality)，相等时，则是强对偶(strong duality)。

下面这张图片生动的解释了这一关系：

要他们相等，变成强对偶，需要满足下面的条件：

$f(w)$与$g_i(w)$都是凸函数，$h_i(w)$是仿射函数，且$g$是严格可行(strictly feasible)的，也就是必存在$w$，使所有$g_i(w)<0​$。

那么，$d^*=p^*$的充要条件是，其最优解$w^*,\alpha^*,\beta^*$满足下面的Karush-Kuhn-Tucker(KKT)条件：

$$ \begin{aligned} \frac{\partial}{\partial w}L(w^\ast,\alpha^\ast,\beta^\ast) &= 0,\quad i=1,...,n & \text(K1)\\ \frac{\partial}{\partial \alpha}L(w^\ast,\alpha^\ast,\beta^\ast) &= 0,\quad i=1,...,n & \text(K2)\\ \frac{\partial}{\partial \beta}L(w^\ast,\alpha^\ast,\beta^\ast)&= 0 ,\quad i=1,...,l & \text(K3)\\ \alpha_i^\ast g_i(w^\ast)&= 0,\quad i=1,...,k & \text(K4)\\ g_i(w^\ast)&\leq 0,\quad i=1,...,k & \text(K5)\\ \alpha_i^\ast &\geq 0,\quad i=1,...,k &\text(K6)\\ h_j(x^*)&=0,\quad j=1,...,l&\text(K7) \end{aligned} $$

其中，互补条件(K4)称为KKT的对偶互补条件，由此可知：如果$\alpha^*_i>0$，则$g_i(x^*)=0$。