拉格朗日对偶问题与支持向量机学习笔记(1)

2023-02-27 15:40 作者:ZJU前校长-吴朝晖院士 0人读过 | 我要投稿

0 前言

这两部分内容在之前学凸优化和数据挖掘课的时候就学过了，奈何当时课上全在摸鱼，导致现在要用的时候啥也不会。于是在各种论坛上看别人的笔记，奈何自己实在过于愚笨，很多地方花了很多时间才理解。为了加深自己的印象以及练习一下刚学的markdown，还是写个专栏记录一下自己的学习成果。（不过我不得不说b站专栏对markdown的支持真的太差了，即使使用了相关插件，很多公式也无法识别；此外，由于b站专栏最多只能插入包括公式在内的100张图片，我不得不把这篇文章拆成两部分才能发出来，真是呃呃了）。

本文参考了“https://blog.csdn.net/weixin_44378835/article/details/110732412?utm_source%20=%20app”这篇博文和其他一些博文，进行了一定的缩减，在部分地方添加了自己的想法和更详细的推导过程。

1 拉格朗日对偶问题

1.1 原问题

给出如下的优化问题：

$%5Cdisplaystyle%7B%20min_x%20f_0(x)%5C%5C%0A%5C%5C%0As.t.%5Cquad%20f_i(x)%20%5Cleq%200%2Ci%3D1%2C...%2Cm%5C%5C%0A%5C%5C%0Ah_i(x)%20%3D%200%2C%20i%20%3D1%2C...%2Cn%7D$

其中 $f_i(x)$ 和 $h_i(x)$ 均为 $x$ 的线性组合。我们称这个问题为“原问题”。

在求解原问题的时候，我们会遇到两个不喜欢的东西：①带有约束条件②优化目标不一定是凸函数。因此，我们希望通过转化的方式将原问题变成一个没有约束条件的凸问题，这也是引入拉格朗日乘子法以及构造拉格朗日对偶问题的原因。

1.2 消除约束条件

通过引入拉格朗日乘子 $%5Clambda%2Cv$ ，我们构造另一个函数： $L(x%2C%5Clambda%2Cv)%3Df_0(x)%2B%20%5Cdisplaystyle%20%5Csum%5Em_%7Bi%3D1%7D%5Clambda_i%20f_i(x)%20%2B%20%5Cdisplaystyle%5Csum%5En_%7Bi%3D1%7D%20v_i%20h_i(x)$ ，其中 $%5Clambda_i%20%5Cgeq%200$ 。显然，当 $x$ 满足原问题的约束时，函数 $L(x%2C%5Clambda%2Cv)%20%5Cleq%20f_0(x)$ 。因此，我们找到了一个恒小于等于原优化目标的函数，继续考虑使用此函数去逼近原优化目标。

要用一个较小的函数逼近较大的函数，显然应当去极大化它。记 $J_1(x)%20%3D%20max_%7B%5Clambda%20%5Cgeq%200%2C%20v%7D%20L(x%2C%5Clambda%2Cv)$ 。当 $x$ 满足原问题的约束时，我们取 $%5Clambda_i%20%3D%200$ ，则此时 $J_1(x)%20%3D%20f_0(x)$ ；当 $x$ 不满足原问题的约束时，我们不妨假设存在某个 $i$ ，使得 $f_i(x)%20%3E%200$ ，令 $%5Clambda_i%20%5Cto%20%2B%5Cinfty$ ，则此时 $J_1(x)%20%3D%20%2B%5Cinfty$ 。因此， $J_1(x)$ 可以写为如下形式：

$J_1(x)%20%3D%20%5Cbegin%7Bcases%7D%20f_0(x)%EF%BC%8Cx%E6%BB%A1%E8%B6%B3%E5%8E%9F%E9%97%AE%E9%A2%98%E7%BA%A6%E6%9D%9F%E6%9D%A1%E4%BB%B6%5C%5C%20%2B%20%5Cinfty%EF%BC%8Celse%20%5Cend%7Bcases%7D$

显然， $min_x%20J_1(x)$ 和 $min_x%20f_0(x)$ 是等价的。基于上述讨论，我们将带有约束条件的原问题转化为了一个不带约束条件的优化问题。

1.3 构造对偶问题（无约束的凸函数最小化问题）

考虑构造另一个函数 $J_2(%5Clambda%2Cv)%20%3D%20min_x%20L(x%2C%5Clambda%2Cv)%20%3D%20min_x%20%5Cbigg(%20f_0(x)%2B%20%5Cdisplaystyle%20%5Csum%5Em_%7Bi%3D1%7D%5Clambda_i%20f_i(x)%20%2B%20%5Cdisplaystyle%5Csum%5En_%7Bi%3D1%7D%20v_i%20h_i(x)%20%5Cbigg)$ 。可以证明， $J_2(%5Clambda%2Cv)$ 是关于 $(%5Clambda%2Cv)$ 的凹函数。

