SVM原始問題：$wx$

minlimits_{w,b} frac{1}{2}{||w||}^{2} s.t. |wx_i+b|geq 1 , i=1,2,...,N

定義L（w，α）= frac{1}{2}{||w||}^{2}-alpha(sum_{1}^{N}{|wx_i+b|-1}) ，其中α≥0，

當對所有i， |wx_i+b|geq 1 時（以下間寫為 |wx+b|geq 1 ）， maxlimits_{alpha} L（w，α）= frac{1}{2}{||w||}^{2} ；當某個約束 |wx_i+b|< 1 時，令對應的α取+∞，其他的α取0，L（w，α）的極大值即可取+∞。

則SVM原問題（帶約束 |wx+b|geq 1 的極小值問題）可表示為 minlimits_{w,b}maxlimits_{alpha} L（w，α）（無約束 |wx+b|geq 1 ，但有約束α≥0的極小-極大問題。換句話說在α≥0的約束條件下，如果有某個 |wx_i+b|< 1 ，α可以通過趨於+∞使得 maxlimits_{alpha} L（w，α）趨於+∞，從而 minlimits_{w,b}maxlimits_{alpha}L（w，α） 沒辦法取最小值，即α≥0的約束條件就包含了 |wx+b|geq 1 的約束條件）。

其對偶問題即為極大-極小問題：

maxlimits_{alpha}minlimits_{w,b} L（w，α）。

上述過程即為Lagrange對偶法導出的對偶問題。

補充：

1.在原始問題轉為極小-極大問題時，為什麼不直接解極大-極小問題而要解對偶問題？

因為約束α≥0的存在，極小-極大問題的內層極大問題不方便求解，轉為極大-極小問題後內層極小問題無約束，可以通過最優性條件求解。

2.對偶問題中的解（w*，b*，α*）也是原問題的解嗎？

強對偶定理告訴我們要滿足一定的約束規格（constraint qualifications）/正則條件（regularity conditions）時，對偶問題的解也是原問題的解。參見Karush-Kuhn-Tucker conditions。

常用的約束規格有兩個：

線性約束規格：約束函數都是線性的（《數據挖掘中的新方法——支持向量機》）；

Slater條件：對於凸優化問題，存在使得不等式約束嚴格取不等號的點，稱之為嚴格可行點。（大多數博客文章提到的條件）

Slater條件還有個改良的版本，當某些不等式約束是線性的時候，這些不等式約束不必要求能嚴格取不等號（Convex Optimization – Boyd and Vandenberghe）。

推薦閱讀：

相关文章