Optimization Online


Iteration complexity of an inexact Douglas-Rachford method and of a Douglas-Rachford-Tseng's F-B four-operator splitting method for solving monotone inclusions

M. Marques Alves(maicon.alves***at***ufsc.br)
Marina Geremia(marinageremia***at***yahoo.com.br)

Abstract: In this paper, we propose and study the iteration complexity of an inexact Douglas-Rachford splitting (DRS) method and a Douglas-Rachford-Tseng's forward-backward (F-B) splitting method for solving two-operator and four-operator monotone inclusions, respectively. The former method (although based on a slightly different mechanism of iteration) is motivated by the recent work of J. Eckstein and W. Yao, in which an inexact DRS method is derived from a special instance of the hybrid proximal extragradient (HPE) method of Solodov and Svaiter, while the latter one combines the proposed inexact DRS method (used as an outer iteration) with a Tseng's F-B splitting type method (used as an inner iteration) for solving the corresponding subproblems. We prove iteration complexity bounds for both algorithms in the pointwise (non-ergodic) as well as in the ergodic sense by showing that they admit two different iterations: one that can be embedded into the HPE method, for which the iteration complexity is known since the work of Monteiro and Svaiter, and another one which demands a separate analysis. Finally, we perform simple numerical experiments to show the performance of the proposed methods when compared with other existing algorithms.

Keywords: Inexact Douglas-Rachford method; splitting; monotone operators; HPE method; complexity; Tseng's forward-backward method.

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 11/30/2017
Entry Accepted: 11/30/2017
Entry Last Modified: 11/30/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society