原始问题

对偶问题是相对与原始问题而言的。下面这个含有约束的最优化问题就称为 原始最优化问题或原始问题 。
$$
\left \{
\begin {aligned}
& \min f(x) \\
s.t. & h_i(x) = 0 (i=1,2,\dots ,m) \\
& g_j(x) \le 0 (j=1,2,\dots ,l) \\
\end {aligned}
\right . \tag 1
$$
对于这个原始问题，我们的求解思路就是构建一个广义拉格朗日函数：
$$
L(x, \lambda, \upsilon) = f(x) + \sum_{i=1}^m \lambda_i h_i(x) +\sum_{j=1}^l \upsilon_j g_j(x)
$$
其中：$\upsilon_j \ge 0$。

通过求解$L(x, \lambda, \upsilon)$函数的最小值来得到$f(x)$的最小值。

将$x$看作常数$\lambda_i, \upsilon_j$看作变量，求$L(x, \lambda, \upsilon)$的最大值：
$$
\begin {aligned}
\theta_P(x) & = \max_{\lambda_i,\upsilon_j \ge 0} L(x, \lambda, \upsilon) \\
&= \max_{\lambda_i,\upsilon_j \ge 0} \{ f(x) + \sum_{i=1}^m \lambda_i h_i(x) +\sum_{j=1}^l \upsilon_j g_j(x) \}
\end {aligned}
$$
当$x$ 满足约束条件时，$\sum_{i=1}^m \lambda_i h_i(x) = 0, \sum_{j=1}^l \upsilon_j g_j(x) \le 0$ ,所以 $\theta_(xP) = f(x)$。

当$x$ 不满足约束条件时， $\theta_P(x) = + \infty$。

即：
$$
\theta_P(x) =
\left \{
\begin {aligned}
&f(x), &x满足约束条件 \\
&+\infty, &x不满足约束条件
\end {aligned}
\right .
$$
所以：
$$
\min \theta_P(x) = \min_x \max_{\lambda_i,\upsilon_j \ge 0} L(x, \lambda, \upsilon) \tag 2
$$
称为广义拉格朗日函数的极小极大问题。

当$x$ 满足约束条件时：
$$
\min f(x) = \min \theta_P(x)
$$
由于以上等价关系，式(2)与式原始优化问题(1)是等价的，所以在有些文章中讨论对偶问题时常用$\min \theta_P(x)$表示原始最优化问题。

原始问题的值用p表示（通常时 p星, hexo需要转义，我就用p了）。
$$
p = \min \theta_P(x)
$$

对偶问题

在《凸优化》这本书中，将对偶函数定义为如下形式(为了符号统一，我修改了部分符号)：
$$
\theta_D(\lambda, \upsilon) = \min_x L(x, \lambda, \upsilon)
$$
即，对偶问题首先将$\lambda, \upsilon$看作常数，将$x$ 看作变量，求$L(x, \lambda, \upsilon)$关于$x$的极小值。

然后求$\theta_D(\lambda, \upsilon)$的极大值：
$$
\max_{\lambda_i,\upsilon_j \ge 0} \theta_D(\lambda, \upsilon) = \max_{\lambda_i,\upsilon_j \ge 0} \min_x L(x, \lambda, \upsilon) \tag 3
$$
这就是广义拉格朗日函数的极大极小问题。与之等价的约束最优化问题如下：
$$
\left \{
\begin {aligned}
& \max_{\lambda_i,\upsilon_j} \theta_D(\lambda, \upsilon) = \max_{\lambda_i,\upsilon_j \ge 0} \min_x L(x, \lambda, \upsilon) \\
s.t. & \upsilon_j \ge 0, (i=1,2,\dots ,l) \\
\end {aligned}
\right . \tag 4
$$
称为原始问题的对偶问题。

对偶问题的值为:
$$
d = \max_{\lambda_i,\upsilon_j \ge 0} \theta_D(\lambda, \upsilon)
$$

note: 对于原始问题(1)来说变量是$x$ , 对于对偶问题(4)来说变量是$\lambda, \upsilon$。所以原始问题的最优解记为$\hat x$，对偶问题的最优解记为$\hat \lambda, \hat \upsilon$。

原问题与对偶问题的关系

在实际应用中对偶问题是怎么使用的呢？

当原始问题和对偶问题都有最优值时：
$$
\begin {aligned}
& \left \{
\begin {aligned}
\theta_D(\lambda, \upsilon) = \min_x L(x, \lambda, \upsilon)\
\\
\theta_P(x) = \max_{\lambda_i,\upsilon_j \ge 0} L(x, \lambda, \upsilon) \\
\end {aligned}
\right . \\
\\
& \Rightarrow
\theta_D(\lambda, \upsilon) = \min_x L(x, \lambda, \upsilon)
\le L(x, \lambda, \upsilon) \le
\max_{\lambda_i,\upsilon_j \ge 0} L(x, \lambda, \upsilon) = \theta_P(x)\\
\\
& \Rightarrow
d = \max_{\lambda_i,\upsilon_j \ge 0} \theta_D(\lambda, \upsilon) \le \min_x \theta_P(x) = p
\end {aligned}
$$

可以看出：在某种情况下原始问题的最优值$p$ 与对偶问题的最优值$d$相等。那么什么情况下原问题和对偶问题的最优值相等呢？

下面直接给出《统计学习方法》中的几个定理和推论。

考虑原始问题(1)和对偶问题(4)。假设$f(x)$和$g_j(x)$是凸函数，$h_i(x)$是仿射函数；并且假设不等式约束$g_j(x)$时严格可行的，即存在$x$，对于所有的$i$有$g_j(x) < 0$，则存在$\hat x, \hat \lambda, \hat \upsilon$，使$\hat x$是原问题的解，$\hat x, \hat \lambda, \hat \upsilon$是对偶问题的解，并且$p = d = L(\hat x, \hat \lambda, \hat \upsilon)$

对于原始问题(1)和对偶问题(4)。假设$f(x)$和$g_j(x)$是凸函数，$h_i(x)$是仿射函数；并且假设不等式约束$g_j(x)$时严格可行的。则$\hat x, \hat \lambda, \hat \upsilon$分别是原始问题和对偶问题的解的充分必要条件是$\hat x, \hat \lambda, \hat \upsilon$满足下面的Karush -Kuhn -Tucker(KKT)条件：
$$
\left \{
\begin {aligned}
\nabla_x f(\hat x) + \sum_i^m \lambda_i \nabla_x h_i(\hat x) + \sum_j^l \upsilon_j \nabla_x g_j(\hat x) &= 0 \\
h_i(\hat x) &= 0 (i=1,2,\dots ,m) \\
g_j(\hat x) &\le 0, (j = 1,2 \dots l) \\
\upsilon_j g_j(\hat x) &= 0, (j = 1,2 \dots l) \\
\upsilon_j & \ge 0, (j = 1,2 \dots l) \\
\end {aligned}
\right .
$$

也就是说在满足上面的(KKT)条件的情况下，对偶问题的最优值和原始问题的最优值相等。

总结

在求解约束的最优化问题时，如果原始问题求解困难，而对偶问题求解相对容易，那么可以在满足KKT条件的情况下，通过求解对偶问题来得到原始问题的最优值和最优解。

参考资料

凸优化(Boyd)

统计学习方法