Line Search for Averaged Operator Iteration

Understand

Many popular first order algorithms for convex optimization, such as forward-backward splitting, Douglas-Rachford splitting, and the alternating direction method of multipliers (ADMM), can be formulated as averaged iteration of a nonexpansive mapping.

• In this paper we propose a line search for averaged iteration that preserves the theoretical convergence guarantee, while often accelerating practical convergence.
• We discuss several general cases in which the additional computational cost of the line search is modest compared to the savings obtained.