拉格朗日对偶性

前言

世界没有联想将会怎样。

其实一开始我想研究的内容是SVM，感觉SVM本身并不复杂，但是SVM所涉及的拉格朗日对偶性和核技巧却让我很是费解。几经周折，查阅资料才得知，拉格朗日对偶性在优化理论中非常常见，在最大熵模型当中也有应用，所以决定研究一下拉格朗日对偶性，同时也可以加深一下对SVM的理解。

约束最优化问题

拉格朗日对偶性其实是一类约束最优化问题的性质。第一次见到拉格朗日对偶性的时候，对其表达式形式和名字本身都感觉很熟悉，但是似乎又少了些什么。后来才知道，这与经典微积分当中的多元函数的条件极值有着密切的联系。

多元函数的条件极值

先回顾一下多元函数的条件极值，以简单的二元为例：
\begin{align}
&\min f(x,y)\\
&s.t. \phi(x,y)=0
\end{align}

使用拉格朗日乘子法(Lagrange Multiplier)来求目标函数的极值，步骤如下：
首先设辅助函数$$F(x,y,\lambda)=f(x,y)+\lambda\phi(x,y)$$ 然后对$F(x,y,\lambda)$的各个变量求一阶导数，使之为0并联立
\begin{cases}
F’_x(x,y,\lambda)=f’_x(x,y)+\lambda\phi’_x(x,y)=0\\
F’_y(x,y,\lambda)=f’_y(x,y)+\lambda\phi’_y(x,y)=0\\
F’_\lambda(x,y,\lambda)=\phi(x,y)=0
\end{cases}

最后从上述方程中解出来的$x,y$代入到目标函数$f(x,y)$即可。

含有不等式约束的最优化问题

一般来说，多元函数的条件极值可以看做是一类只含有等式约束的最优化问题。相比而言，拉格朗日对偶性则多了一些不等式约束，这也是两者的最大区别。但是，两者的解决方法极其相似。

拉格朗日对偶性

拉格朗日对偶性实际上指在约束最优化问题中，使用了拉格朗日乘子法的原问题和其对偶问题之间的相互关系。一般来说，满足了KKT条件优化问题总是能够满足强对偶性（KKT是强对偶性必要条件，但是一般都能够生效），使得优化问题中的原问题的解等价于其对偶问题的解。
后面章节先直接介绍广义的拉格朗日乘子法，然后说明拉格朗日对偶性（这是拉格朗日乘子法能够应用含有不等式约束最优化问题的关键），最后直接给出了KKT条件（强对偶性，SVM能够使用核技巧的基础）。

广义拉格朗日乘子法

首先必须声明的是，在经典微积分当中，多元函数的条件极值问题所使用的方法被称为拉格朗日乘子法。而带有不等式约束的最优化问题所使用的方法，我以下称为广义拉格朗日乘子法。

原问题
假设$f(x),h_i(x),g_j(x)$是定义在$R^n$上的连续可微函数，考虑最优化问题
\begin{align}
\min_x& f(x)\\
s.t.& h_i(x)=0,i=1,…,m\\
& g_j(x)\leq0,j=1,…,n
\end{align}

首先引入广义拉格朗日函数
$$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^m \alpha_i h_i(x)+\sum_{j=1}^n \beta_j g_j(x)$$

其中，$x_i=(x^{(1)},x^{(2)},…,x^{(n)})^T \in R^n$，$\alpha_i,\beta^i$是拉格朗日乘子，$\alpha_i \geq 0$。注意这里不等式约束引入的方式跟等式约束相同，至于为何能这么做后面说明。
于是原始问题等价于
$$\min_x \max_{\alpha,\beta:\alpha_i \geq 0} L(x,\lambda,\beta)$$

对偶问题
对偶问题和原问题的区别在于交换了最大值和最小值的位置，同时让$\alpha_i \geq 0$变为约束条件
\begin{align}
\max_{\alpha,\beta:\alpha_i \geq 0} \min_x L(x,\lambda,\beta)\\
s.t.\alpha_i \geq,i=1,…,m 0
\end{align}

以上更详细的过程可以参考《统计学习方法》中附录C的内容。

