  We consider coordinate descent methods on convex quadratic problems, in which
exact line searches are performed at each iteration. (This algorithm is
identical to Gauss-Seidel on the equivalent symmetric positive definite linear
system.) We describe a class of convex quadratic problems for which the
random-permutations version of cyclic coordinate descent (RPCD) outperforms the
standard cyclic coordinate descent (CCD) approach, yielding convergence
behavior similar to the fully-random variant (RCD). A convergence analysis is
developed to explain the empirical observations.
