柴夥說算法（5）-對偶

Nothing is more practical than a good theory.

--Vladimir N. Vapnik

對偶算法的目的是將原問題轉化爲相應的對偶問題，並求解對偶問題的解，如果對偶問題的解和原問題的解等價的話，那麼就得到了原問題的解。這裏需要說明兩點，一，要求對偶問題的求解比原問題求解簡單；二，對偶問題的解和原問題的解等價不一定成立，但是很多情況下，對偶問題的解是原問題解的一個很好逼近。

什麼時候存在對偶呢？對偶這個詞最早出現在高等代數中的線性空間和對偶線性算子空間中，當時是一個很懵圈的概念，現在多少亦然。算法中常見的對偶主要有以下幾種：在圖論中，用於地圖着色中的點着色和面着色，這裏點和面構成對偶關係；在幾何中，和在圖論中相類似，廣泛應用於有限元三角網格生成中的Delaunay三角剖分算法中的三角形邊的中垂線的交點組成的多邊形和原三角形之間構成對偶關係；優化領域中，使用Lagrange乘子法，將一個極小極大的原問題轉化爲它的對偶問題：極大極小的優化問題，一般而言，這裏對偶問題的解和原問題的解之間不相等，它們之間的差距稱爲間隙。

參考資料：

[1] 屈婉玲等著，離散數學（第四版），Chap 8， 清華大學出版社，2012年

[2] https://en.wikipedia.org/wiki/Delaunay_triangulation

[3] 李航著，統計學習方法，附錄C：拉格朗日對偶性，清華大學出版社，2012年

[4] https://www.zhihu.com/question/58584814