サポートベクターマシン
次のような双対形式に帰着することができる。
maximize f ( c 1 ... c n ) = ∑ i = 1 n c i − 1 2 ∑ i = 1 n ∑ j = 1 n y i c i ( x i T x j ) y j c j , {\displaystyle {\text{maximize}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}({\boldsymbol {x}}_{i}^{T}{\boldsymbol {x}}_{j})y_{j}c_{j},}
subject to ∑ i = 1 n c i y i = 0 , and 0 ≤ c i ≤ 1 2 n λ for all i . {\displaystyle {\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.}
双対形式の最大化問題は、線形制約を前提とした c i {\displaystyle c_{i}} の二次関数であり、二次計画法のアルゴリズムで効率的に解くことができる。
ここで、 c i {\displaystyle c_{i}} は次のように定義される。
w = ∑ i = 1 n c i y i x i {\displaystyle {\boldsymbol {w}}=\sum _{i=1}^{n}c_{i}y_{i}{\boldsymbol {x}}_{i}} .
"Minimize ‖ w ‖ {\displaystyle \|{\boldsymbol {w}}\|} subject to y i ( w T x i − b ) ≥ 1 {\displaystyle y_{i}({\boldsymbol {w}}^{T}{\boldsymbol {x}}_{i}-b)\geq 1} for i = 1 , ... , n {\displaystyle i=1,\ldots ,n} ."
これを解いて得られる w {\displaystyle {\boldsymbol {w}}} と b {\displaystyle b} を用いて、分類器 x ↦ sgn  ( w T x − b ) {\displaystyle {\boldsymbol {x}}\mapsto \operatorname {sgn}({\boldsymbol {w}}^{T}{\boldsymbol {x}}-b)} を決定することができる。ここで、 sgn  ( ⋅ ) {\displaystyle \operatorname {sgn}(\cdot )} は符号関数である。
この幾何学的記述から、最大マージン超平面は、それと最も近い位置にある x i {\displaystyle {\boldsymbol {x}}_{i}} によって定まるという重要な帰結が得られる。 x i {\displaystyle {\boldsymbol {x}}_{i}} をサポートベクターと呼ぶ。