拉格朗日对偶性

专栏文章汇总

文章结构如下：

1： 原始问题

2： 对偶问题

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

4： 参考文献

在约束最优化问题中，常常利用拉格朗日对偶性(Lagrange duality)将原始问题转为对偶问题，通过解决对偶问题而得到原始问题的解。

对偶问题有非常良好的性质，以下列举几个：

1. 对偶问题的对偶是原问题；
2. 无论原始问题是否是凸的，对偶问题都是凸优化问题；
3. 对偶问题可以给出原始问题一个下界；
4. 当满足一定条件时，原始问题与对偶问题的解是完全等价的；

1： 原始问题

假设 f \left( x \right), c_{i} \left( x \right), h_{j} \left( x \right) 是定义在 R^{n} 上的连续可微函数。
称约束最优化问题

\begin{align*} \\& \min_{x \in R^{n}} \quad f \left( x \right) \\ & s.t. \quad c_{i} \left( x \right) \leq 0, \quad i = 1,2, \cdots, k \\ & \quad \quad h_{j} \left( x \right) = 0, \quad j=1,2, \cdots, l\end{align*} \\

为原始最优化问题或原始问题。

首先引入拉格朗日函数（generalized Lagrange function）

\begin{align*} \\& L \left( x, \alpha, \beta \right) = f \left( x \right) + \sum_{i=1}^{k} \alpha_{i} c_{i} \left( x \right) + \sum_{j=1}^{l} \beta_{j} h_{j}\left( x \right) \end{align*} \\
其中， x=\left(x^{\left( 1 \right)}, x^{\left( 2 \right)}, \cdots, x^{\left( n \right) } \right)^{T} \in R^{n}, \alpha_{i}, \beta_{j} 是拉格朗日乘子， \alpha_{i} \geq 0 。

构建关于 x 的函数

\begin{align*} \\& \theta_{P} \left( x \right) = \max_{\alpha, \beta; \alpha_{i} \geq 0} L \left( x, \alpha, \beta \right) \end{align*} \\
假设给定某个违反原始问题约束条件的 x ，即存在某个 i 使得 c_{i} \left( x \right) > 0 或 h_{j} \left( x \right) \neq 0 。若 c_{i} \left( x \right) > 0 ，可令 \alpha_{i} \to +\infty ，使得 \theta_{P} \left( x \right)=+\infty ；若 h_{j} \left( x \right) \neq 0 ，可令 \beta_{j} 使 \beta_{j} h_{j} \left( x \right) \to +\infty ，使得 \theta_{P} \left( x \right)=+\infty 。将其余 \alpha_{i}, \beta_{j} 均取值为0。
即

\begin{align*} \\& \theta_{P} \left( x \right) = \max_{\alpha, \beta; \alpha_{i} \geq 0} \left[ f \left( x \right) + \sum_{i=1}^{k} \alpha_{i} c_{i} \left( x \right) + \sum_{j=1}^{l} \beta_{j} h_{j}\left( x \right)\right] = +\infty \end{align*}\\

假设给定某个符合原始问题约束条件的 x ，即 c_{i} \left( x \right) \leq 0 且 h_{j} \left( x \right) = 0 ，
则

\begin{align*} \\& \theta_{P} \left( x \right) =\max_{\alpha, \beta; \alpha_{i} \geq 0} \left[ f \left( x \right) + \sum_{i=1}^{k} \alpha_{i} c_{i} \left( x \right) + \sum_{j=1}^{l} \beta_{j} h_{j}\left( x \right)\right]= f \left( x \right) \end{align*} \\
由以上，得

