# Finding Minimum Norm Fixed Point of Nonexpansive Mappings and Applications

Authors: Xue Yang; Yeong-Cheng Liou; Yonghong Yao
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

We construct two new methods for finding the minimum norm fixed point of nonexpansive mappings in Hilbert spaces. Some applications are also included.


---

## Body

## 1. Introduction

LetC be a nonempty closed convex subset of a real Hilbert space H. Recall that a mapping T:C→C is nonexpansive if (1.1)‖Tx-Ty‖≤‖x-y‖,∀x,y∈C.Iterative algorithms for finding fixed point of nonexpansive mappings are very interesting topic due to the fact that many nonlinear problems can be reformulated as fixed point equations of nonexpansive mappings. Related works can be found in [1–32].On the other hand, we notice that it is quite often to seek a particular solution of a given nonlinear problem, in particular, the minimum-norm solution. In an abstract way, we may formulate such problems as finding a pointx† with the property(1.2)x†∈C,‖x†‖=min⁡x∈C‖x‖,
where C is a nonempty closed convex subset of a real Hilbert space H. In other words, x† is the (nearest point or metric) projection of the origin onto C,(1.3)x†=PC(0),
where PC is the metric (or nearest point) projection from H onto C.A typical example is the least-squares solution to the constrained linear inverse problem(1.4)Ax=b,x∈C,
where A is a bounded linear operator from H to another real Hilbert space H1 and b is a given point in H1. The least-squares solution to (1.4) is the least-norm minimizer of the minimization problem(1.5)min⁡x∈C‖Ax-b‖2.LetSb denote the (closed convex) solution set of (1.4) (or equivalently (1.5)). It is known that Sb is nonempty if and only if PA(C)¯(b)∈A(C). In this case, Sb has a unique element with minimum norm (equivalently, (1.4) has a unique least-squares solution); that is, there exists a unique point x†∈Sb satisfying(1.6)‖x†‖=min⁡{‖x‖:x∈Sb}.
The so-called C-constrained pseudoinverse of A is then defined as the operator AC† with domain and values given by (1.7)D(AC†)={b∈H:PA(C)¯(b)∈A(C)};AC†(b)=x†,b∈D(AC†),wherex†∈Sb is the unique solution to (1.6).Note that the optimality condition for the minimization (1.5) is the variational inequality (VI)(1.8)x̂∈C,〈A*(Ax̂-b),x-x̂〉≥0,x∈C,
where A* is the adjoint of A.Ifb∈D(AC†), then (1.5) is consistent and its solution set Sb coincides with the solution set of VI (1.8). On the other hand, VI (1.8) can be rewritten as(1.9)x̂∈C,〈(x̂-λA*(Ax̂)-b)-x̂,x-x̂〉≤0,x∈C,
where λ>0 is any positive scalar. In the terminology of projections, (1.10) is equivalent to the fixed point equation(1.10)x̂=PC(x̂-λA*(Ax̂-b)).
It is not hard to find that for 0<λ<2/∥A∥2, the mapping x↦PC(x-λA*(Ax-b)) is nonexpansive. Therefore, finding the least-squares solution of the constrained linear inverse problem (1.6) is equivalent to finding the minimum-norm fixed point of the nonexpansive mapping x↦PC(x-λA*(Ax-b)).Motivated by the above least-squares solution to constrained linear inverse problems, we will study the general case of finding the minimum-norm fixed point of a nonexpansive mappingT:C→C:(1.11)x†∈Fix⁡(T),∥x†∥=min⁡{∥x∥:x∈Fix⁡(T)},
where Fix(T)={x∈C:Tx=x} denotes the set of fixed points of T (throughout we always assume that Fix(T)≠∅).We next briefly review two historic approaches which relate to the minimum-norm fixed point problem (1.11).Browder [1] introduced an implicit scheme as follows. Fix a u∈C, and for each t∈(0,1), let xt be the unique fixed point in C of the contraction Tt which maps C into C:(1.12)Ttx=tu+(1-t)Tx,x∈C.
Browder proved that(1.13)s-lim⁡t↓0xt=PFix⁡(T)u.
That is, the strong limit of {xt} as t→0+ is the fixed point of T which is nearest from Fix(T) to u.Halpern [4], on the other hand, introduced an explicit scheme. Again fix a u∈C. Then with a sequence {tn} in (0,1) and an arbitrary initial guess x0∈C, we can define a sequence {xn} through the recursive formula(1.14)xn+1=tnu+(1-tn)Txn,n≥0.
It is now known that this sequence {xn} converges in norm to the same limit PFix(T)u as Browder's implicit scheme (1.12) if the sequence {tn} satisfies, assumptions (A1), (A2), and (A3) as follows: (A1)
limn→∞tn=0,(A2)
∑n=1∞tn=∞,(A3)
either∑n=1∞|tn+1-tn|=∞ or limn→∞(tn/tn+1)=1.Some more progress on the investigation of the implicit and explicit schemes (1.12) and (1.14) can be found in [33–42]. We notice that the above two methods do find the minimum-norm fixed point x† of T if 0∈C. However, if 0∉C, then neither Browder's nor Halpern's method works to find the minimum-norm element x†. The reason is simple: if 0∉C, we cannot take u=0 either in (1.12) or (1.14) since the contraction x↦(1-t)Tx is no longer a self-mapping of C (hence may fail to have a fixed point), or (1-tn)Txn may not belong to C, and consequently, xn+1 may be undefined. In order to overcome the difficulties caused by possible exclusion of the origin from C, we introduce the following two remedies.For Browder's method, we consider the contractionx↦(1-β)PC[(1-t)x]+βTx for some β∈(0,1). Since this contraction clearly maps C into C, it has a unique fixed point which is still denoted by xt, that is, xt=(1-β)PC[(1-t)xt]+βTxt. For Halpern's method, we consider the following iterative algorithm xn+1=(1-β)PC[(1-tn)xn]+βTxn,n≥0. It is easily seen that the net {xt} and the sequence {xn} are well defined (i.e., xt∈C and xn∈C).The purpose of this paper is to prove that the above both implicit and explicit methods converge strongly to the minimum-norm fixed pointx† of the nonexpansive mapping T. Some applications are also included.


