# On the Archimedean Positivstellensatz in Real Algebraic Geometry

Konrad Schmüdgen  University of Leipzig, Mathematical Institute, Augustusplatz
10/11, D-04109 Leipzig, Germany<EMAIL_ADDRESS>
(Date: September 3, 2024)

###### Abstract.

A variant of the Archimedean Positivstellensatz is proved which is based on
Archimedean semirings or quadratic modules of generating subalgebras. It
allows one to obtain representations of strictly positive polynomials on
compact semi-algebraic sets by means of smaller sets of squares or
polynomials. A large number of examples is developed in detail.

AMS Subject Classification (2020). 13J30 (Primary); 12D15, 14P10.

Key words: Positivstellensatz, positive polynomial, semi-algebraic set,
quadratic module, semiring, moment problem

##  1\. Introduction

Archimedean Positivstellensätze are important tools of real algebraic geometry
to describe positive polynomials on compact semi-algebraic sets in terms of
weighted sums of squares or as elements of semirings (see e.g [M08, Section
7.4] or [S17, Section 12.4]). In many situations there are finer versions of
these theorems for which smaller sets of squares or elements are sufficient.
Some results in this direction have been obtained in [SS23, Sections 4 and 6].
The aim of this paper is to provide a variant of a general Archimedean
Positivstellensatz of this kind and to treat a number of illustrating
examples.

To formulate the result we need some terminology and facts from real algebra
[M08], [PD01]. Throughout this paper, $A$ is a commutative unital real algebra
and $A_{1},\dots,A_{m}$, $m\in\mathds{N}$, are subalgebras of $A$ which
contain the unit element $1$ of $A$. For $\alpha\in\mathds{R}$, we write
$\alpha$ for $\alpha\cdot 1$. The subalgebra of $A$ generated by
$A_{1},\dots,A_{n}$, $n\leq m,$, is denoted by
$\mathsf{alg}(A_{1},\dots,A_{n})$.

By a cone in $A$ we mean a subset $C$ of $A$ such that $\lambda c\in C$ and
$c+d\in C$ for all $c,d\in C$ and $\lambda\geq 0$. A cone $C$ in $A$ is called
unital if $1\in C$.

If $C_{j}$ is a unital cone of $A_{j}$ for $j=1,\dots,n$, then
$\mathsf{cone}(C_{1},\dots,C_{n})$ denotes the unital cone in
$\mathsf{alg}(A_{1},\dots,A_{n})$ which is generated by $C_{1}\cdot
C_{2}\cdots C_{n}$. That is, $\mathsf{cone}(C_{1},\dots,C_{n})$ is the set of
elements

$\displaystyle\sum_{k=1}^{r}\,c_{1k}\cdots c_{nk},\leavevmode\nobreak\
\leavevmode\nobreak\ \textrm{ where}\leavevmode\nobreak\ \leavevmode\nobreak\
c_{jk}\in C_{j},\,j=1,\dots,n,\,k=1,\dots,r,\,r\in\mathds{N}.$

We recall the following standard notions of real algebraic geometry.

######  Definition 1.

A unital cone $C$ in $A$ is called a
$\bullet$ _quadratic module_ of $A$ if $a^{2}b\in C$ for all $b\in C$ and
$a\in A.$
$\bullet$ _semiring_ (or a _preprime_) of $A$ if $C\cdot C\subseteq C$.
$\bullet$ _preordering_ of $A$ if $C$ is a quadratic module and a semiring.

The bounded part of $A$ with respect to a unital cone $C$ is defined by

$\displaystyle A_{\rm bd}(C):=\\{a\in A:\leavevmode\nobreak\ \textrm{there
exists}\leavevmode\nobreak\ \lambda>0\leavevmode\nobreak\ \leavevmode\nobreak\
\textrm{such that}\leavevmode\nobreak\ \leavevmode\nobreak\ (\lambda-a)\in
C\leavevmode\nobreak\ \leavevmode\nobreak\ \textrm{and}\leavevmode\nobreak\
\leavevmode\nobreak\ (\lambda+a)\in C\\}.$

A unital cone $C$ of $A$ is called Archimedean if $A=A_{\rm bd}(C)$. If $C$ is
a quadratic module or a semiring of $A$, then $A_{\rm bd}(C)$ is a subalgebra
of $A$. Thus, in this case $C$ is Archimedean if a set of generators of the
algebra $A$ belongs to $A_{\rm bd}(C)$.

For a unital cone $C$ of $A$, we define

$C^{\dagger}:=\\{a\in A:\leavevmode\nobreak\ a+\epsilon\in
C\leavevmode\nobreak\ \textup{ for all }\leavevmode\nobreak\
\epsilon\in(0,\infty)\,\\}.$

Obviously, $C^{\dagger}$ is again a unital cone of $A$ and $C\subseteq
C^{\dagger}$. Such cones were introduced in [KM02] and studied extensively in
[SS23].

A character of $A$ is a unital algebra homomorphism of $A$ into $\mathds{R}$.
The set of all characters of $A$ is denoted by $\mathsf{char}(A)$. For a
subset $C$ of $A$, let

$\displaystyle\mathsf{char}(A;C):=\\{\chi\in\mathsf{char}(A):\,\chi(c)\geq
0\leavevmode\nobreak\ \textrm{for all}\leavevmode\nobreak\ c\in C\,\\}.$

A unital cone $M$ of $A$ is called a $C$-module for a semiring $C$ of $A$ if
$ac\in M$ for all $a\in M$ and $c\in C$. Since $1\in M$, we then have
$C\subseteq M$.

The following theorem is the main result of this paper.

######  Theorem 2.

Suppose that the algebra $A$ is generated by the subalgebras
$A_{1},\dots,A_{m}$ of $A$. We assume that $C_{i}$ is an Archimedean semiring
or an Archimedean quadratic module of the algebra $A_{i}$ for $i=1,\dots,m$.
Let $M$ be a unital cone of $A$. Then for any element $a\in A$ the following
are equivalent:

  * (i)

$\chi(a)>0$ for all $\chi\in\mathsf{char}(A;M)$ and
$\chi\in\mathsf{char}(A;C_{i})$, $i=1,\dots,m$.

  * (ii)

There exists a number $\varepsilon>0$ such that
$a\in\varepsilon+\mathsf{cone}(M,C_{1},\dots,C_{m}).$

We restate the result in the important special case $M=\mathds{R}_{+}\cdot 1$
separately as

######  Corollary 3.

Retain the assumptions of Theorem 2 and let $a\in A$. The the following two
statements are equivalent:

  * (i)

$\chi(a)>0$ for all $\chi\in\mathsf{char}(A;C_{i})$ and $i=1,\dots,m$.

  * (ii)

There is a number $\varepsilon>0$ such that
$a\in\varepsilon+\mathsf{cone}(C_{1},\dots,C_{m}).$

###### Proof.

Set $M=\mathds{R}_{+}\cdot 1$. Then
$\mathsf{cone}(M,C_{1},\dots,C_{m})=\mathsf{cone}(C_{1},\dots,C_{m})$ and all
characters of $A$ are in $\mathsf{char}(A;M)$, so the assertion follows from
Theorem 2. ∎

The following corollary is the main assertion of Theorem 2 in the case $m=1$.
It can be considered as a Positivstellensatz for ”modules” of quadratic
modules.

######  Corollary 4.

Suppose $Q$ is an Archimedean quadratic module of $A$ and let $M$ be a unital
cone of $A$. If $a\in A$ satisfies $\chi(a)>0$ for all
$\chi\in\mathsf{char}(A;M)$ and $\chi\in\mathsf{char}(A;Q)$, then
$a\in\varepsilon+\mathsf{cone}(M,Q)$ for some $\varepsilon>0$.

Let us briefly discuss the preceding results and notions. If all cones $C_{i}$
are semirings of $A_{i}$, then it is easily seen that
$\mathsf{cone}(C_{1},\dots,C_{m})$ is semiring of
$A=\mathsf{alg}(A_{1},\dots,A_{m})$. However, if some cones $C_{i}$ are
quadratic modules and others are semirings which are not preorderings, then
$\mathsf{cone}(C_{1},\dots,C_{m})$ is in general neither a semiring nor a
quadratic module of $A$ (see Example 20 below). In fact, if $C_{i}$ is a
quadratic module of $A_{i}$, then $C_{i}$ is invariant under multiplication by
squares of $A_{i}$, but not under multiplication by squares of the larger
algebra $A$. However, if all $C_{i}$ are Archimedean semirings or quadrartic
modules, then $\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger})$ is even a
preordering. This is shown in the next theorem which is also a main ingredient
of the proof of Theorem 2.

######  Theorem 5.

Under the assumptions of Theorem 2,
$\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$ is an
Archimedean preordering of the algeba $A$ and
$\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger})$ is an
$\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$-module.

The proofs of both theorems are given in the next section. A large number of
examples, known and new ones, are developed in section 3.

######  Remark 6.

The results of this paper have direct applications to the classical multi-
dimensional moment problem. For this we recall Haviland’s theorem [H36], in
the general form given in [S17, Theorem 1.14]:

Suppose $A$ is a finitely generated unital real algebra and $K$ is a closed
subset of $\mathsf{char}(A)$. Let $C$ denote the preordering

(1) $\displaystyle C:=\\{a\in A:\chi(a)>0,\chi\in K\\}.$

If $L$ is a linear functional on $A$ such that $L(a)\geq 0$ for all $a\in C$,
then $L$ is a $K$-moment functional, that is, there exists a Radon measure
$\mu$ on $\mathsf{char}(A)$ supported on $K$ such that all functions of $A$
are $\mu$-integrable and $L(f)=\int fd\mu$ for $f\in A$.

Based on Theorem 2 and Corollaries 3 and 4 we develop in Section 3
descriptions of the preordering $C$ given by (1) in terms of defining
polynomials of the corresponding semi-algebraic sets $K(f_{1},\dots,f_{r})$.
Requiring that $L(a)\geq 0$ for all these elements $a$ yield new solvability
criteria for the $K(f_{1},\dots,f_{r})$-moment problem in the corresponding
examples. We leave it to the reader to restate these criteria.

##  2\. Proofs of Theorems 2 and 5

First we recall two results which will be essentially used in the proofs given
below. The following is the Positivstellensatz for modules of Archimedean
semirings. The version for Archimedean semirings (the case $C=S$) is due to
Krivine [Kv64].

######  Proposition 7.

Suppose that $C$ is an $S$-module of an Archimedean semiring $S$ of a
commutative unital real algebra $A$. Let $a\in A$. If $\chi(a)>0$ for all
$\chi\in\mathsf{char}(A;C)$, then $a\in C$.

###### Proof.

[J01] or [M08, Theorem 5.4.4] or [S23, Theorem 12.43]. ∎

######  Proposition 8.

If $C$ is an $S$-module of an Archimedean semiring $S$ or $C$ is an
Archimedean quadratic module of $A$, then $C^{\dagger}$ is a preordering.

###### Proof.

[SS23, Theorem 3.2 and Corollary 3.6]. ∎

The proofs of the theorems are divided into several steps stated as lemmas. In
the rest of this section we retain the assumptions of Theorem 2 and the
notation introduced above.

######  Lemma 9.

If each cone $C_{i}$ is Archimedean in $A_{i}$ for $=1,\dots,n$, then
$\mathsf{cone}(C_{1},\dots,C_{n})$ is an Archimedean cone in
$\mathsf{alg}(A_{1},\dots,A_{n})$.

###### Proof.

Let us abbreviate $D_{k}:=\mathsf{cone}(C_{1},\dots,D_{k})$ and
$B_{k}:=\mathsf{alg}(A_{1},\dots,A_{k})$. We prove by induction that $D_{k}$
is an Archimedean cone in $B_{k}$ for $k=1,\dots,n$. For $k=1$ this is clear,
since $D_{1}=C_{1}$ is Archimedean in $A_{1}$ by assumption. Assume that the
assertion holds for $k<n$. Let $a\in B_{k+1}$. Since
$B_{k+1}=\mathsf{alg}(A_{k+1},B_{k})$, $a$ is of the form
$\sum_{i=1}^{n}a_{i}b_{i}$, where $a_{\in}A_{k+1}$ and $B_{i}\in B_{k}$ for
$i=1,\dots,n$. Since $C_{k+1}$ is Archimedean in $A_{k+1}$ and $D_{k}$ is
Archimedean in $B_{k}$ by induction assumption, there exists a $\lambda>0$
such that $\lambda\pm a_{i}\in C_{k+1}$ and $\lambda\pm b_{i}\in D_{k}$ for
$i=1,\dots,n$. Then

(2) $\displaystyle 3n\lambda^{2}-a=\sum_{i=1}^{n}(\lambda-
a_{i})(\lambda+b_{i})+\lambda\sum_{i=1}^{n}(\lambda+a_{i})+\lambda\sum_{i=1}^{n}(\lambda-
b_{i})\in D_{k+1}$

which completes the induction proof.+ ∎

######  Lemma 10.

If $c,d\in\mathsf{cone}(C_{1},\dots,C_{m})$ and $\varepsilon>0$, then
$cd+\varepsilon\in\mathsf{cone}(C_{1},\dots,C_{m})$.

###### Proof.

We retain the notation from the proof of Lemma 9 and prove the assertion by
induction. That is, we show that $cd+\varepsilon\in D_{k}$ for $c,d\in D_{k}$
and $\varepsilon>0$. First let $k=1$. Then, since $C_{1}$ is an $S_{1}$-module
of an Archimedean semiring $S_{1}$ or $C_{1}$ is an Archimedean quadratic
module in $A_{1}$, $C_{1}^{\dagger}$ is a preordering in $A_{1}$ by
Proposition 8, so $c,d\in D_{1}=C_{1}$ implies $cd\in C_{1}^{\dagger}$ and
hence $cd+\varepsilon\in C_{1}=D_{1}$. Suppose now that the assertion is true
for $n<m$. Let $c,d\in D_{n+1}$. Then $c$ and $d$ can be written as

$\displaystyle c=\sum_{k=1}^{r}c_{k}u_{k}\leavevmode\nobreak\
\leavevmode\nobreak\ \textrm{and}\leavevmode\nobreak\ \leavevmode\nobreak\
d=\sum_{k=1}^{r}d_{k}v_{k},\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \textrm{where}\leavevmode\nobreak\ \leavevmode\nobreak\
c_{k},d_{k}\in C_{n+1},u,v_{k}\in D_{n}.$

