逐次最小問題最適化法（英: Sequential Minimal Optimization, SMO）はサポートベクターマシン (SVM) の訓練で生じる2次計画問題 (QP) を解くためのアルゴリズムである。1998年にマイクロソフトリサーチのJohn Platt（英語版）によって発明された[1]。SMOはサポートベクターマシンの訓練のために広く使われ、人気のLIBSVMツールによって実装される[2][3]。以前から利用できたSVM訓練法はより一層複雑で、高価なサードパーティーのQPソルバーを必要としたので、1998年のSMOアルゴリズムの公表はSVMコミュニティでたくさんの興奮を引き起こした[4]。
データセット (x1, y1), ..., (xn, yn) に関する二項分類問題を考える。ここで xi は入力ベクトル、yi ∈ {-1, +1} はそれに対応する2値ラベルである。ソフトマージンサポートベクターマシンは以下の双対問題で表される2次計画問題を解くことによって訓練される:
max α ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n y i y j K ( x i , x j ) α i α j , {\displaystyle \max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j},}
ただし
0 ≤ α i ≤ C , for i = 1 , 2 , … , n , {\displaystyle 0\leq \alpha _{i}\leq C,\quad {\mbox{ for }}i=1,2,\ldots ,n,}
∑ i = 1 n y i α i = 0 {\displaystyle \sum _{i=1}^{n}y_{i}\alpha _{i}=0}
ここで C は SVM hyperparameter、K(xi, xj) はカーネル関数（英語版）で、どちらもユーザが与える。変数 α i {\displaystyle \alpha _{i}} はラグランジュ乗数である。
SMOは上記の最適化問題を解くための反復型アルゴリズムである。SMOはこの問題をその時解析的に解かれる一連の最小の可能な部分問題に分割する。ラグランジュ乗数 α i {\displaystyle \alpha _{i}} を伴う線形等式制約のため、最小の可能な問題はそのような2つの乗数を含む。そして、任意の2つの乗数 α 1 {\displaystyle \alpha _{1}} 、 α 2 {\displaystyle \alpha _{2}} について、次の制約に分解される:
0 ≤ α 1 , α 2 ≤ C , {\displaystyle 0\leq \alpha _{1},\alpha _{2}\leq C,}
y 1 α 1 + y 2 α 2 = k , {\displaystyle y_{1}\alpha _{1}+y_{2}\alpha _{2}=k,}
k {\displaystyle k} は前述の和の等式より導かれる定数である。そしてこの問題は解析的に解くことができる。
アルゴリズムは次のように進行する:
すべてのラグランジュ乗数がKKT条件を十分に満たすとき、全体の最適化が終了する。このアルゴリズムは収束することが保証されている。しかし、データセットが大きくなると、組 ( α 1 , α 2 ) {\displaystyle (\alpha _{1},\alpha _{2})} の選び方が O ( n 2 ) {\displaystyle O(n^{2})} で大きくなるので、より速く収束させるために、部分問題を構成する変数を選び出すためのヒューリスティックを使うことが重要となる。