for a wide class of QP problems. Their theoretical polynomial convergence ($O(n\log \frac{1}{\epsilon})$) was first established by Mizuno [@mizuno1994]. In addition, Andersen [*et al*]{} [@Andersen1996implement] showed that the number of iterations needed by IPMs to converge is $O(\log n)$, which demonstrates that their computational effort increases in a slower rate than the size of the problem.

Both the primal and the dual SVM are QP problems. The primal formulation of SVM [@vapnik2000nature] is defined as $$\begin{aligned}
  \textrm{(SVM-P)} \qquad   \min_{{\textbf{w}},b,\xi,{\textbf{s}}} && \frac{1}{2}{\textbf{w}}^T{\textbf{w}}+ c{\textbf{e}}^T\xi \\
  \qquad s.t. && y_i({\textbf{w}}^T{\textbf{x}_i}- b) + \xi_i - s_i = 1, i=1,\dots,N, \\
  && {\textbf{s}}\geq 0, \xi \geq 0.\end{aligned}$$ whereas the dual SVM has the form $$\begin{aligned}
  \textrm{(SVM-D)} \quad \min_{\alpha} && \frac{1}{2}\alpha^TQ\alpha - {\textbf{e}}^T\alpha \\
  s.t. && {\textbf{y}}^T\alpha = 0, \quad \mbox{and} \quad 0 \leq \alpha_i \leq c, \quad i = 1,\cdots,N,\end{aligned}$$ where $Q_{ij} = y_iy_j{\textbf{x}_i}^T{\textbf{x}_j}= \bar{X}\bar{X}^T$. By considering the KKT conditions of (SVM-P) and (SVM-D), the optimal solution is given by ${\textbf{w}}= \bar{X}^T\alpha = \sum_{i\in SV}\alpha_i y_i {\textbf{x}_i}$, where $SV$ is the set of sample indices corresponding to the support vectors. The optimal bias term $b$ can be computed from the complementary slackness condition $\alpha_i(y_i({\textbf{x}_i}^T{\textbf{w}}+ b)-1 + \xi_i) = 0$.

Whether to solve (SVM-P) or (SVM-D) 