实际上，对于任何形如 $h(y)%3Dmin_x%20g(x%2Cy)%20$ 的函数，若 $g(x%EF%BC%8Cy)$ 关于 $y$ 的阶次为1（给定 $x%3Dx_0$ ， $g(x_0%EF%BC%8Cy)$ 为关于 $y$ 的线性函数），则函数 $h(y)$ 是关于 $y$ 的凹函数。
相对应的，对于任何形如 $h(y)%3Dmax_x%20g(x%2Cy)%20$ 的函数，若 $g(x%EF%BC%8Cy)$ 关于 $y$ 的阶次为1，则函数 $h(y)$ 是关于 $y$ 的凸函数。
从直观上去理解，假设 $x%20%5Cin%20%5C%7Bx_1%2C%20x_2%2C%20...%2C%20x_n%5C%7D$ ，对于每个 $x_i$ ，都有一个关于 $y$ 的线性函数 $h_i(y)%3Dg(x_i%2Cy)$ 。对于每一个给定的 $y_0$ ，令 $h(y_0)%3Dmin%20%5C%7Bh_1(y_0)%2C%20h_2(y_0)%2C%20...%2C%20h_n(y_0)%5C%7D$ ，得到的就是所求的 $h(y)$ 。不难发现， $h(y)$ 是关于 $y$ 的凹的分段线性函数。

构造优化问题 $max_%7B%5Clambda%20%5Cgeq%200%2Cv%7D%20J_2(%5Clambda%2Cv)$ ，我们称它为原问题的对偶问题。显然，这是一个无约束的、最大化凹函数的问题，它等价于最小化一个无约束的凸函数。

至此，我们从原问题出发，构造了一个无约束的最小化凸函数问题。

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

结论：对偶问题的最优解≤原问题的最优解，

$d%5E*%20%3D%20max_%7B%5Clambda%20%5Cgeq%200%2Cv%7D%20J_2(%5Clambda%2Cv)%3Dmax_%7B%5Clambda%20%5Cgeq%200%2Cv%7D%20min_x%20L(x%2C%5Clambda%2Cv)%20%5Cleq%20min_xmax_%7B%5Clambda%20%5Cgeq%200%2Cv%7DL(x%2C%5Clambda%2Cv)%20%3D%20min_x%20J_1(x)%20%3D%20p%5E*$

证明过程利用了如下结论：
对于任意函数 $f(x%2Cy)$ ，均有 $max_x%20min_y%20f(x%2Cy)%20%5Cleq%20min_y%20max_x%20f(x%2Cy)$
直观理解：“所有最大值里面的最小值”要大于“所有最小值里面的最大值”。
证明：记 $p(y)%20%3D%20max_x%20f(x%2Cy)%20%5Cgeq%20f(x%2Cy)%2C%5Cforall%20x$ ；
记 $q(x)%20%3D%20min_y%20f(x%2Cy)%20%5Cleq%20f(x%2Cy)%2C%5Cforall%20y$ ；
记 $y%5E*%3Dargmin_yp(y)%EF%BC%8Cx%5E*%3Dargmax_xq(x)$ ；
则有 $min_y%20max_x%20f(x%2Cy)%20%3D%20p(y%5E*)%5Cgeq%20f(x%5E*%2Cy%5E*)%20%5Cgeq%20q(x%5E*)%3Dmax_x%20min_y%20f(x%2Cy)%20$ ，证毕

上述结论就是“弱对偶性”——对于任何上述形式的问题，对偶问题的最优解小于等于原问题的最优解。

1.5 KKT条件

$%5Cdisplaystyle%7B(1)f_i(x)%20%5Cleq%200%2Ci%3D1%2C...%2Cm%5Cquad(%E5%8E%9F%E5%A7%8B%E4%B8%8D%E7%AD%89%E5%BC%8F%E7%BA%A6%E6%9D%9F)%5C%5C%20(2)h_i(x)%20%3D%200%2C%20i%20%3D1%2C...%2Cn%5Cquad(%E5%8E%9F%E5%A7%8B%E7%AD%89%E5%BC%8F%E7%BA%A6%E6%9D%9F)%5C%5C%20(3)%5Clambda_i%20%5Cgeq%200%2Ci%3D1%2C...%2Cm%5Cquad(%E9%9D%9E%E8%B4%9F%E6%80%A7)%5C%5C%20(4)%5Clambda_i%5E*%20*%20f_i(x%5E*)%3D0%2Ci%3D1%2C...%2Cm%5Cquad(%E4%BA%92%E8%A1%A5%E6%9D%BE%E5%BC%9B%E6%80%A7)%5C%5C%20(5)%5Cnabla%20f_0(x%5E*)%2B%20%5Cdisplaystyle%20%5Csum%5Em_%7Bi%3D1%7D%20%5Clambda_i%5E*%20%5Cnabla%20f_i(x%5E*)%20%2B%20%5Cdisplaystyle%5Csum%5En_%7Bi%3D1%7D%20v_i%5E*%20h_i(x%5E*)%3D0%5Cquad(x%5E*%E6%98%AFL%E7%9A%84%E5%B9%B3%E7%A8%B3%E7%82%B9)%5C%5C%7D$ $$

对于一般性优化问题（ $f_0(x)$ 为一般函数）：

KKT是原问题转化为对偶优化问题的必要条件；
原问题准则函数和对偶准则函数的极值点通常不一致。

对于凸优化问题（ $f_0(x)$ 为凸函数）：

满足KKT条件的点，那么它们分别是原问题准则函数和对偶准则函数的极值点并且 strong duality成立（ $d%5E*%20%3D%20p%5E*$ )

2 支持向量机（SVM）

这部分内容会发在拉格朗日对偶问题与支持向量机学习笔记（2）中

标签：SVM 支持向量机拉格朗日对偶优化模型