We present a general decomposition algorithm that is uniformly
applicable to every (suitably normalized) instance of Convex
Quadratic Optimization and efficiently approaches an optimal
solution. The number of iterations required to be within $\ve$
of optimality grows linearly with $1/\ve$ and quadratically
with the number m of variables. The working set selection can be
performed in polynomial time. If we restrict our considerations
to instances of Convex Quadratic Optimization with at most $k_0$
equality constraints for some fixed constant $k_0$ plus some
so-called box-constraints (conditions that hold for most
variants of SVM-optimization), the working set is found in linear
time. Our analysis builds on a generalization of the concept
of rate certifying pairs that was introduced by Hush and Scovel.
In order to extend their results to arbitrary instances of Convex
Quadratic Optimization, we introduce the general notion of a rate
certifying q-set. We improve on the results by Hush and Scovel in
several ways. First our result holds for Convex Quadratic
Optimization whereas the results by Hush and Scovel are specialized to
SVM-optimization. Second, we achieve a higher rate of convergence
even for the special case of SVM-optimization (despite the generality
of our approach). Third, our analysis is technically simpler.
We prove furthermore that the strategy for working set selection which
is based on rate certifying sets coincides with a strategy which is
based on a so-called ``sparse witness of sub-optimality''. Viewed from
this perspective, our main result improves on older convergence results
by List and Simon by providing convergence rates (and by holding under
more general conditions).
