逐次最小問題最適化法
アルゴリズムは次のように進行する:
最適化問題のKKT条件を破るラグランジュ乗数 α 1 {\displaystyle \alpha _{1}} を見つける。
第2の乗数 α 2 {\displaystyle \alpha _{2}} を選び、組 ( α 1 , α 2 ) {\displaystyle (\alpha _{1},\alpha _{2})} を最適化する。
収束するまでステップ1、2を繰り返す。
すべてのラグランジュ乗数がKKT条件を十分に満たすとき、全体の最適化が終了する。このアルゴリズムは収束することが保証されている。しかし、データセットが大きくなると、組 ( α 1 , α 2 ) {\displaystyle (\alpha _{1},\alpha _{2})} の選び方が O ( n 2 ) {\displaystyle O(n^{2})} で大きくなるので、より速く収束させるために、部分問題を構成する変数を選び出すためのヒューリスティックを使うことが重要となる。