Abstract
In this paper we give a quantitative analysis of an explicit iteration method due to C.E. Chidume for the approximation of a zero of an m-accretive operator in Banach spaces which does not involve the computation of the resolvent of A.
1 Introduction
The approximation of zeros of monotone set-valued operators in Hilbert spaces X and—more generally—of accretive operators in Banach spaces is a central theme in both nonsmooth optimization as well as in the study of abstract Cauchy problems. The connection to optimization stems from the fact that the set of minimizers of proper l.s.c. convex functions coincides with the zeros of the so-called subdifferential of f.
The famous Proximal Point Algorithm (PPA) approximates zeros of A using the resolvent function (for ) which is a single-valued firmly nonexpansive function. If A is maximal monotone (such as ) or m-accretive, then and so is defined on the whole space X and it makes sense to consider for a sequence the iteration
Under suitable conditions on this algorithm converges weakly to a zero of A (provided that A has one, [Citation1–3]) but—already in the case of Hilbert spaces—it in general fails to converge strongly (see [Citation4, Citation5]).
Subsequently, so-called Halpern-type variants (HPPA) of (PPA) have been considered (see e.g., [Citation6–8]) which—under suitable conditions on - do converge strongly even in Banach spaces which e.g. are uniformly smooth and at the same time uniformly convex (so e.g., for Lp with ).
One problem with both (PPA) and (HPPA) is that they involve the computation of and so the solution of an inverse problem. Hence the existence of strongly convergence algorithms based on explicit iterations of A itself instead of its resolvent is of interest. Such an algorithm was given in [Citation9] (in Hilbert space) and studied in certain Banach spaces in the case of single-valued A in [Citation10] and in 2-uniformly smooth Banach spaces in [Citation11] and for set-valued A and general uniformly smooth Banach spaces in [Citation12]. The strong convergence of to a zero of A (under suitable conditions on ) is shown in [Citation12] by reducing the situation to the following seminal result of Reich (see also [Citation13] for another proof of an extension of this result):
Theorem 1.1.
[Citation14] Let X be a real uniformly smooth Banach space and be m-accretive with . Then exists and belongs to
More specifically, Chidume shows that
In this paper we first extract from Chidume’s proof an explicit rate of convergence for (Theorem 3.1). It follows from general results in computability that even for there is in general no computable rate of convergence for neither nor However, what recently has been obtained is the next best thing, namely a rate of metastability in the sense of Tao [Citation15, Citation16] for (see [Citation17] which in turn builds on [Citation18]):
Note that noneffectively, implies the Cauchy property and hence the convergence of but does not allow for an effective transformation of into a rate of convergence for
Our rate of convergence together with the rate of metastability in can be combined into a rate satisfying
(Theorem 3.3).
This quantitative result can be seen as a finitization (in the sense of Tao [Citation15]) of Chidume’s theorem as it mathematically trivially (though noneffectively) implies not only that is Cauchy and hence strongly convergent but also that converges to the same limit as converges to.
Definition 1.2.
[Citation19, p. 99] Let X be a real Banach space. with is called the normalized duality mapping of X.
More information on (normalized) duality mappings can be found in [Citation20, Citation21].
Definition 1.3.
([Citation19, p. 128], and [Citation12]) Let X be a Banach space and be a set-valued operator. The domain D(A), the range R(A) and the graph G(A) of A are defined as follows:
A is accretive if for all with
By Kato [Citation22] this is equivalent to the statement that for all
A is m-accretive if for all t > 0 (or - equivalently - for some t > 0) .
is a zero of A if . denotes the set of all zeros of A.
Definition 1.4.
[Citation23, p. 13] A Banach space X is called uniformly smooth if
Remark 1.5.
It is well-known (see e.g., [Citation23], p.13) that the definition above is equivalent to where
Definition 1.6.
X is called uniformly convex if
As in [Citation24], we call functions which provide a in the definitions of uniform smoothness and uniform convexity moduli of uniform smoothness and uniform convexity respectively. Note that this differs from the terminology used in functional analysis where ρX is called the modulus of smoothness of X while it is not a modulus of smoothness in the sense of τFootnote1 and what is called the modulus of uniform convexity δX is a particular, namely the optimal, modulus of uniform convexity η in our sense.
Chidume assumes that A is bounded which is meant as ‘bounded on bounded sets’. As discussed in [Citation25] this is equivalent to A possessing a uniform majorant satisfying
By a majorant for a sequence in X we mean a sequence in such that for all
Notation: Following [Citation12], all our sequences start with the index and we, therefore, use
2 Technical lemmas
In this section we collect some technical estimates for uniformly smooth Banach spaces which are essentially known but in some cases the values of certain constants had to be extracted from the literature.
Lemma 2.1.
(see [Citation26, pp. 64–65], [Citation27, p. 208]) Let X be a uniformly smooth Banach space and ρX be the function defined in Remark 1.5. Then for all with where .
Lemma 2.2.
(see [Citation12, p. 36] and [Citation27]) Let X be uniformly smooth. Then for all and where
Proof.
In [Citation27, p. 208] it is shown that for all with with where
For this yields
Distinguishing the cases and the respective inequalities from Lemma 2.1 imply that
□
Lemma 2.3.
(see [Citation28, p. 284]) Let X be a Banach space. Then for all and for all
Lemma 2.4.
[Citation7, p. 243] Let be sequences of nonnegative real numbers, a sequence of real numbers and a sequence in such that for all
If then it follows that
We now give a quantitative version of Lemma 2.4. Similar versions have been used repeatedly in the context of proof mining e.g. in [Citation29, Citation30]. For completeness, however, we give the proof for the particular formulation we need.
Lemma 2.5.
Let be as in the previous lemma and let be a majorant for Let be rates witnessing quantitatively the conditions on i.e.
Then where and .
Proof.
Let be arbitrary and let
We prove by induction on n that for all :
The case n = N holds by assumption. Assume that the claim holds for Then
Moving inside, using as well as the induction step follows.
Let now Then - using - and imply . □
The following bound on the iterative sequence of Chidume’s algorithm is crucially used:
Lemma 2.6.
(see [Citation12, p.37]) Let X be a uniformly smooth Banach space, be a bounded set-valued accretive operator with D(A) = X and Let and be sequences in (0, 1) and be arbitrary. Let C, D be as in Lemma 2.2 and let be such that
Let be such that
If for all then is bounded by
Proof.
[Citation12, p.37] shows that under the conditions given, one has which implies the claim. □
In the following we give a more explicit and effective description of the bound on which avoids the use of ’s.
Corollary 2.7.
Let be a uniform majorant of A witnessing that A is bounded on bounded sets, i.e.
Then the condition in Lemma 2.6 can be replaced by with
Proof.
With Lemma 2.1 we get
Together with the easy estimates the corollary follows. □
3 Main results
The next theorem gives an explicit and effective rate for the convergence of where is the sequence generated by Chidume’s algorithm and with
Theorem 3.1.
Let X be a uniformly smooth Banach space, be a bounded set-valued m-accretive operator with D(A) = X with Let and let be a uniform majorant of A. Let and be sequences in (0, 1) and arbitrary. Let and be sequences in A satisfying
Let be such that , C and D as in Lemma 2.2, and
If then and and the first three properties are quantitatively witnessed by i.e. then where
Proof.
We follow closely the proof of Theorem 3.2 in [Citation12]. First we show the boundedness of using the nonexpansivity of and the fact that being a zero of A is a common fixed point of the resolvents
With Lemma 2.2, the boundedness of xn (see Lemma 2.6 and Corollary 2.7) and yn and the majorant of A together with Lemma 2.1 and the definition of it follows that
As in [Citation12, pp.38–39] one shows that and (for ) as well as
Combining these four inequalities we get (reasoning as in [Citation12]) for all
With Lemma 2.5 applied to and for all and applying the square root we finally get
□
By Reich’s theorem, mentioned already in the introduction, one can show under the additional condition that diverges to , i.e. that tends to 0, that strongly converges to a zero of A. An explicit rate of metastability witnessing this quantitatively has been computed (under the additional assumption that X is also uniformly convex) in the case of single-valued A in [Citation18] and was recently generalized to the set-valued case in [Citation17].
Theorem 3.2.
[Citation17, Corollary 4.2] Let X be a Banach space which is both uniformly smooth and uniformly convex with respective moduli τ and Let be m-accretive and such that Let be arbitrary and such that and with and functions such that
Then there exists an explicit and fully effective rate of metastability for the sequence which only depends on and Footnote2
As in [Citation31, Theorem 2.8] we can now combine this with Theorem 3.1:
Theorem 3.3.
In addition to the assumptions made in Theorem 3.1 we assume that X is also uniformly convex with a modulus η and that diverges to and that we have functions with
Let be the rate of metastability for as in Theorem 3.2. Then converges to the limit of and we have the following explicit rate of metastability witnessing this fact: where is as in Theorem 3.1 and
Proof.
For we know by Theorem 3.2 that
Given k, g, we apply this to k + 1 and where is the rate from Theorem 3.1:
Let n be as in the formula above and define Since we can restrict things to the smaller interval By Theorem 3.1 we have for all l, m in this smaller interval that
This means in total that for
By construction which finishes the proof. □
The condition involves ρX which is defined as a supremum which may not be computable. The next proposition shows how we can replace this with a condition involving only the modulus τ instead of
Proposition 3.4.
Let X be a uniformly smooth Banach space with a modulus of uniform smoothness τ, be a sequence in (0, 1), some constant and C as in Lemma 2.1. Assume that τ is strictly increasing and so that the inverse of τ is defined on If for K > 0 then
Proof.
By Lemma 2.1 and by the definition of τ
Applying this to we see that
which in turn implies and so from which the proposition follows. □
We now elaborate on an example from [Citation12] for a special choice of the scalars in the case of Lp with which satisfy the conditions in Chidume’s theorem and compute the corresponding rates as well as used in our bounds:
Example 3.5.
Let and define with and
Let
Then satisfy the conditions in our Theorems 3.1 and (together with ) Theorem 3.3 with
Proof.
First observe that we get (using the estimates for ρX with from [Citation26, p.63] or [Citation27, p.193]) if and if Next we have
Let Then (using the Bernoulli inequality with exponent and )
Ad Using again the aforementioned estimates for ρX we have (for )
Let Then for
Hence for we get
Together with this yields
The case is treated analogously.
One easily verifies that satisfy the requirements from Theorem 3.3 for our choice of scalars. □
Remark 3.6.
A rate similar to above can be also obtained using R4 from [Citation32, Section 5], where a different argument is used.
Acknowledgments
This paper grew out of a Bachelor thesis [Citation33] of the first author written under the supervision of the 2nd author.
Additional information
Funding
Notes
1 The existence of a modulus τ is equivalent to the uniform smoothness of X while ρX is also defined for non-smooth Banach spaces and only the aforementioned limit statement expresses uniform smoothness.
2 In [17], and so for we have to apply the rate given in [17] to and to replace 0 by 1 in the original bound.
References
- Martinet, B. (1970). Régularisation d’inéquations variationnelles par approximations successives. Rev. Française Informat. Recherche Opérationnelle 4:154–158. DOI: 10.1051/m2an/197004R301541.
- Rockafellar, R. T. (1976). Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5):877–898. DOI: 10.1137/0314056.
- Bruck, R. E., Reich, S. (1977). Nonexpansive projections and resolvents of accretive operators in Banach spaces. Houston J. Math. 3:459–470.
- Güler, O. (1991). On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29(2):403–419. DOI: 10.1137/0329022.
- Bauschke, H. H., Matoušková, E., Reich, S. (2004). Projection and proximal point methods: convergence results and counterexamples. Nonlinear Anal. 56:715–738. DOI: 10.1016/j.na.2003.10.010.
- Kamimura, S., Takahashi, W. (2000). Approximating solutions of maximal monotone operators in Hilbert spaces. J. Approx. Theory 106(2):226–240. DOI: 10.1006/jath.2000.3493.
- Xu, H.-K. (2002). Iterative algorithms for nonlinear operators. J. London Math. Soc. 66(1):240–256. DOI: 10.1112/S0024610702003332.
- Aoyama, K., Toyoda, M. (2017). Approximation of zeros of accretive operators in a Banach space. Israel J. Math. 220:803–816. DOI: 10.1007/s11856-017-1511-1.
- Bruck, R. E. (1974). A strongly convergent iterative method for the solution of 0∈U(x) for a maximal monotone operator U in Hilbert space. J. Math. Anal. Appl. 48:114–126. DOI: 10.1016/0022-247X(74)90219-4.
- Reich, S. (1977). Extension problems for accretive sets in Banach spaces. J. Funct. Ana. 26:378–395. DOI: 10.1016/0022-1236(77)90022-2.
- Chidume, C. E., Djitte, N. (2012). Strong convergence theorems for zeros of bounded maximal monotone nonlinear operators. Abstr. Appl. Anal. 2012:681348. DOI: 10.1155/2012/681348.
- Chidume, C. E. (2016). Strong convergence theorems for bounded accretive operators in uniformly smooth Banach spaces. Contemp. Math. 659:31–41. DOI: 10.1090/conm/659.
- Bruck, R. E., Reich, S. (1981). Accretive operators, Banach limits, and dual ergodic theorems. Bull. Acad. Polon. Sci. Sér. Math. 29:585–589.
- Reich, S. (1980). Strong convergence theorems for resolvents of accretive operators in Banach spaces. J. Math. Anal. Appl. 75(1):287–292. DOI: 10.1016/0022-247X(80)90323-6.
- Tao, T. (2008). Soft analysis, hard analysis, and the finite convergence principle. In: Tao, T., ed. Structure and Randomness: Pages from Year One of a Mathematical Blog. Providence, RI: American Mathematical Society, pp. 298.
- Tao, T. (2008). Norm convergence of multiple ergodic averages for commuting transformations. Ergod. Theory Dyn. Syst. 28(2):657–688. DOI: 10.1017/S0143385708000011.
- Sipos, A. (2024). On quantitative metastability for accretive operators. Z. Anal. Anwend., to appear. DOI: 10.4171/zaa/1741.
- Kohlenbach, U., Sipoş, A. (2021). The finitary content of sunny nonexpansive retractions. Commun. Contemp. Math. 23(01):1950093. DOI: 10.1142/S0219199719500937.
- Takahashi, W. (2000). Nonlinear Functional Analysis. Fixed Point Theory and its Applications. Yokohama: Yokohama Publishers, iv + 276pp.
- Cioranescu, I. (1990). Geometry of Banach Spaces, Duality Mappings and Nonlinear Problems. Mathematics and its Applications, 62. Dordrecht: Kluwer Academic Publishers Group, xiv + 260pp.
- Reich, S. (1992). Review of [20]. Bull. Amer. Math. Soc. 26:367–370. DOI: 10.1090/S0273-0979-1992-00287-2.
- Kato, T. (1967). Nonlinear semigroups and evolution equations. J. Math. Soc. Japan 19(4):508–520. DOI: 10.2969/jmsj/01940508.
- Chidume, C. E. (2009). Geometric Properties of Banach Spaces and Nonlinear Iterations. Lecture Notes in Mathematics, Vol. 1965. London: Springer.
- Kohlenbach, U., Leuştean, L. (2012). On the computational content of convergence proofs via Banach limits. Philos. Trans. Royal Soc. A: Math. Phys. Eng. Sci. 370:3449–3463. DOI: 10.1098/rsta.2011.0329.
- Pischke, N. Logical metatheorems for accretive and (generalized) monotone set-valued operators. J. Math. Logic, to appear DOI: 10.1142/S0219061323500083.
- Lindenstrauss, J., Tzafriri, L. (Reprint of 2013). Classical Banach Spaces II: Function Spaces, Vol. 97. Berlin: Springer 1979.
- Xu, Z.-B., Roach, G. F. (1991). Characteristic inequalities of uniformly convex and uniformly smooth Banach spaces. J. Math. Anal. Appl. 157(1):189–210. DOI: 10.1016/0022-247X(91)90144-O.
- Petryshyn, W. V. (1970). A characterization of strict convexity of Banach spaces and other uses of duality mappings. J. Funct. Anal. 6(2):282–291. DOI: 10.1016/0022-1236(70)90061-3.
- Kohlenbach, U., Leuştean, L. (2012). Effective metastability of Halpern iterates in CAT(0) spaces. Adv. Math. 231:2526–2556. DOI: 10.1016/j.aim.2012.06.028.
- Körnlein, D. (2015). Quantitative results for Halpern iterations of nonexpansive mappings. J. Math. Anal. Appl. 428:1161–1172. DOI: 10.1016/j.jmaa.2015.03.020.
- Körnlein, D., Kohlenbach, U. (2014). Rate of Metastability for Bruck’s iteration of pseudocontractive mappings in Hilbert space. Numer. Funct. Anal. Optim. 35:20–31. DOI: 10.1080/01630563.2013.809361.
- Körnlein, D., Kohlenbach, U. (2011). Effective rates of convergence for Lipschitzian pseudocontractive mappings in general Banach spaces. Nonlinear Anal 74:5253–5267. DOI: 10.1016/j.na.2011.04.028.
- Findling, R. (2023). Logische Analyse von C.E. Chidumes Algorithmus zur Berechnung von Nullstellen akkretiver Operatoren. Bachelor Thesis, TU Darmstadt.