Nikolas List, Hans U. Simon A General Convergence Theorem for the Decomposition
Method Proceedings of the 17th Annual Conference on
Computational Learning Theory, 363-377, 2004.
Abstract
The decomposition method is currently one of the major methods
for solving the convex quadratic optimization problems being
associated with support vector machines. Although there exist
some versions of the method that are known to converge to an
optimal solution, the general convergence properties of the
method are not yet fully understood. In this paper, we present
a variant of the decomposition method that basically converges
for any convex quadratic optimization problem provided that
the policy for working set selection satisfies three abstract
conditions. We furthermore design a concrete policy that meets
these requirements.