Since $C_{n+1}$ is Archimedean in $A_{1}$ by assumption and $D_{n}$ is
Archimedean in the algebra $B_{n}=\mathsf{alg}(A_{1},\dots,A_{n})$ by Lemma 9,
there exists a number $\lambda>0$ such that $(\lambda-c_{j}d_{k})\in C_{n+1}$
and $(\lambda-u_{j}v_{k})\in D_{n}$ for all $j,k=1,\dots,r$. Further, because
$C_{n+1}^{\dagger}$ is a preordering, again by Proposition 8, we have
$c_{j}d_{k}\in C_{n+1}^{\dagger}$ and hence $c_{j}d_{j}+\delta\in C_{n+1}$ for
any $\delta>0$. By the induction hypothesis, $u_{j}v_{k}+\delta\in D_{n}$ for
$\delta>0$ and $j,k=1,\dots,r$. Now we set $\delta:=-\lambda+\sqrt{\varepsilon
r^{-2}+\lambda^{2}}$. Then $\delta>0$ and $\delta^{2}r^{2}+2\delta\lambda
r^{2}=\varepsilon$. Using the latter equation we obtain

$\displaystyle
cd+\varepsilon=\sum_{j,k=1}^{r}(c_{j}d_{k}+\delta)(u_{j}v_{k}+\delta)+\delta\sum_{j,k=1}^{r}(\lambda-
c_{j}d_{k})+\delta\sum_{j,k=1}^{r}(\lambda-u_{j}v_{k}).$

By construction, the first sum is an element of
$\mathsf{cone}(C_{n+1},D_{n})=D_{n+1}$, the second is in $C_{n+1}$, and the
third is in $D_{n}$. Therefore, $cd+\varepsilon\in D_{n+1}$, which completes
the induction proof. The case $n+1=m$ gives the assertion. ∎

######  Lemma 11.

If $c,d\in\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$ then
$cd\in\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$.

###### Proof.

We mimick the reasoning of the proof of the preceding lemma. By Lemma 9,
$\mathsf{cone}(C_{1},\dots,C_{m})$ is Archimedean in $A$. Hence there exists
$\lambda>0$ such that $(\lambda-c)\in\mathsf{cone}(C_{1},\dots,C_{m})$ and
$(\lambda-d)\in\mathsf{cone}(C_{1},\dots,C_{m})$. Let $\varepsilon>0$ and put
$\delta:=-\lambda+\sqrt{\varepsilon/2+\lambda^{2}}$. Then
$\varepsilon=\delta^{2}+2\delta\lambda+\varepsilon/2$. Since
$c,d\in\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$, we have
$(c+\delta),(d+\delta)\in\mathsf{cone}(C_{1},\dots,C_{m})$. Therefore, it
follows from Lemma 10 that
$[(c+\delta)(d+\delta)+\frac{1}{2}\varepsilon/2]\in\mathsf{cone}(C_{1},\dots,C_{m})$.
Using the preceding facts and

(3) $\displaystyle
cd+\varepsilon=[(c+\delta)(d+\delta)+\varepsilon/2]+\delta(\lambda-c)+\delta(\lambda-d).$

we conclude that $cd+\varepsilon\in\mathsf{cone}(C_{1},\dots,C_{m})$ for all
$\varepsilon>0$. This means that $cd\in\mathsf{cone}(C_{1},\dots,C_{m})$. ∎

######  Lemma 12.

For each $a\in A$, we have
$a^{2}\in\mathsf{cone}(A_{1},\dots,A_{m})^{\dagger}$.

###### Proof.

Since $A$ is generated the subalgebras $A_{1},\dots,A_{m}$ , $a\in A$ is of
the form

(4) $\displaystyle a=\sum_{k=1}^{n}a_{1k}\cdots a_{mk}\,,\leavevmode\nobreak\
\leavevmode\nobreak\ \textrm{ where}\leavevmode\nobreak\ \leavevmode\nobreak\
a_{ik}\in A_{i},\,i=1,\dots,m,k=1,\dots,n.n\in\mathds{N}.$

Without loss of generality we assume that $C_{i}$ is an $S_{i}$-module of a
semiring $S_{i}$ for $i=1,\dots,r$ and $C_{r+1},\dots,C_{m}$ are quadratic
modules. Since each $C_{l}$ is an Archimedean cone of $A_{l}$ by assumption,
there exists a positive number $\lambda$ such that

(5) $\displaystyle(\lambda-a_{jk}),(\lambda+a_{jk})\in
C_{j}\leavevmode\nobreak\ \leavevmode\nobreak\
\textrm{and}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
(\lambda-a_{i1}^{2}-\cdots-a_{in}^{2})\in C_{i}$

for $j=1,\dots,r$, $i=r+1,\dots,m$, and $k=1,\dots,n$.

Now we consider the polynomial algebra
$B:=\mathds{R}[x_{11},x_{12},\dots,x_{mn}]$ and the unital cone $S$ in $B$
obtained by the non-negative combination of polynomials

$\displaystyle(\lambda-x_{11})^{k_{11}}($
$\displaystyle\lambda+x_{11})^{l_{11}}\cdots(\lambda-
x_{1n})^{k_{1n}}(\lambda+x_{1n})^{l_{1n}}\times\cdots\times$
$\displaystyle(\lambda-x_{r1})^{k_{r1}}$
$\displaystyle(\lambda+x_{r1})^{l_{r1}}\cdots(\lambda-
x_{rn})^{k_{rn}}(\lambda+x_{rn})^{l_{rn}}\times$ $\displaystyle(\lambda-
x_{r+1,1}^{2}-\cdots-x_{r+1,n}^{2})$ $\displaystyle
q_{r+1}(x_{r+1,1},\dots,x_{r+1,n})+p_{r+1}(x_{r+1,1},\dots,x_{r+1,n})\times\cdots\times$
$\displaystyle(\lambda-x_{m1}^{2}-\cdots$ $\displaystyle-
x_{mn}^{2})q_{m}(x_{m1},\dots,x_{mn})+p_{m}(x_{m1},\dots,x_{mn}),$

where $k_{11},\dots,k_{rn},l_{11},\dots,l_{rn}\in\mathds{N}_{0}$ and

(6) $\displaystyle
q_{j},p_{j}\in\sum\mathds{R}[x_{j1},\dots,x_{jn}]^{2}\leavevmode\nobreak\
\leavevmode\nobreak\ \textrm{ for}\leavevmode\nobreak\ \leavevmode\nobreak\
j=r+1,\dots,m.$

Since the product of such polynomials is of the same form, $S$ is a semiring
in $B$. We verify that $AS$ is Archimedean in $B$. By definition, $\lambda\pm
x_{ji}$ for $j=1,\dots,r,$ $i=1,\dots,n$ belongs to $S$. Now we turn to
$x_{ji}$, with $j\in\\{r+1,\dots,m\\},i\in\\{1,\dots,n\\}$. Since $\lambda-
x_{j1}^{2}-\cdots-x_{jn}^{2}$ is in $S$ by definition, it follows from the
identity

$\displaystyle\sqrt{\lambda}\pm
x_{ji}=\frac{1}{2\sqrt{\lambda}}\Big{[}(\lambda-x_{j1}^{2}-\cdots-
x_{jn}^{2})+\sum_{l=1,l\neq i}^{n}x_{jl}^{2}+(\sqrt{\lambda}\pm
x_{ji})^{2}\Big{]}$

that $\sqrt{\lambda}\pm x_{ji}$ is in $S$. Therefore, $S$ is an Archimedean
semiring of $B=\mathds{R}[x_{11},\dots,x_{mn}]$.

Let $\varepsilon>0$ and consider the polynomial

$p_{\varepsilon}(x_{11},\dots,x_{mn}):=\Big{(}\sum_{k=1}^{n}x_{1k}\cdots
x_{mk}\Big{)}^{2}+\varepsilon$

of $\mathds{R}[x_{11},\dots,x_{mn}]$. Obviously, $p_{\varepsilon}>0$ on
$\mathds{R}^{mn}$. In particular, $p_{\varepsilon}>0$ on the semi-algebraic
set of $\mathds{R}^{mn}$ defined by the semiring $S$. Therefore, by the
Archimedean positivstellensatz for semirings (Proposition 7 for $C=S$),
$p_{\varepsilon}$ belongs to $S$.

Setting $x_{ji}=a_{ji}$ in $p_{\varepsilon}(x_{11},\dots,x_{mn})$ and using
(4) we conclude that $a^{2}+\varepsilon$ is a non-negative combination of
elements

$\displaystyle(\lambda-a_{11})^{k_{11}}($
$\displaystyle\lambda+a_{11})^{l_{11}}\cdots(\lambda-
a_{1n})^{k_{1n}}(\lambda+a_{1n})^{l_{1n}}\times\cdots\times$
$\displaystyle(\lambda-a_{r1})^{k_{r1}}$
$\displaystyle(\lambda+a_{r1})^{l_{r1}}\cdots(\lambda-
a_{rn})^{k_{rn}}(\lambda+a_{rn})^{l_{rn}}\times$ $\displaystyle(\lambda-
a_{r+1,1}^{2}-\cdots-a_{r+1,n}^{2})$ $\displaystyle
q_{r+1}(a_{r+1,1},\dots,a_{r+1,n})+p_{r+1}(a_{r+1,1},\dots,a_{r+1,n})\times\cdots\times$
$\displaystyle(\lambda-a_{m1}^{2}-\cdots$ $\displaystyle-
a_{mn}^{2})q_{m}(a_{m1},\dots,a_{mn})+p_{m}(a_{m1},\dots,a_{mn}),$

For $i=1,\dots,r$ we have $(\lambda\pm a_{ij})\in C_{i}$ by (5) and $C_{i}$ is
a semiring by assumption. Hence, the product of all terms in first two lines
belongs to $C_{1}\cdots C_{r}$. From (6) it follows that
$q_{j}(a_{j,1},\dots,a_{jn})$ and $p_{j}(a_{j,1},\dots,a_{jn})$ are in
$\sum(A_{j})^{2}.$ for $j=r+1,\dots,m$. Since $C_{j}$ is a quadratic module of
$A_{j}$ for $j=r+1,\dots,m$ we conclude that the product of terms in the last
two lines is in $C_{r+1}\cdots C_{m}$. Hence the whole product belongs to
$\mathsf{cone}(C_{1},\dots,C_{m})$. Therefore,
$a^{2}+\varepsilon\in\mathsf{cone}(C_{1},\dots,C_{m})$ for all
$\varepsilon>0$. That means that
$a^{2}\in\mathsf{cone}(C_{1},\dots,S_{m})^{\dagger}$. ∎

######  Lemma 13.

(7)
$\displaystyle\mathsf{char}(A;\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}))$
$\displaystyle=\mathsf{char}(A;\mathsf{cone}(M,C_{1},\dots,C_{m}))$ (8)
$\displaystyle=\mathsf{char}(A;M)\cap_{i=1}^{m}\mathsf{char}(A;C_{i}).$

###### Proof.

Since
$\mathsf{cone}(M,C_{1},\dots,C_{m})\subseteq\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger})$,
it is obvious that
$\mathsf{char}(A;\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}))\subseteq\mathsf{char}(A;\mathsf{cone}(M,C_{1},\dots,C_{m})).$
Conversely, let $\chi\in\mathsf{char}(A;\mathsf{cone}(M,C_{1},\dots,C_{m}))$
and $c\in\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}).$ Then,
$c=\sum_{i=1}^{r}a_{i}c_{i}$, with $a_{i}\in M$ and
$c_{i}\in\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$. For any $\varepsilon>0$,
we have $a_{i}(c_{i}+\varepsilon)\in\mathsf{cone}(M,C_{1},\dots,C_{m})$, so

$\displaystyle\chi(c)-\varepsilon\sum_{i=1}^{r}\chi(a_{i})=\sum_{i=1}^{r}\chi(a_{i}(c_{i}+\varepsilon))\geq
0.$

Letting $\varepsilon\to+0$ yields $\chi(c)\geq 0$, so
$\chi\in\mathsf{char}(A;\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger})).$
This proves the equality (7).

A character $\chi$ of $A$ is in
$\mathsf{char}(A;\mathsf{cone}(M,C_{1},\dots,C_{m}))$ if and only if
$\chi(ac_{1}\cdots c_{m})\newline =\chi(a)\chi(c_{1})\cdots\chi(c_{m})\geq 0$
for all $a\in M$, $c_{1}\in C_{1},\dots,c_{m}\in C_{m}$, or equivalently,
$\chi\in\mathsf{char}(A;M)$ and $\chi\in\mathsf{char}(A;C_{i})$ for all
$i=1,\dots,m$. This proves (8). ∎

Now we are ready to prove the two theorems.

Proof of Theorem 5:

From Lemma 11 and 12, $\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$ is
invariant under multiplication and contains all squares. Hence it is a
preordering. By Lemma 9, it is Archimedean.

Since $\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$ is invariant under
multiplication, it is obvious that
$\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger})$ is a
$\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$-module.

Proof of Theorem 2:

(i)$\to$(ii): Since $\mathsf{cone}(C_{1},\dots,C_{m})$ is Archimedean by Lemma
9, so is the larger
$\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger})$. Hence
$\mathsf{char}(A;\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}))$
is compact in the weak topology. Hence the positive continuous function
$a\to\chi(a)$ on the compact space
$\mathsf{char}(A;\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}))=\mathsf{char}(A;M)\cap_{i=1}^{m}\mathsf{char}(A;C_{i})$
(by (7) and (8)) has a positive infimum, say $\alpha$. Hence $a-\alpha/2$
satisfies condition (i) as well. From Theorem 5 we know that
$\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$ is an Archimedean preordering and
$\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger})$ is a
$\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$-module. Therefore, by the
Positivstellensatz for modules of Archimedean semirings (Proposition 7), (i)
implies that $a-\alpha/2$ belongs to
$\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger})$, that is, we
have $a-\alpha/2=\sum_{i=1}^{s}a_{i}c_{i}$, with $a_{i}\in M$ and
$c_{i}\in\mathsf{cone}(C_{1},\dots,C_{m})^{\dagger}$ for $i=1,\dots,s$. Using
once more that $\mathsf{cone}(C_{1},\dots,C_{m})$ is Archimedean (Lemma 9)
there exists $\lambda>0$ such that
$(\lambda-\sum_{i=1}^{s}a_{i})\in\mathsf{cone}(C_{1},\dots,C_{m})\subseteq\mathsf{cone}(M,C_{1},\dots,C_{m})$.
Set $\varepsilon:=\alpha/4$ and $\delta:=\alpha(4\lambda)^{-1}$. Then
$\alpha/2-\delta\lambda=\varepsilon$. Since
$c_{i}+\delta\in\mathsf{cone}(C_{1},\dots,C_{m})$, we therefore obtain