## 2. Preliminaries

LetH be a real Hilbert space with inner product 〈·,·〉 and norm ∥·∥, respectively. Let C be a nonempty closed convex subset of H. Recall that the nearest point (or metric) projection from H onto C is defined as follows: for each point x∈H, PCx is the unique point in C with the property (2.1)‖x-PCx‖≤‖x-y‖,y∈C.Note thatPC is characterized by the inequality (2.2)PCx∈C,〈x-PCx,y-PCx〉≤0,y∈C.Consequently,PC is nonexpansive.Below is the so-called demiclosedness principle for nonexpansive mappings.Lemma 2.1 (cf. [7]).
LetC be a nonempty closed convex subset of a real Hilbert space H, and let T:C→C be a nonexpansive mapping with fixed points. If (xn) is a sequence in C such that xn→x* weakly and xn-Txn→y strongly, then (I-T)x*=y.Finally we state the following elementary result on convergence of real sequences.Lemma 2.2 (see [19]).
Let{an}n=0∞ be a sequence of nonnegative real numbers satisfying
(2.3)an+1≤(1-γn)an+γnσn,n≥0,where {γn}n=0∞⊂(0,1) and {σn}n=0∞ are satisfied that  (i)
∑n=0∞γn=∞;(ii)
eitherlimsupn→∞σn≤0 or ∑n=0∞|γnσn|<∞. Then {an}n=0∞ converges to 0.We use the following notation:(i)
Fix(T) stands for the set of fixed points of T;(ii)
xn⇀x stands for the weak convergence of (xn) to x;(iii)
xn→x stands for the strong convergence of (xn) to x.


## 3. Main Results

