在求解一个优化命题时，如果其对偶形式便于求解，常常可以通过求解对偶问题来避免直接对原问题进行求解。比如机器学习中典型的SVM就涉及到对偶理论，以及拉格朗日乘子法、KKT条件等概念。

首先简单通俗地说说这几个概念是干嘛的

  1. 对偶理论：对偶也就是孪生双胞胎，一个优化命题也就有其对应的兄弟优化命题。

  2. 拉格朗日函数：将原本优化命题的目标函数和约束整合成一个函数。

  3. KKT条件：函数的最优值满足的性质。

上面的解释可能不够准确，但希望对这些概念有个初步的认识，接下来从优化命题的角度来解释一下这些东西。

首先是原问题

$$ \begin{aligned} \min _{x \in R^{n}} f_0(x) & \\ \text { s.t. } f_{i}(x) \leq 0, i &=1,2, \ldots, k \\ h_{j}(x)=0, j &=1,2, \ldots, l \end{aligned} $$

这个优化命题说的是你有个函数 $f_0(x)$，它的自变量是 $x$，维度为 $n$，你想要求这个函数的最小值，同时这个自变量(优化里又叫决策变量)还需要满足 $k$ 个不等式约束 $f_i(x) \le 0$ 以及 $l$ 个等式约束 $h_j(x) = 0$。假设满足这些约束的情况下这个函数的最小值为 $p^*$。

如果是个无约束的求极值问题，高中时我们就学过，求导并令导函数为 $0$ 便能求出函数取得极值时对应的自变量 $x^*$。 但是这里是有约束的优化问题，显然直接求导的方法不再适用，那自然的想法就是把约束去掉，拉格朗日函数就是通过将约束线性组合放入目标函数而形成的新的一个函数：

$$ L(x,\lambda,v) = f_0(x) + \sum_{i=1}^k \lambda_i f_i(x) + \sum_{j=1}^l v_j h_j(x) $$ 这里 $L(x,\lambda,v)$ 是个三元函数 $R^n \times R^k \times R^l \rightarrow R$，且 $\lambda \ge 0,v$ 称为拉格朗日向量，至于这个系数 $\lambda$ 为什么还需要满足 $\lambda \ge 0$，你先记住这是为了确保下界，后面会详细解释。

原问题的等价形式

我们原来是要求函数 $f_0(x)$ 关于 $x$ 的最小值，为了不考虑原问题的约束而构造了拉格朗日函数 $L(x,\lambda,v)$。我们先将其看作是 $\lambda,v$ 的函数，然后定义函数：

$$ q(x) = \max_{\lambda \ge 0,v } L(x,\lambda,v) $$

可以证明 $\min_{x\in R^{n}}q(x)$ 与原问题等价，即满足

$$ p^* = \min_{x\in R^{n}}q(x) = \min_{x\in R^{n}}\max_{\lambda \ge 0,v}L(x,\lambda,v) $$

这个证明很简单，我们只需要分类讨论一下这个无约束问题中原问题约束是否成立：

  1. $x$ 满足原问题约束，则 $q(x) = f_0(x)$

  2. $x$ 不满足原问题约束，即 $f_i(x) \ge 0$ 或 $h_j(x) \not= 0$，则 $q(x) = + \infty$

因此 $\min_{x}q(x) = \min_{x}f_0(x)$ 且 $x$ 满足原问题约束，即 $\min_{x\in R^{n}}q(x)$ 等价于原问题。

拉格朗日对偶函数

先前我们把拉格朗日函数看作是 $\lambda,v$ 的函数，现在我们将其看作是关于 $x$ 的函数，定义拉格朗日对偶函数，这只是个名字，其实就是 $L(x,\lambda,v)$ 关于 $x$ 的下界(或者理解为最小值)：

$$ g(\lambda,v) = \min_{x \in R^{n} } L(x,\lambda,v) $$

拉格朗日对偶函数 $g(\lambda,v)$ 有两个重要的性质：

  1. 这是个凹函数(这里不证明了，感兴趣的可以自查)
  2. $g(\lambda,v)\le p^*$

性质2是重点！我们来证明一下，假设 $\tilde{x}$ 是原问题的可行解，说明 $\tilde{x}$ 满足原问题的不等式约束以及等式约束，将其带入 $L(x,\lambda,v)$ 中，有

$$ L(\tilde{x},\lambda,v) = f_0(\tilde{x}) + \sum_{i=1}^k \lambda_i f_i(\tilde{x}) + \sum_{j=1}^l v_j h_j(\tilde{x}) $$

根据 $g(\lambda,v)$ 的定义有

$$ g(\lambda,v) = \min_{x} L(x,\lambda,v) \le L(\tilde{x},\lambda,v) = f_0(\tilde{x}) + \sum_{i=1}^k \lambda_i f_i(\tilde{x}) $$

$\min_{x} L(x,\lambda,v) \le L(\tilde{x},\lambda,v)$ 是因为函数的(最小值)下界肯定小于可行解代入的值呀！

