Analysis of Order Strategies for Alternating Algorithms in Optimization

We investigate the choice of order of directions for Alternating Coordinate or Block Coordinate Descent algorithms. It is known that when starting the algorithm, the ordering of blocks in the first few steps can be important. We find for three blocks that it is beneficial to begin an alternating algorithm by testing different permutations of the blocks, i.e. 6 different orders for the first three steps. We study which combinations of orders are most effective and design a testing strategy that involves testing 6 permutations for 2 full passes. This strategy outperforms both random, fixed order and other testing strategies in fair comparisons. On quadratic test problems, we prove that our strategy for three directions is optimal among strategies employing two full passes and never gives bad results. For 4 search directions we find a similar search strategy for testing 2 full passes, with 24 permutations. We observe that testing orders is the most beneficial on hard (i.e. ill-conditioned) problems.As the number of directions and dimensions of the problem grows, the initial search orders still matter, but the number of steps needed for the best order to emerge grows. Further, as the number is directions grows, the number of permutations of directions grows factorially. It may become impossible to find the optimal order in an efficient way, but our observations suggest efficient strategies to find a good order for the first steps.