Duality (optimization)

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem.However in general the optimal values of the primal and dual problems need not be equal. Their difference is called the duality gap. For convex optimization problems, the duality gap is zero under a constraint qualification condition.

转化对偶问题的方法主要是用来求解形如下列的有约束函数的极值的问题的一种解法：

\begin{equation} \begin{aligned} &\min _{x} f(x) \\ \text { s.t. } &g(x) \leq 0 \\ &h(x)=0 \end{aligned} \end{equation}

首先引入参数把有约束问题转化为无约束问题：

\begin{equation} \mathcal{L}(x, \alpha, \beta)=f(x)+\alpha g(x)+\beta h(x) \quad \alpha \geq 0, \beta: \quad \text { Lagrange 乘子 } \end{equation}

于是原来的有约束规划问题转化为了：

\begin{equation} \min _{x} \max _{\alpha \geq 0, \beta} \mathcal{L}(x, \alpha, \beta) \end{equation}

下边进行一个简单的说明来证明上述问题与原来的无约束问题等价：

  • g(x)>0,则α∗→∞g(x)>0,\text{则}\alpha^* \to \infty
  • g(x)≤0,则α∗=0g(x)\le0,\text{则}\alpha^*=0

也就是说α\alpha存在可行的解是建立在g(x)≤0g(x)\le0的前提下的.同理可以用来说明β\beta也是一样的条件，换言之，只有当x在原约束条件内时，上述函数才可能有可行解，且最优解的值为min⁡f(x)\min f(x).
转化成上述问题后，函数的最优值还是不好求解，所以我们引入上述规划问题的对偶问题：

\begin{equation} \max _{\alpha \geq 0, \beta}\min _ {x} \mathcal{L}(x, \alpha, \beta) \end{equation}

可以通过下列的证明（弱对偶）得到：

\begin{equation} d^{*}=\max _{\alpha \geq 0, \beta} \min _{x} \mathcal{L}(x, \alpha, \beta) \leq \min _{x} \max _{\alpha \geq 0, \beta} \mathcal{L}(x, \alpha, \beta)=p^{*} \end{equation}

具体证明过程如下：

\begin{equation} \begin{gathered} g(a)=\min _{x} f(a, x) \\ g(a) \leq f(a, x), \text { for any } x \\ \max _{\mathrm{a}} g(a) \leq \max _{\mathrm{a}} f(a, x), \text { for any } x \\ \max _{\mathrm{a}} g(a) \leq \min _{x} \max _{\mathrm{a}} f(a, x) \\ \max _{a} \min _{x} f(a, x) \leq \min _{x} \max _{\mathrm{a}} f(a, x) \end{gathered} \end{equation}

这时如果优化问题是一个凸优化问题，且满足下列的KKT条件：

\begin{align} \nabla \mathcal{L}\left(x^{*}, \alpha^{*}, \beta^{*}\right) &=0 \\ \alpha^{*} & \geq 0 \\ g\left(x^{*}\right) & \leq 0 \\ h\left(x^{*}\right) &=0 \\ \alpha^{*} g\left(x^{*}\right) &=0 \end{align}

另外如果α∗>0\alpha^*>0 ，那么g(x∗)=0g(x^*)=0 ，这时我们称约束被激活
如果g(x∗)<0g(x^*)<0 ，那么α∗=0\alpha^*=0 ，这时我们则称约束未被激活
那么上述不等式就可以取到等号，即两个问题是等价的（强对偶）：

\begin{equation} d^{*}=\max _{\alpha \geq 0, \beta} \min _{x} \mathcal{L}(x, \alpha, \beta) = \min _{x} \max _{\alpha \geq 0, \beta} \mathcal{L}(x, \alpha, \beta)=p^{*} \end{equation}

这也就是说我们要找的最优解满足方程7。这个时候再把x的值代入就可以将原来的优化问题转化为了针对α,β\alpha,\beta的优化问题（SVM的思路）