$\displaystyle
a=\alpha/2-\delta\lambda+\sum_{i=1}^{s}a_{i}(c_{i}+\delta)+\delta\Big{(}\lambda-\sum_{i=1}^{s}a_{i}\Big{)}\in\varepsilon+\mathsf{cone}(M,C_{1},\dots,C_{m}).$

(ii)$\to$(i): Suppose that (ii) holds, say $a=\varepsilon+c$ with
$c\in\mathsf{cone}(M,C_{1},\dots,C_{m})$. Then
$\chi(a)=\varepsilon+\chi(c)\geq\varepsilon>0$ for all
$\chi\in\mathsf{char}(A;\mathsf{cone}(M,C_{1},\dots,C_{m}))=\mathsf{char}(A;M)\cap_{i=1}^{m}\mathsf{char}(A;C_{i})$
by (8). This proves (i).

##  3\. Examples

Throughout this section, we abbreviate
$\mathds{R}_{n}[\underline{x}]:=\mathds{R}[x_{1},x_{2},\dots,x_{n}]$. The
characters of $A:=\mathds{R}_{n}[\underline{x}]$ are precisely the point
evaluations at points of $\mathds{R}^{n}$. For notational simplicity we
identify a point evaluation with the corresponding point of $\mathds{R}^{n}$.
Thus, if $C_{i}$ is a semiring or a quadratic module of $A_{i}$ generated by
polynomials $f_{1},\dots,f_{r}\in\mathds{R}_{n}[\underline{x}]$, it is easily
seen that $\mathsf{char}(A;C_{i})$ is the semi-algebraic set

(9) $\displaystyle K(f_{1},\dots,f_{r}):=\\{t\in\mathds{R}^{n}:f_{1}(t)\geq
0,\dots,f_{r}(t)\geq 0\\}.$

In this section we develop a number of examples. Our particular aim is to
obtain representations of positive polynomials based on smaller sets of
polynomials. For instance, instead of squares of arbitrary elements of $A$ in
many examples only squares of elements of certain subalgebras occur.

All assertions in the examples follow from Theorem 2 or from Corollary 4 or
Proposition 7. In most cases we leave the details of verifications to the
reader.

We begin with some simple examples around cubes $[-1,1]^{n}$ for
$n\in\mathds{N}$.

######  Example 14.

Multi-dimensional Bernstein theorem on $[-1,1]^{n}$
Recall that Bernstein’s theorem says that each polynomial $q\in\mathds{R}[x]$
which is positive on the interval $[-1,1]$ is of the form

$\sum_{k,l=0}^{r}\alpha_{kl}(1-x)^{k}(1+x)^{l},\leavevmode\nobreak\
\leavevmode\nobreak\ \textrm{where}\leavevmode\nobreak\ \leavevmode\nobreak\
\alpha_{kl}\geq 0,k,l=1,\dots,r,\leavevmode\nobreak\ \leavevmode\nobreak\
\textrm{and}\leavevmode\nobreak\ r\in\mathds{N}_{0}$

Now let $n\in\mathds{N}$ and set $A=\mathds{R}_{n}[\underline{x}]$. If
$p\in\mathds{R}_{n}[\underline{x}]$ and $p(x)>0$ for all $x\in[-1,1]^{n}$,
then $p$ is a sum of terms

(10)
$\displaystyle\alpha(1-x_{1})^{k_{1}}(1+x_{1})^{l_{1}}\cdots(1-x_{n})^{k_{n}}(1+x_{n})^{l_{n}},$

where $\alpha\geq 0$ and
$k_{1},\dots,k_{n},l_{1},\dots,l_{n}\in\mathds{N}_{0}$.

This is an immediate consequence of Theorem 2, applied with
$A_{i}=\mathds{R}[x_{i}]$ and the semiring $C_{i}$ of $A_{i}$ generated by
$1+x_{i},1-x_{i}$. It follows also directly the Archimedean Positivstellensatz
for semirings (Proposition 7), applied to the Archimedean semiring defined the
sum of terms (10).

######  Example 15.

Multi-dimensional Markoff-Lukacs theorem on $[-1,1]^{n}$
First let us state the one-dimensional Markoff-Lukacs theorem. A polynomial
$q\in\mathds{R}[x]$ is non-negative on $[-1,1]$ if and only if $q$ belongs to

(11) $\displaystyle
C:=\\{(1-x^{2})q_{1}(x)^{2}+p(x)^{2}\,:q_{1},p_{1}\in\mathds{R}[x]\\}.$

(It should be emphasized that we have single squares in (11) rather than sums
of squares. Further, this result implies at once that $C$ is a preordering in
$\mathds{R}[x]$.)

Now we turn an $n$-dimensional version. If $p\in\mathds{R}_{n}[\underline{x}]$
satisfies $p(x)>0$ for all $x\in[-1,1]^{n}$, then $p$ is a sum of terms

$\displaystyle\alpha[(1-x_{1}^{2})q_{1}(x_{1})^{2}$
$\displaystyle+p_{1}(x_{1})^{2}]\cdots[(1-x_{n}^{2})q_{n}(x_{n})^{2}+p_{n}(x_{n})^{2}],$

where $\alpha\geq 0$ and $q_{1},p_{1},\dots,q_{n},p_{n}\in\mathds{R}[x].$

This follows from Theorem 2, applied with $A_{j}=\mathds{R}[x_{j}]$ and

(12) $\displaystyle
C_{j}:=\\{(1-x_{j}^{2})q_{j}(x_{j})^{2}+p_{j}(x_{j})^{2}\,:q_{j},p_{j}\in\mathds{R}[x_{j}]\\}.$

######  Example 16.

Combining Bernstein and Markoff-Lukacs theorems on $[-1,1]^{r+s}$
Let $R$ be the cube $[-1,1]^{r+s}$ in $\mathds{R}^{s+k}$, where
$r,s\in\mathds{N}$ . If $p\in\mathds{R}_{r+s}[\underline{x}]$ satisfies
$p(x_{1},\dots,x_{r+s})>0$ for all $(x_{1},\dots,x_{r+s})\in R$, then $p$ is a
sum of terms

$\displaystyle\alpha(1$ $\displaystyle-
x_{1})^{k_{1}}(1+x_{1})^{l_{1}}\cdots(1-x_{r})^{k_{r}}(1+x_{r})^{l_{r}}\times$
$\displaystyle[(1-x_{r+1}^{2})q_{1}(x_{r+1})^{2}$
$\displaystyle+p_{1}(x_{r+1})^{2}]\cdots[(1-x_{r+s}^{2})q_{s}(x_{r+s})^{2}+p_{s}(x_{r+s})^{2}],$

where $\alpha\geq 0$, $k_{1},\dots,k_{r},l_{1},\dots,l_{r}\in\mathds{N}_{0}$
and $q_{1},p_{1},\dots,q_{s},p_{s}\in\mathds{R}[x].$

This follows from Theorem 2, applied with $A_{i}=\mathds{R}[x_{i}]$. For
$i=1,\dots,r,$ we let $C_{i}$ be the Archimedean semiring of $A_{i}$ generated
by $1-x_{i}$, $1+x_{i}$ and for $j=r+1,\dots,r+s$, $C_{j}$ is the Archimedean
preordering $C_{j}$ in $A_{j}$ defined by (25).

This result can be also obtained from Proposition 7, applied to the
Archimedean semiring of $\mathds{R}_{r+s}[\underline{x}]$ generated by the
semirings $C_{i}$, $i=1,\dots,r+s$.

In the following two examples we use the unit ball

$B^{s}:=\\{(x_{1},\dots,x_{s})\in\mathds{R}^{s}:x_{1}^{2}+\cdots+x_{s}^{2}\leq
1\\}.$

######  Example 17.

$[-1,1]^{r}\times B^{s}$
Let $r,s\in\mathds{N}$ and $A:=\mathds{R}_{r+s}[\underline{x}]$. We set
$R=[-1,1]^{r}\times B_{s}$, that is,

$\displaystyle R:=\\{(x_{1},\dots,x_{r+s})\in\mathds{R}^{r+s}:-1\leq x_{1}\leq
1,\dots,-1\leq x_{r}\leq 1,x_{r+1}^{2}+\cdots+x_{r+s}^{2}\leq 1\\}.$

If $p(x)>0$ for all $x\in R$, then $p$ is a nonnegative combination of terms

$\displaystyle(1-x_{1})^{k_{1}}(1+x_{1})^{l_{1}}\cdots$
$\displaystyle(1-x_{r})^{k_{r}}(1+x_{r})^{l_{r}}\times$ (13)
$\displaystyle[(1-x_{r+1}^{2}-\cdots-x_{r+s}^{2})$ $\displaystyle
q(x_{r+1},\dots,x_{r+s})+p(x_{r+1},\dots,x_{r+s})],$

where $k_{1},\dots,k_{r},l_{1},\dots,l_{r}\in\mathds{N}_{0}$ and
$q,p\in\sum\mathds{R}[x_{r+1},\dots,x_{r+s}]^{2}.$

######  Example 18.

$B^{s}$ revisited
The cone spanned by the terms in (13) is an Archimedean quadratic module of
$\mathds{R}[x_{r+1},\dots,x_{r+s}]$ which contains all strictly positive
polynomials on the corresponding unit ball. In this example we recall [SS23,
Example 4.1] which gives an Archimedean semiring for unit ball in $B_{s}$.

Let $S$ denote the semiring of $A=\mathds{R}[x_{1},\dots,x_{s}]$ generating by
the polynomials

(14) $\displaystyle f(x):=1-x_{1}^{2}-\cdots-x_{s}^{2},\leavevmode\nobreak\
g_{j,\pm}(x):=(1\pm x_{j})^{2},\;j=1,\dots,s.$

Clearly, $\mathsf{char}(A;S)$ corresponds to the unit ball

$B^{s}\equiv K(f)=\\{x\in\mathds{R}^{d}:x_{1}^{2}+\cdots+x_{s}^{2}\leq 1\\}.$

As noted in [SS23], $S$ is Archimedean. Therefore, by Proposition 7 , if $p\in
A$ and $p(x)>0$ for all $x\in B^{s}$, then $p$ is a non-negative combination
of terms

(15) $\displaystyle(1-x_{1}^{2}-\cdots-
x_{d}^{2})^{n}(1-x_{1})^{2k_{1}}(1+x_{1})^{2\ell_{1}}\cdots(1-x_{d})^{2k_{d}}(1+x_{d})^{2\ell_{d}},$

with $n,k_{1},\ell_{1},\dots,k_{d},\ell_{s}\in\mathds{N}_{0}$.

Inserting (15) (with $x_{1},\dots,x_{s}$ replaced by $x_{r+1},\dots,x_{r+s}$)
instead of (13) we obtain another description of strictly positive polynomials
on $[-1,1]^{r}\times B^{s}$.

For later use it is convenient to have this result also for the ball

