為什麼支持向量機要用拉格朗日對偶演算法來解最大化間隔問題？

01-11

為什麼不直接解關於最大化間隔的凸二次規劃問題，而要轉成拉格朗日對偶求解呢？

並不一定要用拉格朗日對偶。

要注意用拉格朗日對偶並沒有改變最優解，而是改變了演算法複雜度：

在原問題下，求解演算法的複雜度與樣本維度（等於權值w的維度）有關；

而在對偶問題下，求解演算法的複雜度與樣本數量（等於拉格朗日運算元a的數量）有關。

因此，如果你是做線性分類，且樣本維度低於樣本數量的話，在原問題下求解就好了，Liblinear之類的線性SVM默認都是這樣做的；

但如果你是做非線性分類，那就會涉及到升維（比如使用高斯核做核函數，其實是將樣本升到無窮維），升維後的樣本維度往往會遠大於樣本數量，此時顯然在對偶問題下求解會更好。

原本用QP就可以了，不過用Langrange Dual的話第一可以減少演算法複雜度，第二在之後引入不同的kernel時從數學上講更加自然。

線性情況下用 SGD 就可以了，適合處理海量數據。

這樣：

就可以由求特徵向量w轉化為求比例係數a，

就可以導出含有內積形式的目標函數，

就可以實現對內積後的gram矩陣使用核函數，以達到非線性分類的目的。

簡而言之，就是以上。

有人回復：嗯，這是為了方便引入核函數。如果是線性可分問題，那麼直接用一般解QP問題的方法是否更好？

個人意見：支持向量機實現非線性的方法的數學本質是升維，升維升到無窮維你還怎麼表達那個w？所以還是使用拉格朗日對偶方法更好一點。準確的說，可以用一些優化演算法直接求最小間距，但是，升維的時候核要是正定的，且升維可數，而且不是很大的時候可以用。不建議這麼搞。

不邀自來，從兩個方面來回答這個問題吧。

1) 不等式約束一直是優化問題中的難題，求解對偶問題可以將支持向量機原問題約束中的不等式約束轉化為等式約束；

2) 支持向量機中用到了高維映射，但是映射函數的具體形式幾乎完全不可確定，而求解對偶問題之後，可以使用核函數來解決這個問題。

以上。

大概是不等式下求極值的優選吧。