Anderson Acceleration For ADMM And Its Applications

Most engineering application problems can be attributed to optimization problems,which aims to find the minimal value for given objective functions and constraints.In recent years,on the one hand,the amount of data that needs to be processed in the project is getting larger and larger with the development of science and technology,and so does the scale of the optimization problems,which motives researchers to seek for algorithms which can be applied to large-scale optimization.On the other hand,as the complexity of the problem increases,sometimes the objective function is nonconvex and nonsmooth,which makes many traditional gradient-based optimization methods inapplicable.ADMM is such a suitable algorithm for solving large-scale optimization problems and nonconvex nonsmooth optimization problems.When the objective func-tion can be expressed as the sum of two functions of different variables,and there is a linear constraint between the two variables,ADMM alternately optimizes these two variables and dual variables.It is usually easier to optimize a single function than to optimize the sum of the two functions,in which case we often can get the analytical solution or solve it in parallel,in practice.These features make the iteration cost of each step of ADMM very low,which is suitable for large-scale optimization.In the whole optimization process,ADMM does not need the gradient of these two functions,instead it needs the proximal mapping of these two functions.And for many functions,the proximal mapping is very easy to calculate,which makes ADMM very suitable for nonconvex nonsmooth optimization.Although ADMM has been widely used in engineering,researchers have noticed that it has a notable disadvantage.Usually ADMM can get a low-precision solution quickly,but it would take a lot of time to improve the accuracy of the solution.In some applications,the accuracy requirements are very high.This promotes researchers to think about the acceleration method for ADMM.However,most methods can only be applied to convex ADMM problems,which greatly limits the usage of their methods.Anderson acceleration is an algorithm used to accelerate fixed-point iterations.In recent years,due to the simple implementation and good numerical performance of An-derson Acceleration,it has been widely used in engineering.This article is divided into Two parts.In the first part,we proceeded directly from ADMM itself,and examined fixed point iteration scheme under general setting,then for some special settings,fixed point iterations on lower dimensional variable are given.At the same time,we note that in order to ensure the convergence of the accelerated algorithm,we first need to en-sure the convergence of ADMM itself.The existing convergence proof of nonconvex ADMM requires some strong assumptions,which can not be satisfied by some practical problems.This article makes a detailed analysis of the structure of these problems,and gives a new proof of convergence of nonconvex ADMM with special structure.In the second part,we utilize the equivalence between ADMM and Douglas-Rachford(DR)splitting,by examining the fixed point iteration scheme of the DR splitting algorithm,we reduce the dimension of the accelerated variable for general separable ADMM prob-lems.Finally,utilizing the notion of DR envelope,we also give a proof of the conver-gence of the accelerated algorithm.