进一步联想

其实，按照一般的正常想法，关于拉格朗日对偶性的问题到这里就应该截止了，可是对于学数学出身并且有强迫症的我觉得完全不对啊，各种问题接踵而至：
1.为何拉格朗日乘子法能够用在含有不等式约束的最优化问题中？
2.什么是拉格朗日对偶性，仅仅是两个对偶问题就能称之为对偶性？
3.什么是强对偶，这和KKT条件之间有什么关系？
…
于是才有了后面的章节。

对偶性理论

这个首先介绍，这个章节的来源：
[1] 带约束优化问题 拉格朗日 对偶问题 KKT条件
[2] 优化问题中的对偶性理论
特别是前者所举出的例子对于对偶理论的解释让人醍醐灌顶，如果能看懂上满两篇，那么请直接忽略后面的章节。
言归正传。

拉格朗日对偶函数

首先定义拉格朗日对偶函数
$$t(\alpha,\beta)=\inf_{x\in\mathcal{D}} L(x,\alpha,\beta)=\inf_{x \in D} \left(f(x)+\sum_{i=1}^m \alpha_i h_i(x)+\sum_{j=1}^n \beta_j g_j(x) \right)$$

其中$\inf$表示下确界，这里沿用上一章节的优化问题。
不妨假设$x^\ast$是问题的一个可行解，由于$g_j(x) \leq 0$且$\beta_i \geq 0$得
$$\sum_{i=1}^m \alpha_i h_i(x)+\sum_{j=1}^n \beta_j g_j(x) \leq 0$$

从而
$$L(x^\ast,\alpha,\beta)=f(x^\ast)+\sum_{i=1}^m \alpha_i h_i(x^\ast)+\sum_{j=1}^n \beta_j g_j(x^\ast) \leq f(x^\ast)$$

因此
$$t(\alpha,\beta)=\inf_{x\in\mathcal{D}} L(x,\alpha,\beta) \leq L(x^\ast,\alpha,\beta) \leq f(x^\ast)$$

然而我看到这里总感觉一知半解，其实，最关键的一句话没说出来：

上面的过程其实就是目标函数加一个负值，它当然小于原函数值，它阐述了对偶函数是最优值的下界的性质，从而使我们可以通过极大化对偶问题来逼近原函数最优解。

这也就是为什么广义拉格朗日乘子法可以使用在含有不等式约束的最优化问题中的原因。另外，一个逼近过程的例子可以本章节开头部分参考资料[1]中看到，而参考资料[2]则叙述一套数学上比较完备的对偶理论，可惜整体逻辑性不好。
但是问题依然存在：对偶性体现在什么地方？接着看下面的章节。

对偶性

其实参考资料[1]和[2]都举了一个非常精彩的例子来解释对偶性，为了更熟悉当然也更省事，我直接当了搬运工。

原问题

以线性规划为例
\begin{align}
\min & C^T x\\
s.t. & Ax = b\\
&x \geq 0
\end{align}

广义拉格朗日函数
$$L(x,\lambda ,\mu)=C^T x-\sum\limits_{i=1}^n \lambda_i x_i+\mu^T(Ax-b)=-b^T\mu+(C+A^T\mu-\lambda)^Tx$$

对偶函数
\begin{align}
g(\lambda , \mu)&=\inf\limits_x L(x, \lambda , \mu)
= -b^T\mu +\inf\limits_x (C + A^T\mu - \lambda)^Tx\\
&=\begin{cases}-b^T \mu，&A^T\mu - \lambda + c = 0\\ -\infty,&others\end{cases}
\end{align}

对偶问题

上面是对偶函数，我们说过，对偶函数刻画的是一个下界，哪个下界是最好的呢？最大的是最好的，所以，对偶问题可以表述为$\max g(\lambda, \mu)$，重新整理表述为
\begin{align}
\max& -b^T \mu\\
s.t.& A^T\mu - \lambda + c = 0\\
&\lambda \geq 0
\end{align}

这里将$\lambda$省去，进一步缩写为
\begin{align}
\max& -b^T \mu\\
s.t.& A^T\mu - \lambda + c \geq \lambda
\end{align}

