  We consider coordinate descent (CD) methods with exact line search on convex
quadratic problems. Our main focus is to study the performance of the CD method
that use random permutations in each epoch and compare it to the performance of
the CD methods that use deterministic orders and random sampling with
replacement. We focus on a class of convex quadratic problems with a diagonally
dominant Hessian matrix, for which we show that using random permutations
instead of random with-replacement sampling improves the performance of the CD
method in the worst-case. Furthermore, we prove that as the Hessian matrix
becomes more diagonally dominant, the performance improvement attained by using
random permutations increases. We also show that for this problem class, using
any fixed deterministic order yields a superior performance than using random
permutations. We present detailed theoretical analyses with respect to three
different convergence criteria that are used in the literature and support our
theoretical results with numerical experiments.
