A Class Of Improved Coordinate Descent Methods Based On Gauss-Southwell-Lipschitz Rule

The coordinate descent method plays a very important role in optimization problems.In this paper,we propose a class of improved coordinate descent methods based on Gauss-Southwell-Lipschitz(GSL)rule to solve unconstrained minimization problems.First,using an index set that the multiplicative perturbation of GSL rule determines and a new probability criterion,we propose a greedy randomized coordinate descent method and derive the convergence of the algorithm in expectation.The greedy randomized coordinate descent method is generalized by introducing a relaxation parameter??(0,1]in the involved the index set,named a relaxed greedy randomized coordinate descent method.Besides,we analyze the iterative complexity of the greedy randomized coordinate descent method for solving the unconstrained minimization problem.The results demonstrate that the method can solve the unconstrained minimization problem with any confidence level.Furthermore,the effectiveness of our proposed algorithm is verified by a mass of numerical experiments.Next,these algorithms are applied to least-squares problems.To avoid calculating A~TA,we redescribe the framework of these algorithms and give the convergence of these algorithms in expectation.It is worth mentioning that the relaxed greedy randomized coordinate descent method of relaxation parameter?=1 reduced to greedy coordinate descent method.In this case,we proved the convergent expression of the algorithm.Furthermore,we discuss a block coordinate descent method for solving least-square problems.We propose a greedy block coordinate descent method based on the index set and derive the convergence of the algorithm.Moreover,these algorithms are used to solve the least-square problems to verify the effectiveness of our proposed algorithm.Finally,based on the equivalence of GSL and MD rules,the difference and relation between Kaczmarz algorithm and coordinate descent method are discussed.In addition,using an index set that the multiplicative perturbation of MD rule,we propose a greedy block Kaczmarz algorithm for solving consistent linear system,and derive the convergence of the algorithm.Furthermore,we test the effectiveness of the algorithm.