|
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 ε of optimality grows linearly with 1/ε 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 k0 equality constraints for some
fixed constant k0 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 (2003) 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 convergence results by List and Simon
(2004) and Simon (2004) by providing convergence rates (and
by holding under more general conditions).
|