$B^{s}_{\rho}(x_{0}):=\\{\\{(x_{1},\dots,x_{s})\in\mathds{R}^{s}:(x_{1}-x_{01})^{2}+\cdots+(x_{s}-x_{0s})^{2}\leq\rho^{2}\\}$

with center $x_{0}=(x_{01},\dots,x_{0s})\in\mathds{R}^{s}$ and radius
$\rho>0$. This case is obtained from the unit ball $B^{s}$ be a linear
transformation $x_{i}\to\rho^{-1}(x_{i}-x_{0i})$. Thus, if $p\in A$ satisfies
$p(x)>0$ for all $x\in B^{s}_{\rho}(x_{0})$, then $p$ is a non-negative
combination of polynomials

$\displaystyle\big{(}\rho^{2}-(x_{1}-x_{01})^{2}-\cdots-$
$\displaystyle(x_{s}-x_{0s})^{2}\big{)}^{n}\big{(}\rho-(x_{1}-x_{01})\big{)}^{2k_{1}}\big{(}\rho+(x_{1}-x_{01})\big{)}^{2\ell_{1}}\times$
$\displaystyle\cdots\times\big{(}\rho-(x_{s}-x_{0s})\big{)}^{2k_{s}}\big{(}\rho+(x_{s}-x_{0s})\big{)}^{2\ell_{s}},$

with $n,k_{1},\ell_{1},\dots,k_{d},\ell_{s}\in\mathds{N}_{0}$.

######  Example 19.

Part of the interior of the elliptic paraboloid $x_{3}\geq
x_{1}^{2}+x_{2}^{2}$, $x_{3}\leq 1$
Let $C$ denote the semiring of $A:=\mathds{R}[x_{1},x_{2},x_{3}]$ generated by
$x_{3}-x_{1}^{2}-x_{2}^{2}$ and $x_{3}$, $1-x_{3}$,
$(1-x_{1})^{2},(1+x_{1})^{2},(1-x_{2})^{2},(1+x_{2})^{2}$. Clearly,
$\mathsf{char}(A;C)$ is the semialgebraic set

$R=\\{(x_{1},x_{2},x_{3})\in\mathds{R}^{3}:x_{3}\geq
x_{1}^{2}+x_{2}^{2},\leavevmode\nobreak\ x_{3}\leq 1\,\\}.$

For $i,j\in\\{1,2\\}$, $i\neq j$, we have

(16) $\displaystyle 2+x_{3}\pm
2x_{j}=x_{3}-x_{1}^{2}-x_{2}^{2}+\frac{1}{2}[(1+x_{i})^{2}+(1-x_{i})^{2}]+(1\pm
x_{j})^{2}\in C.$

Since $x_{3},1-x_{3}\in C$, $x_{3}\in A_{\rm bd}(C)$. Hence $3\pm
2x_{j}=(2+x_{3}\pm 2x_{j})+(1-x_{3})\in C$ by (16), so that $x_{j}\in A_{\rm
bd}(C)$ for $j=1,2$. Therefore, the semiring $C$ of $A$ is Archimedean.

Let $p\in\mathds{R}[x_{1},x_{2},x_{3}]$. If $q(x_{1},x_{2},x_{3})>0$ for all
$(x_{1},x_{2},x_{3})\in R$, it follows from Proposition 7 that $q$ is a non-
negative combination of polynomials

$\displaystyle(x_{3}-x_{1}^{2}-x_{2}^{2})^{n}(1-x_{3})^{k_{3}}x_{3}^{l_{3}}(1-x_{1})^{2k_{2}}(1+x_{1})^{2l_{2}}(1-x_{2})^{2k_{1}}(1+x_{2})^{2l_{1}},$

where $n,k_{1},l_{1},k_{2},l_{2},k_{3},l_{3}\in\mathds{N}_{0}$.

######  Example 20.

In this example we set $A:=\mathds{R}[x_{1},x_{2},x_{3}]$. Further, let
$A_{j}:=\mathds{R}[x_{j}],$ $j=1,2,3,$ and $A_{12}:=\mathds{R}[x_{1},x_{2}]$.
Clearly,

(17) $\displaystyle
C_{12}:=\big{\\{}(1-x_{1}^{2})p_{1}+(1-x_{2}^{2})p_{2}+p_{3}:\,p_{1},p_{2},p_{3}\in\sum\mathds{R}[x_{1},x_{2}]^{2}\,\big{\\}}$

is an Archimedean quadratic module of $A_{12}$ and

(18) $\displaystyle
C_{j}:=\big{\\{}(1-x_{j}^{2})q_{1}+q_{2}:\,q_{1},q_{2}\in\sum\mathds{R}[x_{j}]^{2}\,\big{\\}}$

is an Archimedean preordering of $A_{j}$.

The subalgebras $A_{12,},A_{3}$ and the cones $C_{12},C_{3}$ satisfies the
assumptions of Theorem 2. The semi-algebraic set
$\mathsf{char}(A;C_{12})\cap\mathsf{char}(A;C_{3})$ in $\mathds{R}^{3}$ is
$[-1,1]^{3}$ and $\mathsf{cone}(C_{12},C_{3})$ consists of all sums of terms

(19)
$\displaystyle[(1-x_{1}^{2})p_{1}(x_{1},x_{2})+(1-x_{2}^{2})p_{2}(x_{1},x_{2})+p_{3}(x_{1},x_{2})]\,[(1-x_{3}^{2})q_{1}(x_{3})+q_{2}(x_{3})],$

where $p_{1},p_{2},p_{3}\in\sum\mathds{R}[x_{1},x_{2}]^{2}$ and
$q_{1},q_{2}\in\sum\mathds{R}[x_{3}]^{2}$. In this case, Theorem 2 says that
if $p\in\mathds{R}[x_{1},x_{2},x_{3}]$ is positive on $[-1,1]^{3}$, then $q$
is a sum of terms (19). Note that $C_{12}$ is not a preordering and
$\mathsf{cone}(C_{12},C_{3})$ is neither a quadratic module nor a semiring.

The subalgebras $A_{1},A_{2},A_{3}$ with cones $C_{1},C_{2},C_{3}$ fulfill the
assumptions of Theorem 2 as well. This is just the case $n=3$ of Example 15
and $\mathsf{cone}(C_{1},C_{2},C_{3})$ is a semiring.

######  Example 21.

We reconsider [SS23, Example 7.1] in the context of Theorem 2. Let
$A=\mathds{R}[x_{1},x_{2}]$ and set

$f_{1}(x_{1},x_{2}):=x_{2}-(x_{1}-1/2)^{2},\leavevmode\nobreak\
\leavevmode\nobreak\ f_{2}(x_{1},x_{2}):=x_{2}-x_{1}^{2}.$

For $i=1,2$, let $A_{i}$ be the subalgebra of $A$ generated by $f_{i}$ and
$C_{i}$ the semiring of $A_{i}$ generated by $1-f_{i},1+f_{i}$. It is clear
that $C_{i}$ is Archimedean in $A_{i}$ and that $A$ is generated by $A_{1}$
and $A_{2}$, so the assumptions of Theorem 2 are fulfilled. Then
$\mathsf{char}(A,\mathsf{cone}(C_{1},C_{2}))$ corresponds to the semialgebraic
set

$K:=\\{(x_{1},x_{2})\in\mathds{R}^{2}:{-1}\leq f_{1}(x_{1},x_{2})\leq
1,\leavevmode\nobreak\ {-1}\leq f_{2}(x_{1},x_{2})\leq 1\\}.$

Therefore, by Theorem 2, each polynomial $p\in\mathds{R}[x_{1},x_{2}]$ which
is positive in all points of $K$ is a finite sum of terms

$\alpha(1-f_{1}(x_{1},x_{2}))^{i}(1+f_{1}(x_{1},x_{2}))^{j}(1-f_{2}(x_{1},x_{2})\big{)}^{k}(1+f_{2}(x_{1},x_{2}))^{\ell},$

where $\alpha\geq 0$ and $i,j,k,\ell\in\mathds{N}_{0}$.

Now suppose that $f_{1},\dots,f_{r}$ is a finite set polynomials from
$A:=\mathds{R}[x_{1},\dots,x_{n}]$ such that the semi-algebraic set
$K:=K(f_{1},\dots,f_{r})$ of $\mathds{R}^{n}$ is compact.

It is well-known that the compactness of $K(f_{1},\dots,f_{r})$ does not imply
that the quadratic module $Q$ generated by $f_{1},\dots,f_{r}$ is Archimedean,
so in general the Archimedean Positivstellensatz for quadratic modules does
not apply. Similarly, if the semi-algebraic set obtained from a semiring $S$
is compact, then $S$ is not necessarily Archimedean. In order to apply the
corresponding Archimedean Positivstellensatz one has to enlarge $Q$ or $S$,
respectively. As noted above, we want to obtain representations for the
positive polynomials on $K(f_{1},\dots,f_{r})$ with ”small” classes of squares
or polynomials. To achieve this goal this we propose to proceed as follows.

We choose subalgebras $A_{i}$, $i=1,\dots,m$, and Archimedean quadratic
modules or semirings $C_{i}$ of $A_{i}$ such that $A$ is generated by
$A_{1},\dots,A_{m}$ and the semi-algebraic set corresponding to
$\cap_{i=1}^{m}\mathsf{char}(A;C_{i})$ contains $K(f_{1},\dots,f_{r})$. This
is possible, because $K(f_{1},\dots,f_{r})$ is compact. Let $M$ denote the
unital cone of $A$ defined by

(20) $\displaystyle
M:=\\{\lambda_{0}f_{0}+\lambda_{1}f_{1}+\cdots+\lambda_{r}f_{r}:\,\lambda_{0}\geq
0,\lambda_{1}\geq 0,\dots,\lambda_{r}\\},\leavevmode\nobreak\
\leavevmode\nobreak\ \textrm{where}\leavevmode\nobreak\ f_{0}:=1.$

Then

(21)
$\displaystyle\mathsf{char}(A;M)\cap_{i=1}^{m}\mathsf{char}(A;C_{i})=\mathsf{char}(A;M)=K(f_{1},\dots,f_{r}).$

Therefore, by Theorem 2, if $p\in\mathds{R}_{n}[\underline{x}]$ and $p(x)>0$
for all $x\in K(f_{1},\dots,f_{r})$, then
$p\in\mathsf{cone}(M,\mathsf{cone}(C_{1},\dots,C_{m}))$, that is, $p$ is a sum
of polynomials

(22) $\displaystyle f_{j}\,\alpha\,c_{1}\cdots c_{m},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ {\textrm{w}here}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \alpha\geq 0,\leavevmode\nobreak\
c_{1}\in C_{1},\dots,c_{m}\in C_{m}\leavevmode\nobreak\ \leavevmode\nobreak\
\textrm{and}\leavevmode\nobreak\ \leavevmode\nobreak\ j=0,\dots,r.$

Note that in (22) there are no mixed products of the polynomials
$f_{1},\dots,f_{r}$.

That is, the algebras $A_{i}$ and cones $C_{i}$ are choosen such that
$\mathsf{cone}(C_{1},\dots,C_{m})$ is Archimedean and
$K(f_{1},\dots,f_{r})\subseteq\cap_{i=1}^{m}\mathsf{char}(A;C_{i})$. The terms
$f_{j}$ in (22) are only needed to ensure that the semi-algebraic set
$K(f_{1},\dots,f_{r})$ is the corresponding set (21) of characters.

There is a lot of freedom in choosing the cones $C_{i}$. For instance, one may
have an $n$-dimensional cube, rectangle, or ball as corresponding set
$\cap_{i=1}^{m}\mathsf{char}(A;C_{i})$ and then apply Examples 15, 16, 17, or
18. We illustrate this by a very simple example, the famous Jacobi-Prestel
counter-example [JP01, Example 4.6].

######  Example 22.

$n=2$, $f_{1}=x_{1}-\frac{1}{2},f_{2}=x_{2}-\frac{1}{2},f_{3}=1-x_{1}x_{2}$.
Then $K:=K(f_{1},f_{2},f_{3})$ is a compact set bounded by the hyperbola
$1=x_{1}x_{2}$ and the two lines $x_{1}=\frac{1}{2}$, $x_{1}=\frac{1}{2}$. As
noted in [JP01], the quadratic module of $\mathds{R}[x_{1},x_{2}]$ generated
by $f_{1},f_{2},f_{3}$ is not Archimedean . How to repair this?

We set $A_{1}=\mathds{R}[x_{1}],A_{2}=\mathds{R}[x_{2}]$. and consider two
embeddings of $K(f_{1},f_{2},f_{3})$.

Case 1: Embed $K(f_{1},f_{2},f_{3})$ into the square $[1/2,2]\times[1/2,2].$

Then there are two possibilities. For the first we take $C_{i}$, $i=1,2,$ to
be the semiring generated by $2-x_{i}$ and $x_{i}-\frac{1}{2}$. Clearly,
$C_{i}$ is an Archimedean semring of $A_{i}$. Then
$\mathsf{cone}(M,\mathsf{cone}(C_{1},C_{2}))$ is the unital cone spanned by
$2-x_{1},2-x_{2},x_{1}-\frac{1}{2},x_{2}-\frac{1}{2}$ and $f_{3}$. Therefore,
if $p\in\mathds{R}[x_{1},x_{2}]$ and $p(x)>0$ for all $x\in
K(f_{1},f_{2},f_{3})$, then $p$ is a non-negative combination of terms

(23)
$\displaystyle(2-x_{1})^{k_{1}}(x_{1}-1/2)^{l_{1}}(2-x_{2})^{k_{2}}(x_{2}-1/2)^{l_{2}}\leavevmode\nobreak\
\textrm{and}$ (24) $\displaystyle
f_{3}\,(2-x_{1})^{k_{1}}(x_{1}-1/2)^{l_{1}}(2-x_{2})^{k_{2}}(x_{2}-1/2)^{l_{2}},$

where $k_{1},k_{2},l_{1},l_{2}\in\mathds{N}_{0}$.

For the second possibility we let $C_{i}$, $i=1,2$, be the Archimedean
preordering

(25) $\displaystyle
C_{i}:=\\{(2-x_{i})(x_{i}-1/2)q_{i}(x_{i})^{2}+p_{i}(x_{i})^{2}\,:q_{i},p_{i}\in\mathds{R}[x_{i}]\\}.$

in $A_{i}$. Then, by Theorem 2, if $p(x)>0$ for all $x\in
K(f_{1},f_{2},f_{3})$, then $p$ is a non-negative combination of polynomials

$\displaystyle
f_{i}(x_{1},x_{2})[(2{-}x_{1})(x_{1}{-}1/2)q_{1}(x_{1})^{2}+p_{1}(x_{1})^{2}]\,((2{-}x_{2})(x_{2}{-}1/2)q_{2}(x_{2})^{2}+p_{2}(x_{2})^{2}],$

where $i=0,1,2,3$ and $q_{1},p_{1},q_{2},p_{2}\in\mathds{R}[x]$. Here we have
set $f_{0}=1$.

Case 2: Embed $K(f_{1},f_{2},f_{3})$ into the dics $B^{2}_{\rho}(x_{0})$ with
center $x_{0}=(5/4,5/4)$ and radius $\rho=\sqrt{2}\,\frac{3}{4}=\sqrt{18}/4$.

Then, if $p\in\mathds{R}[x_{1},x_{2}]$ satisfies $p(x_{1},x_{2})>0$ for all
$(x_{1},x_{2})\in K(f_{1},f_{2},f_{3})$, it follows from (22) and the formula
for $B^{2}_{\rho}(x_{0})$ in Example 18 that $p$ is a sum of polynomials

$\displaystyle f_{j}\,\alpha\big{(}9/8-(x_{1}{-}5/4)^{2}$
$\displaystyle-(x_{2}{-}5/4)^{2}\big{)}^{n}\big{(}\sqrt{18}/4-(x_{1}{-}5/4)\big{)}^{2k_{1}}\big{(}\sqrt{18}/4+(x_{1}{-}5/4)\big{)}^{2\ell_{1}}$
$\displaystyle\times\big{(}\sqrt{18}/4-(x_{2}{-}5/4)\big{)}^{2k_{2}}\big{(}\sqrt{18}/4+(x_{2}{-}5/4)\big{)}^{2\ell_{2}},$

where $\alpha\geq 0$, $j=1,2,3$ and
$n,k_{1},\ell_{1},k_{2},\ell_{2}\in\mathds{N}_{0}$.

######  Remark 23.

In this paper we have tried to express positive polynomials on compact semi-
algebraic sets such that small classes of elements or squares are needed.
There are a number of natural questions on this matter. For instance, one may
ask whether the following is true: Each polynomial which is positive on the
square $[0,1]^{2}$ is a finite sum of terms

(26)
$\displaystyle(1-x_{1}^{2})p_{1}(x_{1})^{2}q_{1}(x_{2})^{2}+(1-x_{2}^{2})p_{2}(x_{1})^{2}q_{2}(x_{2})^{2}+p_{3}(x_{1})^{2}q_{3}(x_{2})^{2},$

where $p_{1},p_{2},p_{3},q_{1},q_{2},q_{3}\in\mathds{R}[x]$.

## References

  * [H36] Haviland, E.K.: On the moment problem for distribution functions in more than one dimension II, 58(1936), 164–168.
  * [J01] Jacobi, T.: A representation theorem for certain partially ordered commutative rings, Math. Z. 23(2001), 259–273.
  * [JP01] Jacobi, T. and A. Prestel: Distinguished representations of strictly positive polynomials, J. reine Angew. Math. 532(2001), 223–235.
  * [Kv64] Krivine, J.L.: Quelques propriétés des préordres dans les anneaux commutatifs unitaires, C. R. Acad. Sci. Paris 258(1964), 3417–3418.
  * [KM02] Kuhlmann, S. and M. Marshall: Positivity, sums of squares and the multi-dimensional moment problem, Trans. Amer. Math. Soc. 354(2002), 4285–4302.
  * [M08] Marshall, M.: Positive Polynomials and Sums of Squares, Math. Surveys and Monographs, Amer. Math. Soc., Providence, R.I., 2008.
  * [PD01] A. Prestel and C.N. Delzell: Positive Polynomials, Monographs in Math., Springer-Verlag, Berlin, 2001.
  * [S17] Schmüdgen, K.: The Moment Problem, Graduate Texts in Math., Springer-Verlag, Cham, 2017.
  * [SS23] Schmüdgen, K. and Schötz, M.: Positivstellensätze for semirings, Math. Ann. 2023, https://doi.org/10.1007/s00208-023-02656-0
  * [S23] Schmüdgen, K.: Chapter 12 of [S17]: The moment problem on compact semi-algebraic sets (revised version), ArXiv 2309.10052.


# Rates of asymptotic regularity of the Tikhonov-Mann iteration for families
of mappings

Horaţiu Chevala
a Research Center for Logic, Optimization and Security (LOS), Department of
Computer Science,
Faculty of Mathematics and Computer Science, University of Bucharest.
Academiei 14, 010014 Bucharest, Romania
E-mail<EMAIL_ADDRESS>
###### Abstract

In this paper we generalize the strongly convergent Krasnoselskii-Mann-type
iteration for families of nonexpansive mappings defined recently by Boţ and
Meier in Hilbert spaces to the abstract setting of $W$-hyperbolic spaces and
we compute effective rates of asymptotic regularity for our generalization.
This also generalizes recent results by Leuştean and the author on the
Tikhonov-Mann iteration from single mappings to families of mappings.
Keywords: Mann iteration, Rates of asymptotic regularity, Tikhonov
regularization, Common fixed points, Proof mining
Mathematics Subject Classification: 47J25, 47H09, 03F10

##  1 Introduction

In [4], Boţ and Meier propose a strongly convergent Krasnoselskii-Mann-type
iteration for finding a common fixed point of a family $(T_{n}:H\to H)$ of
nonexpansive self-mappings of a Hilbert space. They define the sequence
$(x_{n})$ by

$\displaystyle
x_{n+1}=(1-\lambda_{n})\beta_{n}x_{n}+\lambda_{n}T_{n}(\beta_{n}x_{n}),$ (1)

where $x_{0}\in H$ is an arbitrary starting point and $(\lambda_{n})$,
$(\beta_{n})$ are sequences in $[0,1]$. Theorem 3.1 of [4] states that, under
some conditions on $(\lambda_{n}),(\beta_{n})$ and $(T_{n})$,

$\displaystyle\lim\limits_{n\to\infty}\left\lVert
x_{n}-T_{n}x_{n}\right\rVert=0,$ (2)

and, furthermore, that if $(T_{n})$ satisfies an additional asymptotic
condition, then $(x_{n})$ converges strongly to a common fixed point of
$(T_{n})$. As a part of the proof of [4, Theorem 3.1], it is also established
that

$\displaystyle\lim\limits_{n\to\infty}\left\lVert
x_{n}-x_{n+1}\right\rVert=0.$ (3)

Properties (3) and (2) are called the asymptotic, respectively the
$(T_{n})$-asymptotic regularity of $(x_{n})$, and are important notions in
optimization and nonlinear analysis, the first one going back to Browder and
Petryshyn [7] being later extended by Borwein, Reich and Shafrir [5].
Furthermore, they serve as key steps in many convergence proofs, including the
one of [4, Theorem 3.1].

The case when $(T_{n})$ is constant in iteration (1) was studied and proven
strongly convergent by Yao, Zhou and Liou [25] and recently by Boţ, Csetnek
and Meier [3]. Also, the single operator case was generalized by Leuştean and
the author [9] to $W$-hyperbolic spaces, where quadratic rates of asymptotic
regularity were obtained. Even better, linear, rates were provided by
Kohlenbach, Leuştean and the author [8] in the same setting. A further
generalization in the single mapping case was introduced in [11] under the
name of alternating Halpern-Mann iteration, proven there to be strongly
convergent in CAT(0) spaces, and later also studied in $W$-hyperbolic spaces
in [19].

In this paper, we generalize iteration (1) from Hilbert spaces to the much
more abstract setting of $W$-hyperbolic space and prove that (3) and (2) also
hold for our generalization. Furthermore, our proofs are quantitative,
providing explicit _rates of asymptotic regularity_ for the iteration. Our
results can also be viewed as a generalization of those in [9] from single
mappings to families of mappings.

The results in this paper are part of the program of _proof mining_ [14, 17]
developed by Kohlenbach, which seeks to obtain new quantitative results via
the proof-theoretical analysis of mathematical proofs.

##  2 Preliminary notions

###  2.1 Quantitative notions

First let us recall the quantitative notions in terms of which our main
results will be expressed. Let $(a_{n})$ be a sequence in a metric space
$(X,d)$ and $a\in X$ be a point. A function $\varphi:\mathbb{N}\to\mathbb{N}$
is a _rate of convergence_ for $(a_{n})$ to $a$ if

$\displaystyle\forall k\in\mathbb{N}\forall
n\geq\varphi(k)\left(d(a_{n},a)\leq\frac{1}{k+1}\right).$

A function $\chi:\mathbb{N}\to\mathbb{N}$ is a _Cauchy modulus_ for $(a_{n})$
if

$\displaystyle\forall k\in\mathbb{N}\forall n\geq\chi(k)\forall
j\in\mathbb{N}\left(d(a_{n},a_{n+j})\leq\frac{1}{k+1}\right).$

A _rate of asymptotic regularity_ for $(a_{n})$ is a rate of convergence to
$0$ for the sequence $(d(x_{n},x_{n+1}))$. Given a mapping $T:X\to X$, a rate
of $T$-asymptotic regularity for $(x_{n})$ is a rate of convergence to $0$ for
$(d(x_{n},Tx_{n}))$, and given a family $(T_{n}:X\to X)$ of self-mappings of
$X$, a rate of $(T_{n})$-asymptotic regularity of $(x_{n})$ is a rate of
convergence to $0$ for the sequence $(d(x_{n},T_{n}x_{n}))$.

A rate of divergence for a series $\sum\limits_{n=0}^{\infty}b_{n}$ of
nonnegative real numbers is a function $\theta:\mathbb{N}\to\mathbb{N}$ such
that

$\displaystyle\forall k\in\mathbb{N}\left(\sum_{n=0}^{\theta(k)}b_{n}\geq
k\right).$

###  2.2 $W$-hyperbolic spaces

Following [9], we say that a _$W$ -space_ is a metric space $(X,d)$ endowed
with a mapping $W:X\times X\times[0,1]\to X$. The intended interpretation for
$W(x,y,\lambda)$ is that of an abstract convex combination of parameter
$\lambda$ between the two points $x$ and $y$. Hence, instead of $W$,
throughout the paper we will use the notation

$\displaystyle(1-\lambda)x+\lambda y=W(x,y,\lambda).$

######  Definition 2.1.

A $W$-space $(X,d,W)$ is said to be a _$W$ -hyperbolic space_ if it satisfies
the following axioms, for all $x,y,z,w\in X$ and $\lambda,\theta\in[0,1]$:
(W1) $d(z,(1-\lambda)x+\lambda y)\leq(1-\lambda)d(z,x)+\lambda d(z,y)$, (W2)
$d((1-\lambda)x+\lambda y,(1-\theta)x+\theta
y)=\left|\lambda-\theta\right|d(x,y)$, (W3) $(1-\lambda)x+\lambda y=\lambda
y+(1-\lambda)x$, (W4) $d((1-\lambda)x+\lambda z,(1-\lambda)y+\lambda
w)\leq(1-\lambda)d(x,y)+\lambda d(z,w)$.

Takahashi [23] already studied $W$-spaces satisfying (W1), while full
$W$-hyperbolic spaces were introduced by Kohlenbach [13]. Examples of
$W$-hyperbolic spaces include all normed spaces, as well as structures from
geodesic geometry, such as Busemann spaces [21] and CAT(0) spaces [1, 6].

Throughout this paper, unless otherwise mentioned, $(X,d,W)$ is a
$W$-hyperbolic space.

######  Proposition 2.2.

The following hold, for all $x,y,z,w\in X$ and $\lambda,\theta\in[0,1]$.

  1. (i)

$d(x,(1-\lambda)x+\lambda y)=\lambda d(x,y)$ and $d(y,(1-\lambda)x+\lambda
y)=(1-\lambda)d(x,y)$;

  2. (ii)

$d((1-\lambda)x+\lambda z,(1-\theta)y+\theta w)\leq(1-\lambda)d(x,y)+\lambda
d(z,w)+\left|\lambda-\theta\right|d(y,w)$;

  3. (iii)

$d((1-\lambda)x+\lambda z,(1-\theta)x+\theta w)\leq\lambda
d(z,w)+\left|\lambda-\theta\right|d(x,w)$.

###### Proof.

See [9, Lemma 2.1]. ∎

##  3 Main results

Let $(T_{n}:X\to X)$ be a sequence of nonexpansive operators (i.e.
$d(T_{n}x,T_{n}y)\leq d(x,y)$ for $x,y\in X$), $(\lambda_{n})$ and
$(\beta_{n})$ be sequences in $[0,1]$, and $x_{0},u\in X$ be two arbitrary
points. We define the _Tikhonov-Mann iteration_ associated to the family
$(T_{n})$ with parameters $(\lambda_{n}),(\beta_{n})$, anchor point $u$ and
starting point $x_{0}$ by

$\displaystyle x_{n+1}$
$\displaystyle=(1-\lambda_{n})u_{n}+\lambda_{n}T_{n}u_{n},\quad\text{where}$
(4) $\displaystyle u_{n}$ $\displaystyle=(1-\beta_{n})u+\beta_{n}x_{n}.$ (5)

If $W$ is a Hilbert space, with the choice $u=0$ we recover the iteration from
[4] and if $(T_{n})$ is a constant sequence we get the Tikhonov-Mann iteration
from [9].

We will consider the following quantitative conditions on the parameters of
the iteration.

$(\operatorname{C}1_{q})$ |  $\prod\limits_{n=0}^{\infty}\beta_{n+1}=0$ with rate of convergence $\sigma$,
---|---
$(\operatorname{C}2_{q})$ |  $\sum\limits_{n=0}^{\infty}\left|\beta_{n+1}-\beta_{n}\right|$ is convergent with Cauchy modulus $\chi_{\beta}$,
$(\operatorname{C}3_{q})$ |  $\sum\limits_{n=0}^{\infty}\left|\lambda_{n+1}-\lambda_{n}\right|$ is convergent with Cauchy modulus $\chi_{\lambda}$,
$(\operatorname{C}4_{q})$ |  $\lim\limits_{n\to\infty}\beta_{n}=1$ with rate of convergence $\eta$,
$(\operatorname{C}5_{q})$ |  $\Lambda\in\mathbb{N}^{*}$ and $N_{\Lambda}\in\mathbb{N}$ are such that $\lambda_{n}\geq\frac{1}{\Lambda}$ for all $n\geq N_{\Lambda}$,
$(\operatorname{C}6_{q})$ |  $\sum\limits_{n=0}^{\infty}d(T_{n+1}u_{n},T_{n}u_{n})$ is convergent with Cauchy modulus $\chi_{T}$.

These are quantitative analogues of the conditions from [4, Theorem 2.1], with
the caveat that the condition that
$\sum\limits_{n=0}^{\infty}(1-\beta_{n})=\infty$ used in that paper is
replaced with the equivalent, when $\beta_{n}>0$, condition that
$\prod\limits_{n=0}^{\infty}\beta_{n+1}=0$. The reason we choose this
reformulation is that it allows us to get better rates of asymptotic
regularity, as observed first by Kohlenbach [15], who used it to obtain
polynomial rates of asymptotic regularity for the Halpern iteration for the
first time.

For a mapping $T:X\to X$, let us denote by $\operatorname{Fix}(T)=\left\\{x\in
X\mid Tx=x\right\\}$ its set of fixed points. In the rest of this paper, let
$F=\bigcap\limits_{n\in\mathbb{N}}\operatorname{Fix}(T_{n})$ be the set of
common fixed points of the family $(T_{n})$, and assume it to be nonempty. The
following lemma provides some useful upper bounds on the sequences involved.

######  Lemma 3.1.

Let $p\in F$ be a common fixed point. Define

$\displaystyle
M=\left\lceil\max\left\\{d(x_{0},p),d(u,p)\right\\}\right\rceil.$ (6)

Then, for all $n\in\mathbb{N}$, the following bounds hold:

  1. (i)

$d(x_{n},p)\leq M$ and $d(x_{n},u)\leq 2M$;

  2. (ii)

$d(u_{n},p)\leq M$ and $d(u_{n},T_{n}u_{n})\leq 2M$.

###### Proof.

All the inequalities are easily proved by adapting the proofs of [9, Lemma
3.1], replacing $T$ with $T_{n}$.

∎

The following lemma establishes the main recursive inequality on $(x_{n})$
that will allow us to obtain its asymptotic regularity.

######  Lemma 3.2.

Let $p\in F$ and $M$ be defined by (6). For all $n\in\mathbb{N}$, the
following hold:

$\displaystyle d(u_{n+1},u_{n})\leq$ $\displaystyle\ \
\beta_{n+1}d(x_{n+1},x_{n})+2M\left|\beta_{n+1}-\beta_{n}\right|;$ (7)
$\displaystyle\begin{split}d(x_{n+2},x_{n+1})\leq&\ \
\beta_{n+1}d(x_{n+1},x_{n})+d(T_{n+1}u_{n},T_{n}u_{n})\\\
&+2M(\left|\lambda_{n+1}-\lambda_{n}\right|+\left|\beta_{n+1}-\beta_{n}\right|)\end{split}$
(8)

###### Proof.

The proofs follow those of [9, Proposition 3.2.(6), (7)]. For (7) we have
that, for all $n\in\mathbb{N}$,

$\displaystyle d(u_{n+1},u_{n})$
$\displaystyle\leq\beta_{n+1}d(x_{n+1},x_{n})+\left|\beta_{n+1}-\beta_{n}\right|d(u,x_{n})\quad\text{by
Lemma \ref{prop:W-derived}.\ref{prop:W-derived:common-left-endpoint}}$
$\displaystyle\leq\beta_{n+1}d(x_{n+1},x_{n})+2M\left|\beta_{n+1}-\beta_{n}\right|\quad\text{from
Lemma \ref{lem:basic-bounds}.\ref{lem:basic-bounds:x-u}}.$

For (8), let $n\in\mathbb{N}$. Then

$\displaystyle d(x_{n+2},x_{n+1})\leq$ $\displaystyle\
(1-\lambda_{n+1})d(u_{n+1},u_{n})+\lambda_{n}d(T_{n+1}u_{n+1},T_{n}u_{n})$
$\displaystyle+\left|\lambda_{n+1}-\lambda_{n}\right|d(u_{n},T_{n}u_{n})\quad\text{by
Lemma \ref{prop:W-derived}.\ref{prop:W-derived:general}}$ $\displaystyle\leq$
$\displaystyle\
(1-\lambda_{n+1})d(u_{n+1},u_{n})+\lambda_{n}d(T_{n+1}u_{n+1},T_{n}u_{n})$
$\displaystyle+2M\left|\lambda_{n+1}-\lambda_{n}\right|\quad\text{by Lemma
\ref{lem:basic-bounds}.\ref{lem:basic-bounds:Tu-u}}$ $\displaystyle\leq$
$\displaystyle\
(1-\lambda_{n+1})d(u_{n+1},u_{n})+2M\left|\lambda_{n+1}-\lambda_{n}\right|$
$\displaystyle+\lambda_{n}(d(T_{n+1}u_{n+1},T_{n+1}u_{n})+d(T_{n+1}u_{n},T_{n}u_{n}))$
$\displaystyle\leq$ $\displaystyle\
(1-\lambda_{n+1})d(u_{n+1},u_{n})+2M\left|\lambda_{n+1}-\lambda_{n}\right|$
$\displaystyle+\lambda_{n}(d(u_{n+1},u_{n})+d(T_{n+1}u_{n},T_{n}u_{n}))$ since
$T_{n+1}$ is nonexpansive $\displaystyle=$ $\displaystyle
d(u_{n+1},u_{n})+\lambda_{n}d(T_{n+1}u_{n},T_{n}u_{n})+2M\left|\lambda_{n+1}-\lambda_{n}\right|$
$\displaystyle\leq$ $\displaystyle\
\beta_{n+1}d(x_{n+1},x_{n})+\lambda_{n}d(T_{n+1}u_{n},T_{n}u_{n})$
$\displaystyle+2M(\left|\lambda_{n+1}-\lambda_{n}\right|+\left|\beta_{n+1}-\beta_{n}\right|)\quad\text{from
\eqref{lem:rec-bounds:u-succ-u}}$ $\displaystyle\leq$ $\displaystyle\
\beta_{n+1}d(x_{n+1},x_{n})+d(T_{n+1}u_{n},T_{n}u_{n})$
$\displaystyle+2M(\left|\lambda_{n+1}-\lambda_{n}\right|+\left|\beta_{n+1}-\beta_{n}\right|)$
$\displaystyle\text{because $0\leq\lambda_{n}\leq 1$}.$

∎

The next inequalities will be used to derive the $(T_{n})$-asymptotic
regularity of $(x_{n})$, and their proofs follows [9, Proposition 3.2].

######  Lemma 3.3.

For all $n\in\mathbb{N}$, the following hold:

  1. (i)

$d(u_{n},T_{n}x_{n})\leq(1-\beta_{n})d(u,T_{n}x_{n})+\beta_{n}d(x_{n},T_{n}x_{n})$;

  2. (ii)

$d(x_{n},T_{n}x_{n})\leq
d(x_{n},x_{n+1})+(1-\beta_{n})d(u,x_{n})+(1-\lambda_{n})d(x_{n},T_{n}x_{n})$;

  3. (iii)

$\lambda_{n}d(x_{n},T_{n}x_{n})\leq d(x_{n},x_{n+1})+2M(1-\beta_{n})$.

###### Proof.

  1. (i)

For all $n\in\mathbb{N}$,

$\displaystyle d(u_{n},T_{n}x_{n})\leq$ $\displaystyle\
d(u_{n},(1-\beta_{n})u+\beta_{n}T_{n}x_{n})+d((1-\beta_{n})u+\beta_{n}T_{n}x_{n},T_{n}x_{n})$
$\displaystyle\leq$ $\displaystyle\
d(u_{n},(1-\beta_{n})u+\beta_{n}T_{n}x_{n})+(1-\beta_{n})d(u,T_{n}x_{n})$ by
Proposition 2.2.(i) $\displaystyle\leq$ $\displaystyle\
\beta_{n}d(x_{n},T_{n}x_{n})+(1-\beta_{n})d(u,T_{n}x_{n})\quad\text{by (W4)}.$

  2. (ii)

For all $n\in\mathbb{N}$,

$\displaystyle d(x_{n},T_{n}x_{n})\leq$ $\displaystyle\
d(x_{n},x_{n+1})+d(x_{n+1},T_{n}x_{n})$ $\displaystyle\leq$ $\displaystyle\
d(x_{n},x_{n+1})+(1-\lambda_{n})d(u_{n},T_{n}x_{n})+\lambda_{n}d(T_{n}u_{n},T_{n}x_{n})$
by (W1) $\displaystyle\leq$ $\displaystyle\
d(x_{n},x_{n+1})+(1-\lambda_{n})d(u_{n},T_{n}x_{n})+\lambda_{n}d(u_{n},x_{n})$
by the nonexpansiveness of $T_{n}$ $\displaystyle\leq$ $\displaystyle\
d(x_{n},x_{n+1})+(1-\lambda_{n})(1-\beta_{n})d(u,T_{n}x_{n})$
$\displaystyle+(1-\lambda_{n})\beta_{n}d(x_{n},T_{n}x_{n})+\lambda_{n}d(u_{n},x_{n})$
$\displaystyle=$ $\displaystyle\
d(x_{n},x_{n+1})+(1-\lambda_{n})(1-\beta_{n})d(u,T_{n}x_{n})$
$\displaystyle+(1-\lambda_{n})\beta_{n}d(x_{n},T_{n}x_{n})+\lambda_{n}(1-\beta_{n})d(u,x_{n})$
by (W4) $\displaystyle\leq$ $\displaystyle\
d(x_{n},x_{n+1})+(1-\lambda_{n})(1-\beta_{n})(d(u,x_{n})+d(x_{n},T_{n}x_{n}))$
$\displaystyle+(1-\lambda_{n})\beta_{n}d(x_{n},T_{n}x_{n})+\lambda_{n}(1-\beta_{n})d(u,x_{n})$
$\displaystyle=$ $\displaystyle\
d(x_{n},x_{n+1})+(1-\beta_{n})d(u,x_{n})+(1-\lambda_{n})d(x_{n},T_{n}x_{n}).$

  3. (iii)

Starting from (ii)

$\displaystyle d(x_{n},T_{n}x_{n})$ $\displaystyle\leq
d(x_{n},x_{n+1})+(1-\beta_{n})d(u,x_{n})+(1-\lambda_{n})d(x_{n},T_{n}x_{n}),$

move the last term to the left-hand side to get that

$\displaystyle\lambda_{n}d(x_{n},T_{n}x_{n})$ $\displaystyle\leq
d(x_{n},x_{n+1})+(1-\beta_{n})d(u,x_{n}).$

Apply Lemma 3.1.(i) to get the conclusion.

∎

Finally, before the main theorems of the paper, let us give sufficient
conditions for a family $(T_{n})$ to satisfy $(\operatorname{C}6_{q})$.

######  Proposition 3.4.

Let $(\gamma_{n})$ be a sequence of positive reals satisfying the following
conditions:

$(\operatorname{C}7_{q})$ |  $\sum\limits_{n=0}^{\infty}\left|{\gamma_{n+1}-\gamma_{n}}\right|$ is convergent with Cauchy modulus ${\chi_{\gamma}}$;
---|---
$(\operatorname{C}8_{q})$ |  $\Gamma\in\mathbb{N}^{*}$ and $N_{\Gamma}\in\mathbb{N}$ are such that $\gamma_{n}\geq\frac{1}{\Gamma}$ for all $n\geq N_{\Gamma}$.

Suppose the family of operators $(T_{n}:X\to X)$ satisfies the following
condition with respect to $(\gamma_{n})$: for all $x\in X$ and
$m,n\in\mathbb{N}$,

$\displaystyle
d(T_{m}x,T_{n}x)\leq\frac{\left|\gamma_{m}-\gamma_{n}\right|}{\gamma_{n}}d(T_{n}x,x).$
(9)

Then, $(T_{n})$ satisfies condition $(\operatorname{C}6_{q})$ with $\chi_{T}$
given by

$\displaystyle\chi_{T}(k)=\max\left\\{N_{\Gamma},{\chi_{\gamma}}(2M\Gamma(k+1)-1)\right\\}.$

###### Proof.

Let $k,j\in\mathbb{N}$ and $n\geq\chi_{T}(k)$. Then,

$\displaystyle\sum_{i=n+1}^{n+j}d(T_{i+1}u_{i},T_{i}u_{i})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:jP2-consequence}}}{{\leq}}\sum_{i=n+1}^{n+j}\frac{\left|{\gamma_{n}-\gamma_{i+1}}\right|}{\gamma_{i}}d(u_{i},T_{i}u_{i})$
$\displaystyle\leq\Gamma\sum_{i=n+1}^{n+j}{\left|{\gamma_{n}-\gamma_{i+1}}\right|}d(u_{i},T_{i}u_{i})\quad\text{by
$(\operatorname{C}8_{q})$}$ $\displaystyle\leq
2M\Gamma\sum_{i=n+1}^{n+j}{\left|{\gamma_{n}-\gamma_{i+1}}\right|}\quad\text{by
Lemma~{}\ref{lem:basic-bounds}.\ref{lem:basic-bounds:Tu-u}}$
$\displaystyle\leq 2M\Gamma\frac{1}{2M\Gamma(k+1)}\quad\text{by
$(\operatorname{C}7_{q})$}$ $\displaystyle=\frac{1}{k+1}$

