Contraction mapping#Firmly non-expansive mapping

{{Short description|Function reducing distance between all points}} In mathematics, a contraction mapping, or contraction or contractor, on a metric space (M, d) is a function f from M to itself, with the property that there is some real number $0 \leq k < 1$ such that for all x and y in M,

: $d(f(x),f(y)) \leq k\,d(x,y).$

The smallest such value of k is called the Lipschitz constant of f. Contractive maps are sometimes called Lipschitzian maps. If the above condition is instead satisfied for

k ≤ 1, then the mapping is said to be a non-expansive map.

More generally, the idea of a contractive mapping can be defined for maps between metric spaces. Thus, if (M, d) and (N, d') are two metric spaces, then $f:M \rightarrow N$ is a contractive mapping if there is a constant $0 \leq k < 1$ such that

: $d'(f(x),f(y)) \leq k\,d(x,y)$

for all x and y in M.

Every contraction mapping is Lipschitz continuous and hence uniformly continuous (for a Lipschitz continuous function, the constant k is no longer necessarily less than 1).

A contraction mapping has at most one fixed point. Moreover, the Banach fixed-point theorem states that every contraction mapping on a non-empty complete metric space has a unique fixed point, and that for any x in M the iterated function sequence x, f (x), f (f (x)), f (f (f (x))), ... converges to the fixed point. This concept is very useful for iterated function systems where contraction mappings are often used. Banach's fixed-point theorem is also applied in proving the existence of solutions of ordinary differential equations, and is used in one proof of the inverse function theorem.{{cite book |first=Theodore |last=Shifrin |title=Multivariable Mathematics |publisher=Wiley |year=2005 |isbn=978-0-471-52638-4 |pages=244–260 }}

Contraction mappings play an important role in dynamic programming problems.{{cite journal |first=Eric V. |last=Denardo |title=Contraction Mappings in the Theory Underlying Dynamic Programming |journal=SIAM Review |volume=9 |issue=2 |pages=165–177 |year=1967 |doi=10.1137/1009030 |bibcode=1967SIAMR...9..165D }}{{cite book |first1=Nancy L. |last1=Stokey |author1-link=Nancy Stokey | first2=Robert E. |last2=Lucas |year=1989 |author-link2=Robert Lucas Jr. |title=Recursive Methods in Economic Dynamics |location=Cambridge |publisher=Harvard University Press |pages=49–55 |isbn=978-0-674-75096-8 |url=https://books.google.com/books?id=BgQ3AwAAQBAJ&pg=PA49 }}

Firmly non-expansive mapping

A non-expansive mapping with $k=1$ can be generalized to a firmly non-expansive mapping in a Hilbert space $\mathcal{H}$ if the following holds for all x and y in $\mathcal{H}$ :

: $\|f(x)-f(y) \|^2 \leq \, \langle x-y, f(x) - f(y) \rangle.$

where

: $d(x,y) = \|x-y\|$ .

This is a special case of $\alpha$ averaged nonexpansive operators with $\alpha = 1/2$ .{{cite journal |title=Solving monotone inclusions via compositions of nonexpansive averaged operators |first=Patrick L. |last=Combettes |year=2004 |journal=Optimization |volume=53 |issue=5–6 |pages=475–504 |doi=10.1080/02331930412331327157 |s2cid=219698493 }} A firmly non-expansive mapping is always non-expansive, via the Cauchy–Schwarz inequality.

The class of firmly non-expansive maps is closed under convex combinations, but not compositions.{{Cite book|title=Convex Analysis and Monotone Operator Theory in Hilbert Spaces|last=Bauschke|first=Heinz H.|publisher=Springer|year=2017|location=New York}} This class includes proximal mappings of proper, convex, lower-semicontinuous functions, hence it also includes orthogonal projections onto non-empty closed convex sets. The class of firmly nonexpansive operators is equal to the set of resolvents of maximally monotone operators.{{Cite journal|last=Combettes|first=Patrick L.|date=July 2018|title=Monotone operator theory in convex optimization|journal=Mathematical Programming|volume=B170|pages=177–206|arxiv=1802.02694|doi=10.1007/s10107-018-1303-3|bibcode=2018arXiv180202694C|s2cid=49409638}} Surprisingly, while iterating non-expansive maps has no guarantee to find a fixed point (e.g. multiplication by -1), firm non-expansiveness is sufficient to guarantee global convergence to a fixed point, provided a fixed point exists. More precisely, if $\operatorname{Fix}f := \{x \in \mathcal{H} \ | \ f(x) = x\} \neq \varnothing$ , then for any initial point $x_0 \in \mathcal{H}$ , iterating

$(\forall n \in \mathbb{N})\quad x_{n+1} = f(x_n)$

yields convergence to a fixed point $x_n \to z \in \operatorname{Fix} f$ . This convergence might be weak in an infinite-dimensional setting.

Subcontraction map

A subcontraction map or subcontractor is a map f on a metric space (M, d) such that

: $d(f(x), f(y)) \leq d(x,y);$

: $d(f(f(x)),f(x)) < d(f(x),x) \quad \text{unless} \quad x = f(x).$

If the image of a subcontractor f is compact, then f has a fixed point.{{cite book | last=Goldstein | first=A.A. | title=Constructive real analysis | zbl=0189.49703 | series=Harper's Series in Modern Mathematics | location=New York-Evanston-London | publisher=Harper and Row | year=1967 |page=17 }}

Locally convex spaces

In a locally convex space (E, P) with topology given by a set P of seminorms, one can define for any p ∈ P a p-contraction as a map f such that there is some k_p < 1 such that {{nowrap|p(f(x) − f(y))}} ≤ {{nowrap|k_p p(x − y)}}. If f is a p-contraction for all p ∈ P and (E, P) is sequentially complete, then f has a fixed point, given as limit of any sequence x_n+1 = f(x_n), and if (E, P) is Hausdorff, then the fixed point is unique.{{cite journal |first1=G. L. Jr. |last1=Cain |first2=M. Z. |last2=Nashed |author-link2=Zuhair Nashed |title=Fixed Points and Stability for a Sum of Two Operators in Locally Convex Spaces |journal=Pacific Journal of Mathematics |volume=39 |issue=3 |year=1971 |pages=581–592 |doi=10.2140/pjm.1971.39.581 |doi-access=free }}

Contraction mapping#Firmly non-expansive mapping

Firmly non-expansive mapping

Subcontraction map

Locally convex spaces

See also

References

Further reading