\begin{align*} \theta_{P} \left( x \right) = \left\{ \begin{aligned} \ & f \left( x \right), x满足原始问题约束 \\ & +\infty, 否则 \end{aligned} \right.\end{align*} \\
则极小化问题

\begin{align*} \\& \min_{x} \theta_{P} \left( x \right) = \min_{x} \max_{\alpha, \beta; \alpha_{i} \geq 0} L \left( x, \alpha, \beta \right)\end{align*} \\
与原始最优化问题等价，即有相同的解。（因为当趋向无穷时，问题无解，因此必须满足约束条件）

\begin{align*} \\& \min_{x} \max_{\alpha, \beta; \alpha_{i} \geq 0} L \left( x, \alpha, \beta \right)\end{align*}\\

称为广义拉格朗日函数的极小极大问题。

定义原始问题的最优值

\begin{align*} \\& p^{*} = \min_{x} \theta_{P} \left( x \right) \end{align*} \\
称为原始问题的值。

2： 对偶问题

构建关于 \alpha, \beta 的函数

\begin{align*} \\& \theta_{D} \left( \alpha, \beta \right) = \min_{x} L \left( x, \alpha, \beta \right)\end{align*} \\
则极大化问题

\begin{align*} \\& \max_{\alpha,\beta;\alpha_{i} \geq 0} \theta_{D} \left( \alpha, \beta \right) = \max_{\alpha,\beta;\alpha_{i} \geq 0} \min_{x} L \left( x, \alpha, \beta \right) \end{align*} \\
称为广义拉格朗日函数的极大极小问题。

将广义拉格朗日函数的极大极小问题表示为约束最优化问题

\begin{align*} \\& \max_{\alpha,\beta;\alpha_{i} \geq 0} \theta_{D} \left( \alpha, \beta \right) = \max_{\alpha,\beta;\alpha_{i} \geq 0} \min_{x} L \left( x, \alpha, \beta \right) \\ & \quad s.t. \quad \alpha_{i} \geq 0, \quad i =1,2, \cdots, k \end{align*} \\
称为原始问题的对偶问题。

定义对偶问题的最优值

\begin{align*} \\& d^{*} = \max_{\alpha, \beta;\alpha_{i} \geq 0} \theta_{D} \left( \alpha, \beta \right) \end{align*} \\
称为对偶问题的值。

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

若原始问题与对偶问题都有最优解，则

\begin{align*} \\& d^{*} = \max_{\alpha,\beta;\alpha_{i} \geq 0} \min_{x} L \left( x, \alpha, \beta \right) \leq \min_{x} \max_{\alpha, \beta; \alpha_{i} \geq 0} L \left( x, \alpha, \beta \right) = p^{*}\end{align*}\\
这个性质便叫做弱对偶性（weak duality），对于所有优化问题都成立，即使原始问题非凸。

与弱对偶性相对应的有一个强对偶性（strong duality） ，强对偶即满足：

d^{*}=p^{*}\\
强对偶是一个非常好的性质，因为在强对偶成立的情况下，可以通过求解对偶问题来得到原始问题的解，在 SVM 中就是这样做的。当然并不是所有的对偶问题都满足强对偶性 ，在 SVM 中是直接假定了强对偶性的成立，其实只要满足一些条件，强对偶性是成立的，比如说 Slater 条件与KKT条件。

Slater条件：对于原始问题及其对偶问题，假设函数 f \left( x \right) 和 c_{i} \left( x \right) 是凸函数， h_{j} \left( x \right) 是仿射函数，且不等式约束 c_{i} \left( x \right) 是严格可行的，即存在 x ，对所有 i 有 c_{i} \left( x \right) < 0 ，则存在 x^{*}, \alpha^{*}, \beta^{*} ，使 x^{*} 是原始问题的解， \alpha^{*}, \beta^{*} 是对偶问题的解，并且

\begin{align*} \\& p^{*}=d^{*} = L \left( x^{*}, \alpha^{*}, \beta^{*} \right) \end{align*}\\
也就是说如果原始问题是凸优化问题并且满足 Slater 条件的话，那么强对偶性成立。需要注意的是，这里只是指出了强对偶成立的一种情况，并不是唯一的情况。

KKT条件：对于原始问题及其对偶问题，假设函数 f \left( x \right) 和 c_{i} \left( x \right) 是凸函数， h_{j} \left( x \right) 是仿射函数，且不等式约束 c_{i} \left( x \right) 是严格可行的，即存在 x ，对所有 i 有 c_{i} \left( x \right) < 0 ，则存在 x^{*}, \alpha^{*}, \beta^{*} ，使 x^{*} 是原始问题的解， \alpha^{*}, \beta^{*} 是对偶问题的解的充分必要条件是 x^{*}, \alpha^{*}, \beta^{*} 满足下面的Karush-Kuhn-Tucker(KKT)条件：

\begin{align*} \\& \nabla _{x} L \left( x^{*}, \alpha^{*}, \beta^{*} \right) = 0 \\ & \alpha_{i}^{*} c_{i} \left( x^{*} \right) = 0,\quad i= 1, 2, \cdots, k \\ & c_{i} \left( x^{*} \right) \leq 0, \quad i=1,2, \cdots, k \\ & \alpha_{i}^{*} \geq 0, \quad i=1,2, \cdots, k \\ & h_{j} \left( x^{*} \right) = 0, \quad j=1,2, \cdots, l\end{align*}\\
总的来说就是说任何满足强对偶性的优化问题，只要其目标函数与约束函数可微，任一对原始问题与对偶问题的解都是满足 KKT 条件的。即满足强对偶性的优化问题中，若 x^{*} 为原始问题的最优解， \alpha^{*}, \beta^{*} 为对偶问题的最优解，则可得 x^{*}, \alpha^{*}, \beta^{*} 满足 KKT 条件。

KKT详见：Karush-Kuhn-Tucker (KKT)条件

小结：本文介绍了对偶的基本概念，对于一个约束优化问题，找到其对偶问题，当弱对偶成立时，可以得到原始问题的一个下界。而如果强对偶成立，则可以直接求解对偶问题来解决原始问题。 SVM 就是这样的。对偶问题由于性质良好一般比原始问题更容易求解，在 SVM 中通过引入对偶问题可以将问题表示成数据的内积形式从而使得 kernel trick 的应用更加自然）。

4： 参考文献

李航. 统计学习方法[M]. 北京：清华大学出版社，2012

支持向量机：Duality " Free Mind