将此问题当做一个新的原问题，重复上面的过程（注：跟上边的不等式形式符号变了，但表达没变）
\begin{align}
\max& C^Tx\\
s.t.& A^T x \leq b
\end{align}

广义拉格朗日函数
$$L(x, \lambda) = C^Tx + \lambda^T(Ax - b)
= -b^T\lambda + (A^T\lambda + C)^T x$$

对偶函数
\begin{align}
g(\lambda)& = \inf\limits_x L(x, \lambda) = -b^T\lambda + \inf\limits_x (A^T\lambda + C)^T x\\
&=\begin{cases}g(\lambda) = -b^T \lambda，&A^T\lambda+c=0\\ -\infty,&others\end{cases}
\end{align}

最后

于是$\max g(\lambda)$可以表示为
\begin{align}
\max& -b^T \lambda\\
s.t.& A^T \lambda + c = 0\\
&\lambda \geq 0
\end{align}

最后发现，以上表达式跟原问题及其相似。或者可以说，对偶问题的对偶问题就是原问题？

关于更详细的拉格朗日乘子法和KKT条件的推导过程，可看参考资料[3]。不过值得注意是的，由于KKT条件只是强对偶的必要条件，故有些推导是错误的。

KKT条件

现在来回答以下两个问题，什么是强对偶和KKT条件(Karush-Kuhn-Tucker)。

强对偶

首先，记原问题的最优解为$p^\ast=\min f(x)$，记对偶问题的最优解为$d^\ast=\max t(\alpha,\beta)$。
然后，回顾前面讲述拉格朗日对偶函数所作出的结论，很容易得出一个结论：
因为对原问题的任意可行解$x^\ast$满足
\begin{align}
&t(\alpha,\beta) \leq f(x^\ast)\\
\Rightarrow &t(\alpha,\beta) \leq p^\ast\\
\Rightarrow &\max t(\alpha,\beta) \leq p^\ast\\
\Rightarrow &d^\ast \leq p^\ast
\end{align}

这便是弱对偶性，即对偶问题的最优解不超过原问题的最优解。
那么很自然的，如果原问题与对偶问题的最优解相等，即等式$d^\ast=p^\ast$ 成立，则称它满足强对偶性。

定义

假设函数$f,g_i,h_j$都是一阶可微函数，定义域是开集，并且对问题的凸性仍无任何假定（关于为何突然引入凸函数，这个看后面小节），$x^\ast$和$\alpha^\ast,\beta^\ast$分别是原问题和对偶问题的最优解，那么
满足以下式子的
\begin{align}
\nabla_xL(x^\ast,\alpha^\ast,\beta^\ast)=0\\
g_i(x^\ast) \leq 0, \quad i=1,…,m \\
h_j(x^\ast) =0, \quad j=1,…,n\\
\alpha_i^\ast g_i(x^\ast) = 0, \quad i=1,…,m \\
\alpha_i^\ast \geq 0, \quad i=1,…,m
\end{align}

可以称为Karush-Kuhn-Tucker(KKT)条件。关于KKT条件更好的定义可以参看KKT-Condition。

KKT条件的意义

KKT条件的意义在于，如果最优化问题是凸优化（比如SVM），并且满足了KKT条件，则该优化问题的原问题和其对偶问题具有强对偶性，因此，可以通过将原问题转化为对偶问题来求解。
或者另一种说法是，KKT条件是强对偶的必要条件（至于如何推导，有待研究）。
那什么是充分条件呢？一般来说，如果原问题是凸优化就是，当然似乎也有例外，这个就没有仔细研究了（但可以肯定的是SVM就是这类凸优化问题）。

依然存在的问题

1.为何KKT条件是强对偶的必要条件，如何推导？
2.满足KKT条件的凸优化就一定满足强对偶性？存在例外吗？
解决上面的问题，似乎需要这本书《凸优化》。

参考资料

[1] 带约束优化问题 拉格朗日 对偶问题 KKT条件
[2] 优化问题中的对偶性理论
[3] 拉格朗日乘子法和KKT条件