∎

Conditions $(\operatorname{C}7_{q})$ and $(\operatorname{C}8_{q})$ are
quantitative versions of those imposed in [4, Theorem 3.1] and are used there
to derive (9). [18] provides a large class of mappings satisfying Condition
(9), named Condition $(C1)$ in that paper: it is shown there that if $X$ is a
CAT(0) space and the family $(T_{n})$ is _jointly $(P_{2})$ with respect to
$(\gamma_{n})$_, then $(T_{n})$ satifies (9).

###  3.1 General rates of asymptotic regularity

######  Theorem 3.5.

Let $p\in F$ be a common fixed point of $(T_{n})$ and $M$ be defined by (6).
Furthermore, define

$\displaystyle\chi(k)=\max\left\\{\chi_{T}(2(k+1)-1),\chi_{\lambda}(8M(k+1)-1),\chi_{\beta}(8M(k+1)-1)\right\\}.$
(10)

Suppose conditions $(\operatorname{C}1_{q})$, $(\operatorname{C}2_{q})$,
$(\operatorname{C}3_{q})$ and $(\operatorname{C}6_{q})$ are satisfied and that
$\psi_{0}:\mathbb{N}\to\mathbb{N}^{*}$ is such that

$\displaystyle\frac{1}{\psi_{0}(k)}\leq\prod_{n=0}^{\chi(3k+2)}\beta_{n+1}.$

