Sequential minimal optimization
Sequential minimal optimization (SMO) is an algorithm for solving the constrained quadratic programming problem that arises when training a support-vector machine. It decomposes the full optimization problem into subproblems containing two Lagrange multipliers, each of which can be solved analytically. Repeated solutions of these subproblems produce a sequence of feasible dual points that approaches an optimum under the standard assumptions used for support-vector classification.
SMO was introduced by John Platt in 1998 as an alternative to applying a general-purpose quadratic-programming package to the entire support-vector-machine dual. Its defining feature is the use of the smallest working set compatible with the dual equality constraint. The method therefore avoids constructing or factorizing the complete kernel matrix, although practical implementations ordinarily retain portions of that matrix in a cache.
Optimization problem
For a binary training set consisting of pairs ((x_i,y_i)), where (y_i\in{-1,+1}), the soft-margin support-vector-machine dual has the form
[ \max_{\boldsymbol{\alpha}} W(\boldsymbol{\alpha})
\sum_{i=1}^{n}\alpha_i
\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i\alpha_j y_i y_j K(x_i,x_j), ]
subject to
[ 0\leq \alpha_i\leq C ]
and
[ \sum_{i=1}^{n}\alpha_i y_i=0. ]
Here, (K(x_i,x_j)) is a positive-semidefinite kernel, while (C) controls the penalty assigned to margin violations. The dual variables determine the resulting decision function,
[ f(x)=\sum_{i=1}^{n}\alpha_i y_i K(x_i,x)+b, ]
where (b) is the intercept. Training consists of finding a feasible multiplier vector that maximizes (W), or equivalently minimizes the corresponding convex quadratic objective.
Changing a single multiplier would ordinarily violate the equality constraint. SMO consequently changes two multipliers at a time, making a pair the smallest nontrivial feasible working set. If the selected indices are (i) and (j), their updates satisfy
[ y_i\alpha_i+y_j\alpha_j
y_i\alpha_i^{\mathrm{old}} + y_j\alpha_j^{\mathrm{old}}. ]
This relation reduces the two-variable subproblem to optimization along a line segment. The endpoints of that segment follow from the box constraints and depend on whether (y_i) and (y_j) have equal labels.
Analytical pair update
For a selected pair, the unconstrained update is determined by the prediction errors
[ E_i=f(x_i)-y_i \qquad\text{and}\qquad E_j=f(x_j)-y_j. ]
The local curvature along the feasible direction is commonly written as
[ \eta
K(x_i,x_i)+K(x_j,x_j)-2K(x_i,x_j). ]
When (\eta>0), the provisional update for the second multiplier is
[ \alpha_j^{\mathrm{new,unc}}
\alpha_j^{\mathrm{old}} + \frac{y_j(E_i-E_j)}{\eta}. ]
The result is clipped to the feasible interval ([L,H]). The first multiplier is then recovered from the equality constraint:
[ \alpha_i^{\mathrm{new}}
\alpha_i^{\mathrm{old}} + y_i y_j \left( \alpha_j^{\mathrm{old}}
\alpha_j^{\mathrm{new}} \right). ]
A nonpositive value of (\eta) can occur when the kernel matrix is only semidefinite or when two mapped observations coincide. In that case, implementations compare the dual objective at the feasible endpoints rather than dividing by the curvature. The selected endpoint must still provide sufficient objective improvement before the pair update is accepted.
After an accepted update, the intercept is recalculated from the Karush–Kuhn–Tucker conditions. If either updated multiplier lies strictly between zero and (C), its corresponding equality supplies an intercept value directly. When both multipliers lie on constraint boundaries, implementations commonly use a value derived from the two boundary-consistent estimates.
Working-set selection
The analytical update does not determine which pair should be optimized. Working-set selection therefore accounts for much of the practical behavior of SMO. A multiplier is eligible for attention when its current state violates the KKT conditions by more than the numerical tolerance used by the implementation.
The original selection heuristic gives priority to a violating multiplier that is not fixed at a box boundary. It then seeks a second multiplier whose error differs substantially from the first multiplier’s error, because a large value of (\lvert E_i-E_j\rvert) often produces a correspondingly large step. If that choice does not improve the objective, the search expands through the remaining non-bound multipliers and subsequently through the full training set.
Later analysis by S. Sathiya Keerthi, Shirish Shevade, Chiranjib Bhattacharyya, and K. R. K. Murthy clarified the relationship between working-set selection, stopping tests, and convergence. Their modified selection rules used more explicit measures of KKT violation and reduced dependence on the traversal order of the training observations. Subsequent second-order selection methods incorporated local curvature into estimates of objective reduction rather than relying only on error differences.
The algorithm terminates when no pair satisfying the chosen violation criterion can produce a material feasible update. This stopping condition is numerical rather than symbolic, because floating-point arithmetic rarely produces exact satisfaction of every KKT equality. The tolerance consequently defines the precision of the computed dual solution.
Convergence
SMO is a specialized decomposition method for convex quadratic optimization. Each accepted pair update preserves primal-dual feasibility with respect to the equality and box constraints, while the exact solution of the pair subproblem prevents deterioration of the dual objective. Since the dual objective is bounded above, the resulting objective sequence converges.
Convergence to an optimal solution additionally depends on the working-set rule continuing to select variables associated with unresolved KKT violations. A heuristic that permanently excludes an eligible multiplier can stall at a nonoptimal feasible point even though every performed pair update is exact. Convergent variants therefore combine preferred selections with a fallback scan capable of reconsidering the full multiplier set.
The optimum need not have a unique multiplier representation when the kernel matrix is singular. In that circumstance, the algorithm can converge to one member of a set of dual optima, all of which have the same objective value. The associated classifier can nevertheless remain unique over the span relevant to the training data.
Computational characteristics
A pair update requires only a small number of kernel evaluations when the relevant matrix entries are already cached. Memory use is therefore governed mainly by the training vectors, the multiplier and error arrays, and the selected kernel-cache capacity. This differs from methods that explicitly store the complete (n\times n) kernel matrix, whose storage requirement grows quadratically with the number of observations.
The total running time is not fixed by the constant size of an individual subproblem. It depends on how many pair updates are required, how effectively the working-set rule identifies productive directions, and how frequently kernel values must be recomputed after cache eviction. Data geometry also affects the number of support vectors and the conditioning of the dual objective.
A cache-aware tie-breaking rule introduced by You Watanabe in 2001 selected among equally ranked admissible pairs by estimating which candidate required fewer uncached kernel evaluations. The rule left the dual subproblem and the KKT stopping criterion unchanged, but it altered the deterministic traversal of tied working sets. It was used principally in implementations whose kernel caches were small relative to the training set.
Error caching provides a related reduction in repeated computation. After a successful pair update, cached errors can be adjusted using the two changed coefficients and the intercept displacement. Maintaining every error exactly requires work proportional to the number of cached training points, whereas partial-cache designs defer some error evaluations until the corresponding observations are reconsidered.
Relationship to support-vector-machine solvers
SMO denotes the two-variable decomposition principle rather than a single immutable implementation. Support-vector-machine packages differ in their working-set criteria, shrinking policies, cache replacement rules, and numerical stopping tests while retaining the same underlying dual structure.
Shrinking temporarily removes variables that appear unlikely to leave their current bounds. This can reduce the active problem substantially, although a final reconstruction is required to verify that the excluded variables satisfy the global optimality conditions. Second-order working-set rules instead attempt to improve progress per update by combining violation magnitude with curvature information.
For a linear kernel, specialized linear classifier solvers can operate directly on the weight vector and may avoid the kernel-cache considerations central to SMO. The decomposition framework remains relevant for nonlinear kernels because the classifier is represented through pairwise kernel evaluations rather than an explicit finite-dimensional parameter vector.