The aim of this section is to introduce some methods for finding the minimum-norm fixed point of a nonexpansive mappingT. First, we prove the following theorem by using an implicit method.Theorem 3.1.
LetC be a nonempty closed convex subset of a real Hilbert space H and T:C→C a nonexpansive mapping with Fix(T)≠∅. For β∈(0,1) and each t∈(0,1), let xt be defined as the unique solution of fixed point equation
(3.1)xt=βTxt+(1-β)PC[(1-t)xt],t∈(0,1).
Then the net {xt} converges in norm, as t→0+, to the minimum-norm fixed point of T.Proof.
First observe that, for eacht∈(0,1), xt is well defined. Indeed, we define a mapping St:C→C by
(3.2)Stx=βTx+(1-β)PC[(1-t)x],x∈C.
For x,y∈C, we have
(3.3)‖Stx-Sty‖=‖β(Tx-Ty)+(1-β)(PC[(1-t)x]-PC[(1-t)y])‖≤β‖Tx-Ty‖+(1-β)‖PC[(1-t)x]-PC[(1-t)y]‖≤[1-(1-β)t]‖x-y‖,
which implies that St is a self-contraction of C. Hence St has a unique fixed point xt∈C which is the unique solution of the fixed point equation (3.1).
Next we prove that{xt} is bounded. Take u∈Fix(T). From (3.1), we have
(3.4)‖xt-u‖=‖βTxt+(1-β)PC[(1-t)xt]-u‖≤β‖Txt-u‖+(1-β)‖PC[(1-t)xt]-u‖≤β‖xt-u‖+(1-β)‖(1-t)xt-u‖≤β‖xt-u‖+(1-β)[(1-t)‖xt-u‖+t‖u‖],
that is,
(3.5)‖xt-u‖≤‖u‖.
Hence, {xt} is bounded and so is {Txt}.
From (3.1), we have
(3.6)‖xt-Txt‖≤(1-β)‖PC[(1-t)xt]-PC[Txt]‖≤(1-β)‖xt-Txt-txt‖≤(1-β)‖xt-Txt‖+(1-β)t‖xt‖,that is,
(3.7)‖xt-Txt‖≤1-ββt‖xt‖⟶0ast⟶0+.
Next we show that {xt} is relatively norm-compact as t→0+. Let {tn}⊂(0,1) be a sequence such that tn→0+ as n→∞. Put xn:=xtn. From (3.7), we have
(3.8)‖xn-Txn‖⟶0.
Again from (3.1), we get
(3.9)‖xt-u‖2≤β‖Txt-u‖2+(1-β)‖PC[(1-t)xt]-u‖2≤β‖xt-u‖2+(1-β)‖xt-u-txt‖2=β‖xt-u‖2+(1-β)[‖xt-u‖2-2t〈xt-u,xt-u〉-2t〈u,xt-u〉+t2‖xt‖2].It turns out that
(3.10)‖xt-u‖2≤〈u,u-xt〉+tM,
where M>0 is some constant such that sup{(1/2)∥xt∥2:t∈(0,1)}≤M. In particular, we get from (3.10)
(3.11)‖xn-u‖2≤〈u,u-xn〉+tnM,u∈Fix⁡(T).
Since {xn} is bounded, without loss of generality, we may assume that {xn} converges weakly to a point x*∈C. Noticing (3.8) we can use Lemma 2.1 to get x*∈Fix(T). Therefore we can substitute x* for u in (3.11) to get
(3.12)‖xn-x*‖2≤〈x*,x*-xn〉+tnM.
However, xn⇀x*. This together with (3.12) guarantees that xn→x*. The net {xt} is therefore relatively compact, as t→0+, in the norm topology.
Now we return to (3.11) and take the limit as n→∞ to get
(3.13)‖x*-u‖2≤〈u,u-x*〉,u∈Fix⁡(T).This is equivalent to
(3.14)0≤〈x*,u-x*〉,u∈Fix⁡(T).Therefore, x*=PFix(T)0. This is sufficient to conclude that the entire net {xt} converges in norm to x* and x* is the minimum-norm fixed point of T. This completes the proof.Next, we introduce an explicit algorithm for finding the minimum norm fixed point of nonexpansive mappings.Theorem 3.2.
LetC be a nonempty closed convex subset of a real Hilbert space H, and let T:C→C be a nonexpansive mapping with Fix(T)≠∅. For given x0∈C, define a sequence {xn} iteratively by
(3.15)xn+1=βTxn+(1-β)PC[(1-αn)xn],n≥0,
where β∈(0,1) and αn∈(0,1) satisfying the following conditions:  (C1)
limn→∞αn=0 and ∑n=0∞αn=∞;(C2)
limn→∞(αn/αn-1)=1. Then the sequence {xn} converges strongly to the minimum-norm fixed point of T.Proof.
First we prove that the sequence{xn} is bounded. Pick p∈Fix(T). Then, we have
(3.16)‖xn+1-p‖=‖β(Txn-p)+(1-β)(PC[(1-αn)xn]-p)‖≤β‖Txn-p‖+(1-β)‖PC[(1-αn)xn]-p‖≤β‖xn-p‖+(1-β)‖(1-αn)(xn-p)-αnp‖≤[1-(1-β)αn]‖xn-p‖+(1-β)αn‖p‖≤max⁡{‖xn-p‖,‖p‖}.By induction,
(3.17)‖xn+1-p‖≤max⁡{‖x0-p‖,‖p‖}.
Next, we estimate ∥xn+1-xn∥. From (3.15), we have
(3.18)‖xn+1-xn‖=‖β(Txn-Txn-1)+(1-β)(PC[(1-αn)xn]-PC[(1-αn-1)xn-1])‖≤β‖Txn-Txn-1‖+(1-β)‖PC[(1-αn)xn]-PC[(1-αn-1)xn-1]‖≤β‖xn-xn-1‖+(1-β)‖(1-αn)(xn-xn-1)+(αn-1-αn)xn-1‖≤[1-(1-β)αn]‖xn-xn-1‖+(1-β)αn|αn-αn-1|αn‖xn-1‖.This together with Lemma 2.2 implies that
(3.19)lim⁡n→∞‖xn+1-xn‖=0.Note that
(3.20)‖xn-Txn‖≤‖xn-xn+1‖+‖xn+1-Txn‖≤‖xn-xn+1‖+(1-β)‖PC[(1-αn)xn]-PC[Txn]‖≤‖xn-xn+1‖+(1-β)‖xn-Txn‖+(1-β)αn‖xn‖.Thus,
(3.21)‖xn-Txn‖≤1β(‖xn-xn+1‖+(1-β)αn‖xn‖)⟶0.
We next show that
(3.22)limsup⁡n→∞〈x̃,x̃-xn〉≤0,
where x̃=PFix(T)0, the minimum norm fixed point of T. To see this, we can take a subsequence {xnk} of {xn} satisfying the properties
(3.23)limsup⁡n→∞〈x̃,x̃-xn〉=lim⁡k→∞〈x̃,x̃-xnk〉,(3.24)xnk⇀x*ask⟶∞.Now since x*∈Fix(T) (this is a consequence of Lemma 2.2 and (3.21)), we get by combining (3.22) and (3.23)
(3.25)limsup⁡n→∞〈x̃,x̃-xn〉=〈x̃,x̃-x*〉≤0.Finally, we show that xn→x̃. As a matter of fact, we have
(3.26)‖xn+1-x̃‖2≤β‖Txn-x̃‖2+(1-β)‖PC[(1-αn)xn]-x̃‖2≤β‖xn-x̃‖2+(1-β)‖xn-x̃-αnxn‖2=β‖xn-x̃‖2+(1-β)[(1-2αn)‖xn-x̃‖2-2αn〈x̃,xn-x̃〉+αn2‖x̃‖2]=[1-2(1-β)αn]‖xn-x̃‖2+2(1-β)αn(〈x̃,x̃-xn〉+αn‖x̃‖22)=(1-δn)‖xn-x̃‖2+δnθn.
By (C1) and (3.22), it is easily found that limn→∞δn=0 and limsupn→∞θn≤0. We can therefore apply Lemma 2.2 to (3.26) and conclude that xn+1→x̃ as n→∞. This completes the proof.


