Editing Support vector machine (section)

=== Dual ===
By solving for the [[Duality (optimization)|Lagrangian dual]] of the above problem, one obtains the simplified problem

<math display="block"> \begin{align}
&\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(\mathbf{x}_i^\mathsf{T} \mathbf{x}_j)y_j c_j, \\
&\text{subject to } \sum_{i=1}^n c_iy_i = 0,\,\text{and } 0 \leq c_i \leq \frac{1}{2n\lambda}\;\text{for all }i.
\end{align}</math>

This is called the ''dual'' problem. Since the dual maximization problem is a quadratic function of the <math> c_i</math> subject to linear constraints, it is efficiently solvable by [[quadratic programming]] algorithms.

Here, the variables <math> c_i</math> are defined such that

<math display="block"> \mathbf{w} = \sum_{i=1}^n c_iy_i \mathbf{x}_i.</math>

Moreover, <math> c_i = 0</math> exactly when <math> \mathbf{x}_i</math> lies on the correct side of the margin, and <math> 0 < c_i <(2n\lambda)^{-1}</math>  when <math> \mathbf{x}_i</math> lies on the margin's boundary. It follows that <math>\mathbf{w}</math> can be written as a linear combination of the support vectors.

The offset, <math> b</math>, can be recovered by finding an <math> \mathbf{x}_i</math> on the margin's boundary and solving
<math display="block"> y_i(\mathbf{w}^\mathsf{T} \mathbf{x}_i - b) = 1 \iff b = \mathbf{w}^\mathsf{T} \mathbf{x}_i - y_i .</math>

(Note that <math>y_i^{-1}=y_i</math> since <math>y_i=\pm 1</math>.)