## General Polynomial Time Decomposition Algorithms

** Nikolas List, Hans Ulrich Simon**; 8(Feb):303--321, 2007.

### Abstract

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 *k _{0}*
equality constraints for some fixed constant

*k*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

_{0}*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).

[abs][pdf]