## 4. Applications

We consider the following minimization problem(4.1)min⁡x∈C⁡φ(x),
where C is a closed convex subset of a real Hilbert space H and φ:C→ℝ is a continuously Fréchet differentiable convex function. Denote by S the solution set of (4.1); that is, (4.2)S={z∈C:φ(z)=min⁡x∈C⁡φ(x)}.AssumeS=∅. It is known that a point z∈C is a solution of (4.1) if and only if the following optimality condition holds:(4.3)z∈C,〈∇φ(z),x-z〉≥0,x∈C.
(Here ∇φ(x) denotes the gradient of φ at x∈C.) It is also known that the optimality condition (4.3) is equivalent to the following fixed point problem, (4.4)z=Tγz,Tγ=PC(I-γ∇φ),whereγ>0 is any positive number. Note that the solution set S of (4.1) coincides with the set of fixed points of Tγ (for any γ>0).If the gradient∇φ is L-Lipschitzian continuous on C, then it is not hard to see that the mapping Tγ is nonexpansive if 0<γ<2/L.Using Theorems3.1 and 3.2, we immediately obtain the following result.Theorem 4.1.
Assumeφ is continuously (Fréchet) differentiable and convex and its gradient ∇φ is L-Lipschitzian. Assume the solution set S of the minimization (4.1) is nonempty. Fix γ such that 0<γ<2/L.
(i)
For eacht∈(0,1), let xt be the unique solution of the fixed point equation
(4.5)xt=βPC[(I-γ∇φ)xt]+(1-β)PC[(1-t)xt].
Then {xt} converges in norm as t→0+ to the minimum-norm solution of the minimization (4.1).(ii)
Define a sequence{xn} via the recursive algorithm
(4.6)xn+1=βPC[(I-γ∇φ)xn]+(1-β)PC[(1-αn)xn],
where the sequence {αn} satisfies conditions (C1)-(C2) in Theorem 3.2. Then {xn} converges in norm to the minimum-norm solution of the minimization (4.1).We next turn to consider a convexly constrained linear inverse problem(4.7)Ax=b,x∈K,
where A is a bounded linear operator with nonclosed range from a real Hilbert space H1 to another real Hilbert space H2 and b∈H2 is given.Problem (4.7) models many applied problems arising from image reconstructions, learning theory, and so on.Due to some reasons (errors, noises, etc.), (4.7) is often illposed and inconsistent; thus regularization and least-squares are taken into consideration; that is, we look for a solution to the minimization problem(4.8)min⁡x∈K12‖Ax-b‖2.
Let Sb denote the solution set of (4.8). It is always closed convex (but possibly empty). It is known that Sb is nonempty if and only if PA(K)¯(b)∈A(K). In this case, Sb has a unique element with minimum norm; that is, there exists a unique point x†∈Sb satisfying(4.9)‖x†‖=min⁡{‖x‖:x∈Sb}.
The K-constrained pseudoinverse of A, AK†, is defined as (4.10)D(AK†)={b∈H2:PA(K)¯(b)∈A(K)},AK†(b)=x†,b∈D(AK†),wherex†∈Sb is the unique solution to (4.9).Set(4.11)φ(x)=12‖Ax-b‖2.Thenφ(x) is quadratic with gradient (4.12)∇φ(x)=A*(Ax-b),x∈H1,whereA* is the adjoint of A. Clearly ∇φ is Lipschitzian with constant L=∥A*A∥=∥A∥2. Therefore, applying Theorem 4.1, we obtain the following result.Theorem 4.2.
Letb∈D(AK†). Fix γ such that 0<γ<2/∥A∥2.
(i)
For eacht∈(0,1), let xt be the unique solution of the fixed point equation
(4.13)xt=βPK[xt-γA*(Axt-b)]+(1-β)PK[(1-t)xt].Then {xt} converges in norm as t→0+ to AK†(b).(ii)
Define a sequence{xn} via the recursive algorithm
(4.14)xn+1=βPK[xn-γA*(Axn-b)]+(1-β)PK[(1-αn)xn],where the sequence {αn} satisfies conditions (C1)-(C2) in Theorem 3.2. Then {xn} converges in norm to AK†(b).



---

*Source: 106450-2011-05-12.xml*