我们知道 $\tilde{x}$ 是原问题的可行解也意味着 $f_i(x) \le 0$，进一步，如果 $\lambda_i \ge 0$ 会发生什么？也就是 $\lambda_i f_i(x) \le 0$，那么 $$ g(\lambda,v) \le f_0(\tilde{x}) + \sum_{i=1}^k \lambda_i f_i(\tilde{x}) \le f_0(\tilde{x}) $$ 也就是 $g(\lambda,v) \le f_0(\tilde{x})$，这是对任意可行解 $\tilde{x}$ 都成立的，那么对函数取得最小值的 $x^*$ 对应的函数值 $p^*$ 也成立。即

$$ g(\lambda,v) \le p^* $$ 这也就得到了性质2，可以理解为我们为原问题的最优值 $p^*$ 找到了一个下界函数 $g(\lambda,v)$，为了确保下界需要满足我们之前的假设 $\lambda \ge 0$，而对 $v$ 的取值则是任意的。

原问题的对偶形式

前面的分析中我们看到原问题的最优值有一个函数下界，那么如果我们来优化这个函数下界，让它来逼近原问题的最优值，是不是为求解原问题提供了另一种思路呢？这就是所谓的对偶问题

$$ \begin{aligned} d^* =\max _{\lambda \ge 0,v} g(\lambda,v) = \max _{\lambda \ge 0,v} \min _{x \in R^n} L(x,\lambda,v) \end{aligned} $$

这个优化命题相当于最大化原问题的下界函数，其中 $d^*$ 为优化命题的最优值，约束 $\lambda \ge 0 $ 是用来确保下界的。根据 $g(\lambda,v)$ 是凹函数这一性质可知，这个最大化凹函数的优化问题是个凸问题，凸问题也就意味着便于求解，因此无论原问题的凹凸性如何，都可以转化为对偶问题然后通过求解这个凸问题来得到原问题的下界，甚至原问题的最优解。什么时候这个下界函数的最大值等于原问题的最优解呢？这就是下面要讨论的问题。

强对偶性与弱对偶性

我们已知知道 $g(\lambda,v)$ 是原函数最小值 $p^*$ 的下界，那么说明 $g(\lambda,v)$ 的最大值也需要满足

$$ d^* \le p^* $$

这就是弱对偶性了，很自然就满足了，那么强对偶性从名字听就比较强，自然要求要严格一点，不能只是取 $\le$ 号，而是直接取等号，即

$$ d^* = p^* $$

对于弱对偶，我们能够通过求解原问题的对偶问题得到原问题最小值的下界，而如果满足强对偶性，我们直接就得到原问题的最优解了！意味着我们能够通过求解对偶问题来避免直接求解原问题同时获得原问题的最优函数值。

强对偶性

如何才能判断原问题是否满足强对偶性呢？

凸问题通常but not always满足强对偶性 也就是说凸问题中有部分满足强对偶性，那对这些部分约束一下就是slater条件：

存在 $x$ 严格可行：$f_i(x) < 0,i=1,…,k$

当不等式约束为仿射函数时，这个条件可以弱化为

存在 $x$ 满足部分严格可行：$f_i(x) \le 0,i=1,…,m;f_i(x) < 0,i=m+1,…,k$

那么有 $$ \text{凸问题} + \text{Slater条件} = \text{强对偶性} $$

进一步探究一下当原问题满足强对偶性时，原问题和对偶问题的最优解满足哪些性质，首先从 $p^* = d^*$ 看起，利用函数的表达式描述这一关系有：

$$ \begin{aligned} f_0(x^*) &= g(\lambda^*,v^*)\\ &= \min_x (f_0(x) + \sum_{i=1}^k \lambda_i^* f_i(x) + \sum_{j=1}^l v_j^* h_j(x))\\ &\le f_0(x^*) + \sum_{i=1}^k \lambda_i^* f_i(x^*) + \sum_{j=1}^l v_j^* h_j(x^*)\\ &\le f_0(x^*) \end{aligned} $$

第一行到第二行是根据 $g(\lambda,v)$ 的函数定义，第二行到第三行是根据函数的下界小于 $x$ 取任意值对应的函数值，这里 $x = x^*$，第三行到第四行是根据 $x^*$ 满足原问题的约束条件 $f_i(x) \le 0, h_j(x) =0$。所以不等号同时取等号，并可以得出以下两条结论：

  1. 极值条件：$x^*$ 是使 $L(x,\lambda^*,v^*)$ 取得下界的点，即 $x^*$ 是使 $\nabla_x L(x,\lambda^*,v^*) = 0$ 的点

  2. 松弛互补条件：$\sum_{i=1}^k \lambda_i^*f_i(x^*)=0$

KKT条件

KKT也就是原问题和对偶问题的最优点 $x^*,\lambda^*,v^*$ 满足的几个条件：

  1. 原问题的约束条件：$f_i(x^*) \le 0,h_j(x^*)=0$
  2. 对偶问题的约束条件：$\lambda_i^* \ge 0$
  3. 松弛互补条件：$\sum_{i=1}^k \lambda_i^*f_i(x^*)=0$
  4. 极值条件： $\nabla_x f_0(x^*) + \sum_{i=1}^k \lambda_i^* \nabla_x f_i(x^*) + \sum_{j=1}^l v_j^* \nabla_x h_j(x^*) = 0$

如果原问题是凸问题，则KKT条件为充要条件，也就是说满足KKT条件的点也就是原问题和对偶问题的最优解，那就能够在满足KKT条件下用求解对偶问题来替代求解原问题，使得问题求解更加容易。