拉格朗日对偶性

拉格朗日对偶是约束最优化问题中最常见的一种方法，将带约束的问题转化为不带约束的问题，并进行求解。除此之外，拉格朗日对偶性有这非常好的性质，例如：

对偶问题可以给出原问题的一个下界
无论原问题是否是凸的，对偶问题都是凸的
当满足一定的条件的时候，原始问题和对偶问题完全等价。

原始问题

首先我们先提到原始问题。考虑这么一个带约束的问题：

$min_{x} f(x)\\ s.t \ \ c_i(x) \le 0,\ i=1,2,...,k \\ \ \ \ \ h_j(x) = 0, \ j=1,2,...,m$

同时引入广义拉格朗日函数：

$L(x,\alpha,\beta) = f(x)+ \sum_{i=1}^k{\alpha_i c_i(x)} + \sum_{j=1}^m{\beta_j h_j(x)}$

其中$\alpha_i$,$\beta_i$是拉格朗日乘子，$\alpha_i\ge0$。那么考虑以下的函数：

$\theta_p(x) = max_{\alpha,\beta;\alpha\ge0}L(x,\alpha,\beta)$

假设存在一个$x$,$x$会是以下四种情况之一：

$x$满足约束$c_i(x)\le0,h_j(x)=0$
$x$不满足约束$c_i(x) \le 0 $
$x$不满足约束$h_j(x)=0$
$x$不满足约束$h_j(x)=0$和$h_j(x)=0$

考虑第一种情况，此时$\theta_p(x)$里面的max为了最大化$L(x,\alpha,\beta)$, 会让$\alpha_i = 0$,且$\beta_i$值任意，此时$\theta_p(x)$等价于$f(x)$.即此时$\theta_p(x)$等价于原问题。

考虑第二种情况，此时$c_i(x) > 0$.$\theta_p(x)$里面的max为了最大化$L(x,\alpha,\beta)$, 会让$\alpha_i \rightarrow +\infty$,且$\beta_i$值任意，此时$\theta_p(x) \rightarrow +\infty$。

考虑第三种情况，此时$h_j(x) \ne 0$,$\theta_p(x)$里面的max为了最大化$L(x,\alpha,\beta)$, 会让$\beta_i \rightarrow +\infty或-\infty$,且$\alpha_i$值为0.此时，$\theta_p(x) \rightarrow +\infty$。

考虑第四种情况，此时$h_j(x) \ne 0$，$c_i(x) > 0$,$\theta_p(x)$里面的max为了最大化$L(x,\alpha,\beta)$, 会让$\beta_i \rightarrow +\infty或-\infty$,且$\alpha_i \rightarrow +\infty$，$\theta_p(x) \rightarrow +\infty$。

因此可以看出$\theta_p(x)$的性质，

$\theta _p=\begin{cases} f\left( x \right)\\ +\infty\\ \end{cases}$

如果考虑问题

$min_x \theta_p(x)$

该问题和原问题是等价的，即它们有等价的解或者同样无解。这样子就得到了广义拉格朗日函数的极小极大问题。定义原问题的最优解为：

$p^* = min_x \theta_p(x)$

对偶问题

定义问题：

$\theta_D(\alpha,\beta)=min_x L(x,\alpha,\beta)$

再考虑极大化$\theta_D(\alpha,\beta)=min_x=L(x,\alpha,\beta)$,即

$max_{\alpha_i,\beta_j;\alpha_i\ge 0} \theta_D(\alpha,\beta) = max_{\alpha_i,\beta_j;\alpha_i\ge 0} min_x L(x,\alpha,\beta)$

该问题被称为广义拉格朗日函数的极大极小问题。该问题表达为带约束的优化问题

$max_{\alpha_i,\beta_j} min_x L(x,\alpha,\beta) \\ s.t \ \ \alpha_i\ge 0, \ \ i=1,2,...,k$

该带约束的问题被称为原始问题的对偶问题。同时定义该对偶问题的最优解为：

$d^* = max_{\alpha_i,\beta_j} \theta_D(\alpha,\beta)$

对偶问题和原始问题的关系

弱对偶性和强对偶性

对偶问题和原始问题的最优解满足以下关系：

$d^* \le p^*$

证明很简单，即：

$\theta_D(\alpha,\beta)=min_x L(x,\alpha,\beta) \le L(x,\alpha,\beta) \le max_{\alpha,\beta;\alpha\ge0}L(x,\alpha,\beta)=\theta_p(x)$

即

$\theta_D(\alpha,\beta) \le \theta_p(x)$

则有

$max_{\alpha,\beta} \ \theta_D(\alpha,\beta) \le min_x \ \theta_p(x) \\ d^* \le p^*$

这个性质也被称为弱对偶性，对所有的优化问题成立，即使原始问题非凸。相对于弱对偶性，也有强对偶性：

$d^* = p^*$

Slater条件

考虑原始问题和对偶问题。假设函数$f(x) , c_i(x)$是凸函数，并且$h_j(x)$是仿射函数，并且不等式$c_i(x)$是严格可行的,即存在x,对于所有的i有$c_i(x) < 0$则存在$x^,\alpha^,\beta^$,使得$x^$是原问题的最优解，$\alpha^,\beta^$是对偶问题的最优解，同时有：

$d^* = p^* = L(x^*,\alpha^*,\beta^*)$

Note, 该slater条件对应SVM即要求数据集是线性可分的；如果数据是线性不可分的，那么此时使用SVM寻找分隔超平面也失去了意义。

KKT条件

对于原始问题和对偶问题，假设假设函数$f(x) , c_i(x)$是凸函数，并且$h_j(x)$是仿射函数，并且不等式$c_i(x)$是严格可行的，则$x^$是原问题的最优解，$\alpha^,\beta^$是对偶问题的最优解的充分必要条件是$x^$$\alpha^,\beta^$满足以下的KKT条件：

$\begin{cases} \Delta_x L(x^*,\alpha^*,\beta^*) =0 \\ \Delta_\alpha L(x^*,\alpha^*,\beta^*) =0 \\ \Delta_\beta L(x^*,\alpha^*,\beta^*) =0 \\ \alpha_i^*c_i(x)=0, i=1,2,...,k \\ c_i(x^*) \le 0 , i=1,2,...,k \\ \alpha_i \ge 0 , i=1,2,...,k \\ h_j(x^*)=0, j=1,2,...,m \end{cases}$

其中，$\alpha_i^c_i(x)=0, i=1,2,…,k $被称为是KKT条件的对偶互补条件。由此条件可知：若$\alpha_i^ >0$,则$c_i(x^*)=0$.

其他

当原始问题为凸优化问题的时候，其对偶问题的强对偶性与KKT条件是互为充要的。

当原始问题不为凸优化问题是，利用其对偶问题也可以得到原问题最优解的下界。

参考文章

https://blog.csdn.net/qq_32742009/article/details/81413068

统计学习方法附录C