Then $(x_{n})$ is $(T_{n})$-asymptotically regular with rate

$\displaystyle{{\Sigma}}(k)=\max\left\\{\sigma(6M(k+1)\psi_{0}(k)-1),\chi(3k+2)+1\right\\}+1.$

###### Proof.

We will apply Proposition 5.2.(ii) of [9], which is a particular case of
quantitative versions of a well-known Lemma by Xu [24] proved in [16, 20],
with

$\displaystyle s_{n}$ $\displaystyle=d(x_{n},x_{n+1}),$ $\displaystyle a_{n}$
$\displaystyle=1-\beta_{n},$ $\displaystyle c_{n}$
$\displaystyle=d(T_{n+1}u_{n},T_{n}u_{n})+2M(\left|\lambda_{n+1}-\lambda_{n}\right|+\left|\beta_{n+1}-\beta_{n}\right|),$
$\displaystyle L$ $\displaystyle=2M.$

We proceed to show that the conditions of that proposition are fulfilled.

Claim: $\chi$, as defined by (10), is a Cauchy modulus for
$\sum\limits_{n=0}^{\infty}c_{n}$.

Proof of claim: For brevity, denote
$\widehat{c}_{n}=\sum\limits_{i=0}^{n}c_{i}$,
$\widehat{t}_{n}=\sum\limits_{i=0}^{n}d(T_{i+1}u_{i},T_{i}u_{i})$,
$\widehat{\lambda}_{n}=\sum\limits_{i=0}^{n}\left|\lambda_{n+1}-\lambda_{n}\right|$
and
$\widehat{\beta}_{n}=\sum\limits_{i=0}^{n}\left|\beta_{n+1}-\beta_{n}\right|$,
so that

