拉格朗日對偶問題與支持向量機學習筆記(1)

2023-02-27 15:40 作者:ZJU前校長-吳朝暉院士 0人讀過 | 我要投稿

0?前言

這兩部分內(nèi)容在之前學凸優(yōu)化和數(shù)據(jù)挖掘課的時候就學過了，奈何當時課上全在摸魚，導致現(xiàn)在要用的時候啥也不會。于是在各種論壇上看別人的筆記，奈何自己實在過于愚笨，很多地方花了很多時間才理解。為了加深自己的印象以及練習一下剛學的markdown，還是寫個專欄記錄一下自己的學習成果。（不過我不得不說b站專欄對markdown的支持真的太差了，即使使用了相關插件，很多公式也無法識別；此外，由于b站專欄最多只能插入包括公式在內(nèi)的100張圖片，我不得不把這篇文章拆成兩部分才能發(fā)出來，真是呃呃了）。

本文參考了“https://blog.csdn.net/weixin_44378835/article/details/110732412?utm_source%20=%20app”這篇博文和其他一些博文，進行了一定的縮減，在部分地方添加了自己的想法和更詳細的推導過程。

1?拉格朗日對偶問題

1.1?原問題

給出如下的優(yōu)化問題：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? $%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$ 的線性組合。我們稱這個問題為“原問題”。

在求解原問題的時候，我們會遇到兩個不喜歡的東西：①帶有約束條件②優(yōu)化目標不一定是凸函數(shù)。因此，我們希望通過轉化的方式將原問題變成一個沒有約束條件的凸問題，這也是引入拉格朗日乘子法以及構造拉格朗日對偶問題的原因。

1.2?消除約束條件

通過引入拉格朗日乘子 $%5Clambda%2Cv$ ，我們構造另一個函數(shù)： $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$ 滿足原問題的約束時，函數(shù) $L(x%2C%5Clambda%2Cv)%20%5Cleq%20f_0(x)$ 。因此，我們找到了一個恒小于等于原優(yōu)化目標的函數(shù)，繼續(xù)考慮使用此函數(shù)去逼近原優(yōu)化目標。

要用一個較小的函數(shù)逼近較大的函數(shù)，顯然應當去極大化它。記 $J_1(x)%20%3D%20max_%7B%5Clambda%20%5Cgeq%200%2C%20v%7D%20L(x%2C%5Clambda%2Cv)$ 。當 $x$ 滿足原問題的約束時，我們?nèi)?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=%5Clambda_i%20%3D%200" alt="%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)$ 是等價的?；谏鲜鲇懻摚覀儗в屑s束條件的原問題轉化為了一個不帶約束條件的優(yōu)化問題。

1.3?構造對偶問題（無約束的凸函數(shù)最小化問題）

考慮構造另一個函數(shù) $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)$ ?？梢宰C明， $J_2(%5Clambda%2Cv)$ 是關于 $(%5Clambda%2Cv)$ 的凹函數(shù)。

實際上，對于任何形如 $h(y)%3Dmin_x%20g(x%2Cy)%20$ 的函數(shù)，若 $g(x%EF%BC%8Cy)$ 關于 $y$ 的階次為1（給定 $x%3Dx_0$ ， $g(x_0%EF%BC%8Cy)$ 為關于 $y$ 的線性函數(shù)），則函數(shù) $h(y)$ 是關于 $y$ 的凹函數(shù)。
相對應的，對于任何形如 $h(y)%3Dmax_x%20g(x%2Cy)%20$ 的函數(shù)，若 $g(x%EF%BC%8Cy)$ 關于 $y$ 的階次為1，則函數(shù) $h(y)$ 是關于 $y$ 的凸函數(shù)。
從直觀上去理解，假設 $x%20%5Cin%20%5C%7Bx_1%2C%20x_2%2C%20...%2C%20x_n%5C%7D$ ，對于每個 $x_i$ ，都有一個關于 $y$ 的線性函數(shù) $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)$ 。不難發(fā)現(xiàn)， $h(y)$ 是關于 $y$ 的凹的分段線性函數(shù)。

構造優(yōu)化問題 $max_%7B%5Clambda%20%5Cgeq%200%2Cv%7D%20J_2(%5Clambda%2Cv)$ ，我們稱它為原問題的對偶問題。顯然，這是一個無約束的、最大化凹函數(shù)的問題，它等價于最小化一個無約束的凸函數(shù)。

至此，我們從原問題出發(fā)，構造了一個無約束的最小化凸函數(shù)問題。

1.4?原問題和對偶問題的關系

結論：對偶問題的最優(yōu)解≤原問題的最優(yōu)解，

$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*$

證明過程利用了如下結論：
對于任意函數(shù) $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$ ，證畢

上述結論就是“弱對偶性”——對于任何上述形式的問題，對偶問題的最優(yōu)解小于等于原問題的最優(yōu)解。

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$ $$

對于一般性優(yōu)化問題（ $f_0(x)$ 為一般函數(shù)）：

KKT是原問題轉化為對偶優(yōu)化問題的必要條件；
原問題準則函數(shù)和對偶準則函數(shù)的極值點通常不一致。

對于凸優(yōu)化問題（ $f_0(x)$ 為凸函數(shù)）：

滿足KKT條件的點，那么它們分別是原問題準則函數(shù) 和對偶準則函數(shù)的極值點并且 strong duality成立（ $d%5E*%20%3D%20p%5E*$ )

2?支持向量機（SVM）

這部分內(nèi)容會發(fā)在拉格朗日對偶問題與支持向量機學習筆記（2）中

標簽：SVM 支持向量機拉格朗日對偶優(yōu)化模型

最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频