Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive stepsizes and convergence

  • 2018-01-11 14:13:16
  • Dirk A. Lorenz, Quoc Tran-Dinh
  • 4

Abstract

We revisit the classical Douglas-Rachford (DR) method for finding a zero ofthe sum of two maximal monotone operators. Since the practical performance ofthe DR method crucially depends on the stepsizes, we aim at developing anadaptive stepsize rule. To that end, we take a closer look at a linear case ofthe problem and use our findings to develop a stepsize strategy that eliminatesthe need for stepsize tuning. We analyze a general non-stationary DR scheme andprove its convergence for a convergent sequence of stepsizes with summableincrements. This, in turn, proves the convergence of the method with the newadaptive stepsize rule. We also derive the related non-stationary alternatingdirection method of multipliers (ADMM) from such a non-stationary DR method. Weillustrate the efficiency of the proposed methods on several numericalexamples.

 

Introduction (beta)

None

 

Conclusion (beta)

None