Elsevier

Operations Research Letters

Volume 46, Issue 6, November 2018, Pages 585-587
Operations Research Letters

On the asymptotic behaviour of the Aragón Artacho–Campoy algorithm

https://doi.org/10.1016/j.orl.2018.10.003Get rights and content

Abstract

Aragón Artacho and Campoy recently proposed a new method for computing the projection onto the intersection of two closed convex sets in Hilbert space; moreover, they proposed in 2018 a generalization from normal cone operators to maximally monotone operators. In this paper, we complete this analysis by demonstrating that the underlying curve converges to the nearest zero of the sum of the two operators. We also provide a new interpretation of the underlying operators in terms of the resolvent and the proximal average.

Introduction

Throughout this note, X is a real Hilbert spacewith inner product | and associated norm . The notation of our paper is standard and mainly follows [6] to which we also refer to basic results on convex analysis and monotone operator theory. A central problem is to find a zero (critical point) of the sum of two maximally monotone operators. The Douglas–Rachford and Peaceman–Rachford algorithms (see Fact 2.1 ) are classical approaches to solve this problem. If the monotone operators are normal cone operators of nonempty closed convex subsets of X, then one obtains a feasibility problem, i.e., the problem of finding a point in the intersection of the two sets. Suppose, however, that we are interested in finding the nearest point in the intersection. One may then apply several classical best approximation algorithms (see, e.g., [6, Chapter 30]). In the recently published paper [2], Aragón Artacho and Campoy presented a novel algorithm, which we term the Aragón Artacho–Campoy Algorithm (AACA) to solve this best approximation problem. Even more recently, they extended this algorithm in [1] to deal with general maximally monotone operators.

The aim of this paper is to re-derive the AACA from the view point of the proximal and resolvent average. We also complete their analysis by describing the asymptotic behaviour of the underlying curve.

This note is organized as follows. In Section 2, we collect a few facts and results that will make the subsequent analysis more clear. Section 3 contains a new variant of a convergence result for AACA (Theorem 3.2) as well as the announced asymptotic behaviour of the curve (Theorem 3.4).

Section snippets

Auxiliary results

Fact 2.1 Douglas–Rachford and Peaceman–Rachford

Let A and B be maximally monotone on X. Suppose that zer(A+B)=(A+B)1(0), let λ]0,1], and set T=(1λ)Id+λRBRA,where JA=(Id+A)1 and RA=2JAId. Let x0X and define (nN)xn+1=Txn.Then there exists x̄FixT such that z̄=JAx̄zer(A+B) and the following hold:

  • (i)

    If A or B is strongly monotone, then zer(A+B)={z̄}.

  • (ii)

    If λ<1, then xnx̄ and JAxnz̄.

  • (iii)

    If λ<1 and A or B is strongly monotone, then JAxnz̄.

  • (iv)

    If λ=1 and A is strongly monotone, then JAxnz̄.

Proof

This follows from [6, Theorem 26.11 and Proposition 26.13].

The Aragón Artacho–Campoy algorithm (AACA)

From now on, we suppose that A and B are maximally monotone on X, wX, and γ]0,1[.Let σA0 and σB0 be such that AσAId and BσBId are monotone,and we also assume that A+B is maximally monotonewhich will make all results more tidy. (See also Remark 3.3 .) Next, as in Remark 2.3, we introduce the resolvent averages between A,B and N{w}: Aγ:XX:xA(γ1(x(1γ)w))+γ1(1γ)(xw)and Bγ:XX:xB(γ1(x(1γ)w))+γ1(1γ)(xw).

Proposition 3.1

The following hold true:

  • (i)

    Aγ, Bγ, and Aγ+Bγ are maximally monotone.

  • (ii)

    Aγ, Bγ, and

Acknowledgements

The authors thank two anonymous referees for their careful reading and constructive comments. SA was partially supported by Saudi Arabian Cultural Bureau . HHB and XW were partially supported by NSERC Discovery Grants. WMM was partially supported by NSERC Postdoctoral Fellowship.

References (10)

There are more references available in the full text version of this article.
View full text