$\displaystyle\widehat{c}_{n}=\widehat{t}_{n}+2M(\widehat{\lambda}_{n}+\widehat{\beta}_{n}).$

Let $k\in\mathbb{N}$ and $n\geq\chi(k)$ and $j\in\mathbb{N}$. Given the
definition of $\chi$ and the fact that $\chi_{T}$, $\chi_{\lambda}$ and
$\chi_{\beta}$ are Cauchy moduli for $(\widehat{t}_{n})$,
$(\widehat{\lambda}_{n})$ and $(\widehat{\beta}_{n})$ respectively, we get
that

$\displaystyle\widehat{c}_{n+j}-\widehat{c}_{n}$
$\displaystyle=\widehat{t}_{n+j}-\widehat{t}_{n}+2M(\widehat{\lambda}_{n+j}-\widehat{\lambda}_{n}+\widehat{\beta}_{n+j}-\widehat{\beta}_{n})$
$\displaystyle\leq\frac{1}{2(k+1)}+2M\left(\frac{1}{8M(k+1)}+\frac{1}{8M(k+1)}\right)$
$\displaystyle=\frac{1}{k+1}.$

$\blacksquare$

This claim, together with Lemma 3.2.(8) shows that we are in the conditions to
apply [9, Proposition 5.2.(ii)] and obtain our result. ∎

###  3.2 General rates of $(T_{n})$-asymptotic regularity

The following lemma shows that in the presence of conditions
$(\operatorname{C}4_{q})$, $(\operatorname{C}5_{q})$, the asymptotic
regularity of $(x_{n})$ also implies its $(T_{n})$-asymptotic regularity, with
an explicit translation of rates.

######  Lemma 3.6.

Suppose $\varphi$ is a rate of asymptotic regularity for $(x_{n})$ and assume
that conditions $(\operatorname{C}4_{q})$, $(\operatorname{C}5_{q})$ hold.
Then, $\widetilde{\varphi}$ defined by

$\displaystyle\widetilde{\varphi}(k)=\max\left\\{N_{\Lambda},\varphi(2\Lambda(k+1)-1),\eta(4M\Lambda(k+1)-1)\right\\}$

is a rate of $(T_{n})$-asymptotic regularity for $(x_{n})$.

###### Proof.

Let $k\in\mathbb{N}$ and $n\geq\widetilde{\varphi}(k)$. We need to show that
$d(x_{n},T_{n}x_{n})\leq\frac{1}{k+1}$.

As $n\geq N_{\Lambda}$, Condition $(\operatorname{C}5_{q})$ shows that
$\lambda_{n}>0$ and that

$\displaystyle\frac{1}{\lambda_{n}}\leq\Lambda.$ (11)

Since $n\geq\varphi(2\Lambda(k+1)-1)$, the fact that $\varphi$ is a rate of
asymptotic regularity yields

$\displaystyle d(x_{n},x_{n+1})\leq\frac{1}{2\Lambda(k+1)}.$ (12)

Finally, because $n\geq\eta(4M\Lambda(k+1)-1)$ and $\eta$ is a rate of
convergence for $\lim\limits_{n\to\infty}(1-\beta_{n})=0$, we get

$\displaystyle 1-\beta_{n}\leq\frac{1}{4M\Lambda(k+1)}.$ (13)

From Lemma 3.2.(iii), we know that

$\displaystyle
d(x_{n},T_{n}x_{n})\leq\frac{1}{\lambda_{n}}d(x_{n},x_{n+1})+\frac{1}{\lambda_{n}}2M(1-\beta_{n}),$

which, together with (11), (12) and (13) yields

$\displaystyle d(x_{n},T_{n}x_{n})\leq\Lambda\frac{1}{2\Lambda(k+1)}+\Lambda
2M\frac{1}{4M\Lambda(k+1)}=\frac{1}{k+1}$

thus proving the claim. ∎

######  Theorem 3.7.

Suppose conditions $(\operatorname{C}1_{q})$, $(\operatorname{C}2_{q})$,
$(\operatorname{C}3_{q})$, $(\operatorname{C}4_{q})$,
$(\operatorname{C}5_{q})$ and $(\operatorname{C}6_{q})$ hold. Let ${{\Sigma}}$
be defined as in Theorem 3.5. Then $(x_{n})$ is $(T_{n})$-asymptotically
regular with rate

$\displaystyle\widetilde{{{\Sigma}}}(k)=\max\left\\{N_{\Lambda},{{\Sigma}}(2\Lambda(k+1)-1),\eta(4M\Lambda(k+1)-1)\right\\}.$
(14)

###### Proof.

Apply Lemma 3.6 together with Theorem 3.5. ∎

Other than the parameters $(\lambda_{n})$, $(\beta_{n})$ of the iteration, the
rates of ($(T_{n})$-)asymptotic regularity we obtained depend weakly on the
space $X$ and on the mappings $(T_{n})$, only via $M$ and $\chi_{T}$. The
rates are less uniform compared to the rates obtained in the single mapping
case in [9], where only $M$ is present. Indeed, if $(T_{n})$ is constant, then
$\chi_{T}$ can simply be taken as $k\mapsto 0$. However, Proposition 3.4 shows
that for a large class of mappings, the dependence on $\chi_{T}$ can be
reduced to one only on the real parameters $(\gamma_{n})$.

In the following example we compute explicit rates for a concrete choice of
$(\beta_{n})$, $(\lambda_{n})$ and $(\gamma_{n})$. The rates obtained for this
example are the same as those obtained for the single mapping case in [9,
Corollary 4.3], which demonstrates how under the hypotheses of Proposition
3.4, the additional dependence on the familiy $(T_{n})$ is eliminated.

######  Example 3.8.

Let $\lambda_{n}=\lambda\in(0,1)$, $\beta_{n}=1-\frac{1}{n+1}$ and
$\gamma_{n}=1+\frac{1}{n+1}$ and consider the iteration $(x_{n})$ given by (4)
with these parameters and let $(T_{n})$ be a family of nonexpansive mappings
satisfying $\eqref{eq:jP2-consequence}$ with respect to $(\gamma_{n})$. Then

  1. (i)

$(x_{n})$ is asymptotically regular with rate

$\displaystyle k\mapsto 144M^{2}(k+1)^{2}-6M(k+1);$

  2. (ii)

$(x_{n})$ is $(T_{n})$-asymptotically regular with rate

$\displaystyle k\mapsto
576M^{2}\left\lceil\frac{1}{\lambda}\right\rceil^{2}(k+1)^{2}-12M\left\lceil\frac{1}{\lambda}\right\rceil(k+1).$

###### Proof.

  1. (i)

We will apply Theorem 3.5. Let us first show that its assumptions are
fulfilled. Because

$\displaystyle\prod_{i=0}^{n}\beta_{n+1}=\frac{1}{n+2},\quad\sum_{i=0}^{n}\left|\beta_{i+1}-\beta_{i}\right|=1-\frac{1}{n+2}\
\text{and}\ \sum_{i=0}^{n}\left|\lambda_{i+1}-\lambda_{i}\right|=0,$

we get that $(\operatorname{C}1_{q})$, $(\operatorname{C}2_{q})$ and
$(\operatorname{C}3_{q})$ are satified, respectively, with

$\displaystyle\sigma(k)=k,\quad\chi_{\beta}(k)=k,\quad\chi_{\lambda}(k)=0.$

$(\operatorname{C}4_{q})$ holds with

$\displaystyle\eta(k)=k.$

$(\operatorname{C}5_{q})$ is satified with,

$\displaystyle
N_{\Lambda}=0,\quad\Lambda=\left\lceil\frac{1}{\lambda}\right\rceil.$

Furthermore, as

$\displaystyle\sum_{i=0}^{n}\left|\gamma_{i+1}-\gamma_{i}\right|=1-\frac{1}{n+2},$

$(\gamma_{n})$ fulfills $(\operatorname{C}7_{q})$ and
$(\operatorname{C}8_{q})$ with

$\displaystyle\Gamma=1,\quad
N_{\Gamma}=0\quad\text{and}\quad{\chi_{\gamma}}(k)=k.$

Thus, by Proposition 3.4, it follows that $(T_{n})$ satisfies
$(\operatorname{C}6_{q})$ with

$\displaystyle\chi_{T}(k)=\max\left\\{N_{\Gamma},2M\Gamma(k+1)-1\right\\}=2M(k+1)-1$

It follows that $\chi$ defined by (10) is equal in this case to

$\displaystyle\chi(k)$
$\displaystyle=\max\left\\{\chi_{T}(2(k+1)-1),\chi_{\lambda}(8M(k+1)-1),\chi_{\beta}(8M(k+1)-1)\right\\}$
$\displaystyle=\max\left\\{4M((k+1))-1,0,8M(k+1)-1\right\\}$
$\displaystyle=8M(k+1)-1$

Finally, $\psi_{0}$ can be taken as $\psi_{0}(k)=\chi(3k+2)=24M(k+1)-1$. Thus,

$\displaystyle{{\Sigma}}(k)$
$\displaystyle=\max\left\\{\sigma(6M(k+1)\psi_{0}(k)-1),\chi(3k+2)+1\right\\}+1$
$\displaystyle=144M^{2}(k+1)^{2}-6M(k+1)$

  2. (ii)

Apply Theorem 3.7 with the rate ${{\Sigma}}$ from (i), we get that

$\displaystyle\widetilde{{{\Sigma}}}(k)$
$\displaystyle=\max\left\\{N_{\Lambda},{{\Sigma}}(2\Lambda(k+1)-1),\eta(4M\Lambda(k+1)-1)\right\\}$
$\displaystyle=576M^{2}\left\lceil\frac{1}{\lambda}\right\rceil^{2}(k+1)^{2}-12M\left\lceil\frac{1}{\lambda}\right\rceil(k+1)$

∎

###  3.3 Linear rates of ($(T_{n})$-)asymptotic regularity

In this section, we compute linear rates of asymptotic regularity for
iteration (1), by applying a lemma on real numbers introduced by Sabach and
Shtern [22], that was originally used there to obtain the linear asymptotic
regularity of a viscosity-type Halpern iteration, and was recently employed to
the same end for a variety of iterations [8, 19, 10].

The following is a particular case of [22, Lemma 3], as reformulated in [19].

######  Lemma 3.9.

Let $L>0$, and define, for all $n\in\mathbb{N}$, $a_{n}=\frac{2}{n+2}$.
Suppose $(s_{n})$ is a sequence of nonnegative reals such that $s_{0}\leq L$
and that

$\displaystyle s_{n+1}\leq(1-a_{n+1})s_{n}+(a_{n}-a_{n+1})L$ (15)

for all $n\in\mathbb{N}$. Then,

$\displaystyle s_{n}\leq\frac{2L}{n+2}$

for all $n\in\mathbb{N}$.

######  Theorem 3.10.

Let $\beta_{n}=1-\frac{2}{n+2}$, $\lambda_{n}=\lambda\in(0,1)$ and
$\gamma_{n}=\frac{n+3}{n+2}$ and suppose the family $(T_{n})$ satisfies (9)
with respect to $(\gamma_{n})$. Then, the iteration (1) with parameters
$(\beta_{n})$ and $(\lambda_{n})$ satisfies, for all $n,m\in\mathbb{N}$,

$\displaystyle d(x_{n},x_{n+1})$ $\displaystyle\leq\frac{6M}{n+2};$
$\displaystyle d(x_{n},T_{n}x_{n})$
$\displaystyle\leq\frac{10M}{\lambda(n+2)};$ $\displaystyle
d(x_{n},T_{m}x_{n})$ $\displaystyle\leq\frac{20M}{\lambda(n+2)}.$

Thus, the mappings $k\mapsto 6M(k+1)-2$ , $k\mapsto
10M\left\lceil\frac{1}{\lambda}\right\rceil(k+1)-2$ and $k\mapsto
20M\left\lceil\frac{1}{\lambda}\right\rceil(k+1)-2$ are rates of asymptotic,
$(T_{n})$-asymptotic and $T_{m}$-asymptotic regularity for $(x_{n})$,
respectively.

###### Proof.

For the first inequality, we will apply Lemma 3.9 with

$\displaystyle s_{n}$ $\displaystyle=d(x_{n},x_{n+1}),$ $\displaystyle a_{n}$
$\displaystyle=1-\beta_{n},$ $\displaystyle L$ $\displaystyle=3M.$

Note first that

$\displaystyle\left|\gamma_{n+1}-\gamma_{n}\right|$
$\displaystyle=\frac{1}{(n+2)(n+3)},$
$\displaystyle\frac{\left|\gamma_{n+1}-\gamma_{n}\right|}{\gamma_{n}}$
$\displaystyle=\frac{n+2}{n+3}\cdot\frac{1}{(n+2)(n+3)}=\frac{1}{(n+3)^{2}}$
and that $\displaystyle\beta_{n+1}-\beta_{n}$
$\displaystyle=\frac{2}{(n+2)(n+3)}.$

We now show that the main condition (15) is satisfied. By Lemma 3.2 and (9),
for all $n\in\mathbb{N}$,

$\displaystyle s_{n+1}$
$\displaystyle\leq\beta_{n+1}s_{n}+2M(\beta_{n+1}-\beta_{n})+d(T_{n+1}u_{n},T_{n}u_{n})$
$\displaystyle\leq\beta_{n+1}s_{n}+2M(\beta_{n+1}-\beta_{n})+\frac{\left|\gamma_{n+1}-\gamma_{n}\right|}{\gamma_{n}}d(T_{n}u_{n},u_{n})$
$\displaystyle\leq\beta_{n+1}s_{n}+2M(\beta_{n+1}-\beta_{n})+2M\frac{\left|\gamma_{n+1}-\gamma_{n}\right|}{\gamma_{n}}$
$\displaystyle=\beta_{n+1}s_{n}+(\beta_{n+1}-\beta_{n})\left(2M+2M\frac{\left|\gamma_{n+1}-\gamma_{n}\right|}{\gamma_{n}(\beta_{n+1}-\beta_{n})}\right)$
$\displaystyle=\beta_{n+1}s_{n}+(\beta_{n+1}-\beta_{n})\left(2M+\frac{2M}{(n+3)^{2}}\cdot\frac{(n+2)(n+3)}{2}\right)$
$\displaystyle=\beta_{n+1}s_{n}+(\beta_{n+1}-\beta_{n})\left(2M+M\frac{n+2}{n+3}\right)$
$\displaystyle\leq\beta_{n+1}s_{n}+(\beta_{n+1}-\beta_{n})L$

