A Smoothing Anderson Acceleration Algorithm for Nonsmooth Fixed Point Problems with Linear Convergence

Abstract. In this paper, we consider the Anderson acceleration method for solving the contractive fixed point problem, which is nonsmooth in general. We define a class of smoothing functions for the original nonsmooth fixed point mapping, which are primarily applicable to problems involving max-type nonsmoothness. Based on the Anderson acceleration technique, we propose the Smoothing Anderson(m) algorithm, in which we utilize a smoothing function of the original nonsmooth fixed point mapping and update the smoothing parameter adaptively. We first demonstrate the r-linear convergence of the proposed Smoothing Anderson(m) algorithm for solving the considered nonsmooth contractive fixed point problem with r-factor no larger than [Formula: see text], where [Formula: see text] is the contractive factor of the fixed point mapping. Second, we establish that both the Smoothing Anderson(1) and the Smoothing EDIIS(1) algorithms are q-linearly convergent with q-factor no larger than [Formula: see text]. Finally, we present three numerical examples with practical applications arising from elastic net regression, free boundary problems for infinite journal bearings, and nonnegative logistic regression to illustrate the superior performance of the proposed Smoothing Anderson(m) algorithm compared with some popular methods.