拉格朗日对偶
拉格朗日对偶常用于带约束条件的最优化问题上，为了系统讲述这种方法的思想，我们首先引入一个带约束条件的最优化问题：
$$\quad min_xf(x) \\ s.t.\quad c_i(x) \leq 0 \quad (i=1, 2, …, k) \\ \quad h_j(x)=0 \quad (j=1, 2, …, l)$$
其中，$f(x)、c_i(x)、h_j(x)$ 分别是定义在 $x \in \mathbb{R}^n$ 上的连续可微函数。对于此类带约束条件的优化问题，一般我们考虑使用拉格朗日乘子法解决，首先引入拉格朗日乘子 $\alpha_i(\alpha_i \geq 0), \beta_j$，构造广义拉格朗日函数如下：
$$L(x, \alpha, \beta)=f(x)+\Sigma_{i=1}^{k} \alpha_i \cdot c_i(x)+\Sigma_{j=1}^l \beta_j \cdot h_j(x)$$
定义关于 $x$ 的函数：
$$\theta_p(x)=max_{\alpha,\beta:\alpha \geq 0}L(x, \alpha, \beta)=max_{\alpha,\beta:\alpha \geq 0}f(x)+\Sigma_{i=1}^{k} \alpha_i \cdot c_i(x)+\Sigma_{j=1}^l \beta_j \cdot h_j(x)$$
当 $c_i(x)$ 或 $h_j(x)$ 不满足原始约束条件时，即 $c_i(x)>0$ 或者 $h_j(x) \neq 0$ 时，$\theta_p(x)=max_{\alpha,\beta:\alpha \geq 0}L(x, \alpha, \beta)=+\infty$，而当二者都满足原始约束条件时，$\theta_p(x)=max_{\alpha,\beta:\alpha \geq 0}L(x, \alpha, \beta)=f(x)$，即：
$$\theta_p(x)=\begin{cases}+\infty& \text{$c_i(x)$ 或 $h_j(x)$ 不满足约束条件}\\
f(x)& \text{otherwise}
\end{cases}$$
因此，$min_x \theta_p(x)$ 等价于 $c_i(x)$ 或 $h_j(x)$ 同时满足约束条件下的 $min_xf(x)$ 问题，即其与原始问题等价。也就是说，带约束条件的原始问题与不带约束条件的广义拉格朗日函数的极小极大问题等价，即与如下问题等价：
$$min_x \theta_p(x)=min_xmax_{\alpha,\beta:\alpha \geq 0}L(x, \alpha, \beta)$$
设原始问题的最优值为 $p^*$，即有：$p^*=min_x \theta_p(x)$。
某些时候，直接求原始问题的解计算很复杂，这种情况下，我们通常需要将广义拉格朗日函数的极小极大问题转化为其对偶问题来进行求解，与之相对应的对偶问题为广义拉格朗日函数的极大极小化问题，定义如下：
$$max_{\alpha,\beta:\alpha \geq 0}min_xL(x, \alpha, \beta)$$
设以上对偶问题的最优值是 $d^*$。既然我们将原始问题转化为对偶问题进行求解，那么接下来的一个问题自然就是原始问题的最优值 $p^*$ 与对偶问题的的最优值 $d^*$ 之间有什么关系呢？下面直接以定理的形式给出这二者之间的关系。
定理1. 如果原始问题和对偶问题都有最优值，则有：
$$d^*=max_{\alpha,\beta:\alpha \geq 0}min_xL(x, \alpha, \beta) \leq min_xmax_{\alpha,\beta:\alpha \geq 0}L(x, \alpha, \beta)=p^*$$
证明： 显然，$\forall_{x, \alpha, \beta}$，有如下不等式成立：
$$min_xL(x, \alpha, \beta) \leq min_{x, \alpha \geq 0, \beta}L(x, \alpha, \beta) \leq max_{\alpha,\beta:\alpha \geq 0}L(x, \alpha, \beta)$$
即：$min_xL(x, \alpha, \beta) \leq max_{\alpha,\beta:\alpha \geq 0}L(x, \alpha, \beta)$，进一步地，有：
$$max_{\alpha,\beta:\alpha \geq 0}min_xL(x, \alpha, \beta) \leq min_xmax_{\alpha,\beta:\alpha \geq 0}L(x, \alpha, \beta)$$
即：$d^* \leq p^*$，得证。
既然我们需要通过求对偶问题的最优值 $d^*$ 来求原始问题的最优值 $p^*$，而 $d^* \leq p^*$，那么接下来我们需要关心的问题是，$d^*$ 与 $p^*$ 能否相等？以及二者何时相等呢？针对这两个问题，下面不加证明地给出如下两个定理。
定理2. 对于以上所述的原始问题和对偶问题，当原始优化问题的可行域定义在 $x$ 的凸集上（也就是说，对于可行域内的每一对点，连接该对点的直线段上的每个点也在可行域内），$f(x)$、$c_i(x)$ 是一个凸函数，$h_j(x)$ 是一个仿射函数，并且存在某个 $x$，使得对所有的 $i$，都有 $c_i(x)<0$，那么必定存在 $x^*$、$\alpha^*$ 和 $\beta^*$，使得 $x^*$ 是原始问题的解，$\alpha^*$ 和 $\beta^*$ 是对偶问题的解，同时：
$$d^*=p^*=L(x^*, \alpha^*, \beta^*)$$
定理3. 如果原始问题和对偶问题满足定理 2，那么，$x^*$ 是原始问题的解，$\alpha^*$ 和 $\beta^*$ 是对偶问题的解，并且 $d^*=p^*=L(x^*, \alpha^*, \beta^*)$ 的充分必要条件是 $x^*$、$\alpha^*$ 和 $\beta^*$ 同时满足如下所述的 KKT (Karush-Kuhn-Tucker) 条件：
$$\nabla_xL(x^*, \alpha^*, \beta^*)=0\\
\nabla_{\alpha}L(x^*, \alpha^*, \beta^*)=0\\
\nabla_{\beta}L(x^*, \alpha^*, \beta^*)=0\\
\alpha_i^*c_i(x^*)=0 \quad i=1, 2, …, k\\
\alpha_i^* \geq 0 \quad i=1, 2, …, k\\
c_i(x^*) \leq 0 \quad i=1, 2, …, k\\
h_j(x^*)=0 \quad j=1, 2, …, l$$
其中，$\alpha_i^*c_i(x^*)=0$ 称为 KKT 的对偶互补条件，通过此式可知，如果 $\alpha_i^*>0$，则必有 $c_i(x^*)=0$。