thus proving the first claim. For the second claim, using the previous and
Lemma 3.3.(iii), we have

$\displaystyle d(x_{n},T_{n}x_{n})$
$\displaystyle\leq\frac{1}{\lambda}d(x_{n},x_{n+1})+\frac{4M}{\lambda(n+2)}$
$\displaystyle\leq\frac{6M}{\lambda(n+2)}+\frac{4M}{\lambda(n+2)}=\frac{10M}{\lambda(n+2)}.$

Finally,

$\displaystyle d(x_{n},T_{m}x_{n})$ $\displaystyle\leq
d(x_{n},T_{n}x_{n})+\frac{\left|\gamma_{n}-\gamma_{m}\right|}{\gamma_{m}}d(x_{n},T_{n}x_{n})$
$\displaystyle=d(x_{n},T_{n}x_{n})+\frac{\left|n-m\right|}{(m+2)(n+3)}d(x_{n},T_{n}x_{n})$
$\displaystyle\leq 2d(x_{n},T_{n}x_{n})$

and the claim follows from the previous result.

∎

###  3.4 Relation to the modified Halpern iteration

In this section we show that the relation between the modified Halpern,
originally introduced in [12], and the Tikhonov-Mann iterations studied in [8]
for the single mapping case extends to families of mappings: the
($(T_{n})$-)asymptotic regularity of one iteration implies that of the other,
with an explicit translation of rates.

The modified Halpern iteration as defined for $W$-hyperbolic spaces in [8] can
naturally be extended to families of mappings as follows. Define, for all
$n\in\mathbb{N}$,

$\displaystyle y_{n+1}$
$\displaystyle=(1-\beta_{n+1})u+\beta_{n+1}v_{n},\quad\text{where}$
$\displaystyle v_{n}$
$\displaystyle=(1-\lambda_{n})y_{n}+\lambda_{n}T_{n}y_{n}.$

######  Proposition 3.11.

Assume that $y_{0}=(1-\beta_{0})u+\beta_{0}x_{0}$. Then, for all
$n\in\mathbb{N}$,

$\displaystyle u_{n}=y_{n}\quad\text{and}\quad x_{n+1}=v_{n}.$

###### Proof.

The proof goes by induction on $n$ just like the proof of [8, Proposition
3.2], replacing $T$ with $T_{n}$. ∎

######  Proposition 3.12.

Assume that $(\operatorname{C}4_{q})$ holds, that
$y_{0}=(1-\beta_{0})u+\beta_{0}x_{0}$, define

$\displaystyle\alpha(k)=\eta(2M(k+1)-1),$

and suppose $\Sigma$ is a rate of ($(T_{n})$)-asymptotic regularity for one of
the sequences $(x_{n})$ or $(y_{n})$. Then, the other sequence is ($(T_{n})$-)
asymptotically regular with rate

$\displaystyle\Sigma^{\prime}(k)=\max\left\\{\alpha(3k+2),\Sigma(3k+2)\right\\}$

###### Proof.

Noting that

$\displaystyle
d(x_{n},u_{n})\stackrel{{\scriptstyle\text{Proposition~{}\ref{prop:W-derived}.\ref{prop:W-derived:common-
left-
endpoint}}}}{{=}}(1-\beta_{n})d(x_{n},u)\stackrel{{\scriptstyle\text{Lemma~{}\ref{lem:basic-
bounds}.\ref{lem:basic-bounds:x-u}}}}{{\leq}}(1-\beta_{n})2M,$

the fact that $\lim\limits_{n\to\infty}d(x_{n},u_{n})=0$ with rate of
convergence $\alpha$ is proved as in [8, Lemma 4.1]. Using this, the fact that
$\Sigma^{\prime}$ is a rate of ($(T_{n})$-)asymptotic regularity is proved the
same as in [8, Proposition 4.2], replacing $T$ with $T_{n}$. ∎

##  4 Rates of asymptotic regularity for the Tikhonov-forward-backward
algorithm with variable step-size

Let us first recall some notions from convex optimization and monotone
operator theory. Let $H$ be a Hilbert space. For a set-valued operator
$A:H\rightrightarrows H$, its graph is $\operatorname{gra}(A)=\left\\{(x,u)\in
H\mid u\in Ax\right\\}$ and its set of zeroes is
$\operatorname{zer}(A)=\left\\{x\in H\mid 0\in Ax\right\\}$. Given
$A:H\rightrightarrows H$, the inverse of $A$ is the operator
$A^{-1}:H\rightrightarrows H$, $A^{-1}u=\left\\{x\mid u\in Ax\right\\}$ and
the scaling of $A$ by $\gamma\in\mathbb{R}$ is the operator $\gamma
A:H\rightrightarrows H$, $(\gamma A)x=\left\\{\gamma u\mid u\in Ax\right\\}$.
Given two set-valued operators $A,B:H\rightrightarrows H$, their sum,
$A+B:H\rightrightarrows H$, is defined by $(A+B)x=\left\\{u+v\mid u\in Ax,v\in
Bx\right\\}$ and their composition, $AB:H\rightrightarrows H$, by
$(AB)x=\left\\{v\in H\mid\text{ there exists }u\in Ax\text{ such that }v\in
Bu\right\\}$.

We say that $A:H\rightrightarrows H$ is _monotone_ if, for all
$(x,u),(y,v)\in\operatorname{gra}(A)$, we have that $\left\langle
x-y,u-v\right\rangle\geq 0$. $A$ is called _maximally monotone_ if there
exists no other monotone operator $B:H\rightrightarrows H$ such that
$\operatorname{gra}(A)\subsetneq\operatorname{gra}(B)$. For a maximally
monotone operator $A$, its _resolvent_ of order $\gamma>0$ is defined by

$\displaystyle\operatorname{J}_{{\gamma}{A}}=(\operatorname{Id}+\gamma
A)^{-1}.$

and it is known to be a single-valued, nonexpansive mapping, where
$\operatorname{Id}:H\to H$ is the identity mapping. A single-valued operator
$B:H\to H$ is said to be $\beta$-cocoercive for some $\beta>0$ if, for all
$x,y\in H$, $\left\langle x-y,Bx-By\right\rangle\geq\beta\left\lVert Tx-
Ty\right\rVert^{2}$.

The _forward-backward_ algorithm is one of the procedures widely employed for
finding a point in $\operatorname{zer}(A+B)$ where $A$ is maximally monotone
and $B$ is cocoercive. We refer to [2] for a more detailed account of this
algorithm and the theory of monotone operators in general.

Based on their strongly convergent Krasnoselskii-Mann iteration for families
of mappings, the authors of [4] define a version of the forward-backward
algorithm with variable step-size and prove its strong convergence. In this
section, we give a generalized verion of this iteration based on (4) and
compute rates of ($(T_{n})$-)asymptotic regularity for it.

Let in the following $A:H\rightrightarrows H$ be maximally monotone and
$B:H\to H$ be $\beta$-cocoercive for some $\beta>0$. The Tikhonov-forward-
backward algorithm with variable step size associated with $A$ and $B$ is
defined by

$\displaystyle x_{n+1}$
$\displaystyle=(1-\lambda_{n})u_{n}+\lambda_{n}\operatorname{J}_{{\gamma_{n}}{A}}(u_{n}-\gamma_{n}Bu_{n}),\quad\text{where}$
$\displaystyle u_{n}$ $\displaystyle=(1-\beta_{n})u+\beta_{n}x_{n},$

where $(\beta_{n})\subset(0,1]$, $(\gamma_{n})\subset(0,2\beta)$ and
$\lambda_{n}\subset(0,\frac{1}{\alpha_{n}}]$.

######  Corollary 4.1.

Assume $(\operatorname{C}1_{q})$, $(\operatorname{C}2_{q})$,
$(\operatorname{C}3_{q})$, $(\operatorname{C}7_{q})$,
$(\operatorname{C}8_{q})$ are satisfied. Let
$\chi_{T}:\mathbb{N}\to\mathbb{N}$ be defined by:

$\displaystyle\chi_{T}(k)=\max\left\\{N_{\Gamma},{\chi_{\gamma}}(2M\Gamma(k+1)-1)\right\\}.$
(16)

Then $(x_{n})$ is asymptotically regular with rate ${{\Sigma}}$ as defined as
in Theorem 3.5.

###### Proof.

For any $n\in\mathbb{N}$, define
$T_{n}=\operatorname{J}_{{\gamma_{n}}{A}}(\operatorname{Id}-\gamma_{n}B)$, so
that $x_{n}$ can be written as

$\displaystyle x_{n+1}=(1-\lambda_{n})u_{n}+\lambda_{n}T_{n}u_{n}.$

It is known [2, Proposition 26.1.(v)] that $T_{n}$ is
$\frac{2\beta}{4\beta-\gamma_{n}}$-averaged, and hence nonexpansive. Lemma 3.2
of [4] then shows that $(T_{n})$ satisfies (9) with respect to $(\gamma_{n})$,
and thus, by Proposition 3.4, $(\operatorname{C}6_{q})$ holds with $\chi_{T}$.
All the hypotheses to apply Theorem 3.5 are thus satisfied, and hence the
result follows. ∎

##  5 Acknowledgements

The author is grateful to Laurenţiu Leuştean for initially suggesting the
investigation of the topic herein and for the later comments that improved the
paper.

## References

  * [1] S. Alexander, V. Kapovitch, and A. Petrunin.  An Invitation to Alexandrov Geometry. CAT(0) Spaces.  Springer, 2019.
  * [2] H.H. Bauschke and P.L. Combettes.  Convex Analysis and Monotone Operator Theory in Hilbert Spaces.  Springer, 2010.
  * [3] R.I. Boţ, E.R. Csetnek, and D. Meier.  Inducing strong convergence into the asymptotic behaviour of proximal splitting algorithms in Hilbert spaces.  Optimization Methods and Software, 34:489–514, 2019.
  * [4] R.I. Boţ and D. Meier.  A strongly convergent Krasnosel’skiǐ–Mann-type algorithm for finding a common fixed point of a countably infinite family of nonexpansive operators in Hilbert spaces.  Journal of Computational and Applied Mathematics, 395:113589, 2021\.
  * [5] J. Borwein, S. Reich, and I. Shafrir.  Krasnoselski-Mann iterations in normed spaces.  Canadian Mathematical Bulletin, 35:21–28, 1992.
  * [6] M. Bridson and A. Haefliger.  Metric Spaces of Non-Positive Curvature.  Springer, 1999.
  * [7] F.E. Browder and W.V. Petryshyn.  Construction of fixed points of nonlinear mappings in Hilbert spaces.  Journal of Mathematical Analysis and Applications, 20:197–228, 1967\.
  * [8] H. Cheval, U. Kohlenbach, and L. Leuştean.  On modified Halpern and Tikhonov-Mann iterations.  Journal of Optimization Theory and Applications, 197:233–251, 2023\.
  * [9] H. Cheval and L. Leuştean.  Quadratic rates of asymptotic regularity for the Tikhonov-Mann iteration.  Optimization Methods and Software, 37(6):2225–2240, 2022.
  * [10] H. Cheval and L. Leuştean.  Linear rates of asymptotic regularity for Halpern-type iterations.  arXiv:2303.05406 [math.OC], 2023.
  * [11] B. Dinis and P. Pinto.  Strong convergence for the alternating Halpern-Mann iteration in CAT(0) spaces.  arXiv:2112.14525 [math.FA], to appear in SIAM Journal of Optimization, 2021.
  * [12] T.H. Kim and H.K. Xu.  Strong convergence of modified Mann iterations.  Nonlinear Analysis, 61:51–60, 2005.
  * [13] U. Kohlenbach.  Some logical metatheorems with applications in functional analysis.  Transactions of the American Mathematical Society, 357:89–128, 2005\.
  * [14] U. Kohlenbach.  Applied Proof Theory: Proof Interpretations and Their Use in Mathematics.  Springer, 2008.
  * [15] U. Kohlenbach.  On quantitative versions of theorems due to F.E. Browder and R. Wittmann.  Advances in Mathematics, 226:2764–2795, 2011.
  * [16] U. Kohlenbach and L. Leuştean.  Effective metastability of Halpern iterates in CAT(0) spaces.  Advances in Mathematics, 231:2526–2556, 2012.
  * [17] U. Kohlenbach.  Proof-theoretic Methods in Nonlinear Analysis.  In B. Sirakov, P. Ney de Souza, and M. Viana, editors, Proceedings of ICM 2018, Vol. 2, pages 61–82. World Scientific, 2019.
  * [18] L. Leuştean, A. Nicolae, and A. Sipoş.  An abstract proximal point algorithm.  Journal of Global Optimization, 72:553–577, 2018.
  * [19] L. Leuştean and P. Pinto.  Rates of asymptotic regularity for the alternating Halpern-Mann iteration.  Optimization Letters, published online: https://doi.org/10.1007/s11590-023-02002-y, 2023.
  * [20] L. Leuştean and P. Pinto.  Quantitative results on a Halpern-type proximal point algorithm.  Computational Optimization and Applications, 79:101–125, 2021.
  * [21] A. Papadopoulos.  Metric Spaces, Convexity and Nonpositive Curvature.  European Mathematical Society, 2005.
  * [22] S. Sabach and S. Shtern.  A first order method for solving convex bilevel optimization problems.  SIAM Journal on Optimization, 27(2):640–660, 2017.
  * [23] W. Takahashi.  A convexity in metric space and nonexpansive mappings, I.  Kodai Mathematical Seminar Reports, 22:142–149, 1970.
  * [24] H.-K. Xu.  Iterative algorithms for nonlinear operators.  Journal of the London Mathematical Society, 66:240–256, 2002.
  * [25] Y. Yao, H. Zhou, and Y.C. Liou.  Strong convergence of a modified Krasnoselski-Mann iterative algorithm for non-expansive mappings.  Journal of Applied Mathematics and Computing, (29):383–389, 2009\.