1 Definition and Basic Properties
1.1 Nonexpansive mappings in metric spaces
Let \((X,d_X)\) and \((Y,d_Y)\) be metric spaces. A mapping \(T:X\to Y\) is nonexpansive if for all \(x_1,x_2\in X\), \[ d_Y(Tx_1,Tx_2)\le d_X(x_1,x_2). \] Intuitively, \(T\) never stretches distances; it may keep them the same or compress them.
This definition is purely metric and does not require linear structure. It is stable under restriction to subsets and under composing with isometries on either side (when the compositions are well-defined).
1.2 Nonexpansive mappings in normed linear spaces
| If \(X\) is a normed linear space with metric \(d(x,y)=\|x-y\|\), and \(T:X\to X\) (or to another normed space) is single-valued, then nonexpansiveness becomes |
|---|
\[
| \|T x - T y\|\le \|x-y\|\quad\text{for all }x,y. |
|---|
\] In this setting, nonexpansive maps are often discussed alongside other “distance-controlled” maps, such as Lipschitz mappings and contractions. The constant governing the inequality is exactly \(1\) for nonexpansiveness.
1.3 Relationship to Lipschitz continuity
Nonexpansiveness is the Lipschitz property with Lipschitz constant equal to \(1\). More precisely, a map is nonexpansive iff it is \(1\)-Lipschitz with respect to the chosen metrics induced by norms.
This connection clarifies why nonexpansive maps are useful in analysis: many arguments depend only on the fact that iterates cannot enlarge distances too rapidly, even if they do not shrink them.
1.4 Examples and counterexamples
Example (identity and isometries). The identity map \(T(x)=x\) is nonexpansive. Any isometry (distance-preserving map) is also nonexpansive because it satisfies equality in the defining inequality.
Example (projections in Hilbert space). In a Hilbert space, the metric projection onto a closed convex set is nonexpansive. This is a fundamental geometric source of nonexpansive operators.
Example (averaging). Maps of the form \(T=\frac{1}{2}(I+S)\) with \(S\) nonexpansive are nonexpansive under appropriate assumptions; such constructions are common in algorithmic splitting methods.
| Counterexample (distance-increasing map). If \(T(x)=2x\) on a normed space, then \(\|Tx-Ty\|=2\|x-y\|\), so the defining inequality fails and \(T\) is expansive, not nonexpansive. |
|---|
Subtlety. A map can be Lipschitz with constant \(1\) without being linear or smooth; nonexpansiveness is about global distance behavior, not differentiability.
2 Connections to Other Classes of Maps
2.1 Contractions and strict contractivity
A map is a contraction if there exists \(\alpha\in[0,1)\) such that \[
| \|Tx-Ty\|\le \alpha\|x-y\|\quad\text{for all }x,y. |
|---|
\] Every contraction is nonexpansive, but the converse is false: a nonexpansive map may preserve distances in some directions and therefore need not yield the strong convergence guarantees typical of contraction mappings.
In fixed point theory, contractions lead to uniqueness and geometric convergence of Picard iterates under completeness assumptions. Nonexpansive maps generally require weaker or more delicate conditions.
2.2 Expansive and isometric mappings
A mapping is expansive (in one common usage) if it expands distances by a factor greater than \(1\) on some scale, e.g. \[
| \|Tx-Ty\|\ge c\|x-y\| |
|---|
\] with \(c>1\) for all or relevant pairs. Exact inequalities vary by definition, but the key contrast with nonexpansiveness is that distances are forced to grow.
Isometries are the extreme opposite of strict contractivity: they satisfy \[ d(Tx,Ty)=d(x,y) \] for all \(x,y\). Thus isometries are nonexpansive with equality everywhere, and they are typically not contractive.
2.3 Firmly nonexpansive mappings
A mapping \(T\) is firmly nonexpansive if it satisfies a stronger inequality than nonexpansiveness. In a Hilbert space, one standard characterization is: \[
| \|Tx-Ty\|^2 \le \langle Tx-Ty,\, x-y\rangle\quad\text{for all }x,y. |
|---|
\] Firm nonexpansiveness implies nonexpansiveness. Conceptually, it encodes a form of “averaging” or “monotonicity-like” behavior that is particularly well suited for proximal algorithms and resolvent operators.
2.4 Averaged and nonexpansive operators
An operator \(T\) is averaged if it can be written as \[ T = (1-\lambda)I + \lambda S \] for some \(\lambda\in(0,1)\) and some nonexpansive \(S\). Averaged maps form a structured subclass of nonexpansive operators. In many convergence proofs, showing that an update map is averaged provides access to Fejér monotonicity-type arguments and yields convergence of iterates under mild conditions.
3 Fixed Point Theory for Nonexpansive Maps
3.1 Existence of fixed points (high-level conditions)
Given \(T:C\to C\) on a subset \(C\) of a metric or Banach space, fixed point theory asks whether there exists \(x^\ast\in C\) with \(Tx^\ast=x^\ast\).
For nonexpansive maps, existence is not automatic. Typical sufficient conditions involve:
- compactness (or relative compactness) in appropriate settings, combined with continuity,
- convexity and geometric properties of the underlying space (e.g., reflexivity and weak compactness),
- and invariance of closed convex subsets under \(T\).
In Banach spaces, additional assumptions such as normal structure or related geometric conditions can be needed to ensure fixed points for nonexpansive self-maps on bounded closed convex sets.
3.2 Uniqueness versus non-uniqueness
Nonexpansive mappings generally do not have unique fixed points. Uniqueness is typical for contractions, where strict distance reduction prevents multiple fixed points except in degenerate cases.
For nonexpansive maps, the fixed point set may be:
- a single point,
- a convex subset,
- or a more complicated closed set, depending on structure and additional properties such as firm nonexpansiveness or monotonicity.
3.3 Fixed point sets and invariance properties
When \(T\) is nonexpansive and the space has suitable convexity/linear structure, fixed point sets often inherit stability:
- convexity may hold for firmly nonexpansive or averaged operators in Hilbert spaces,
- closedness is commonly obtained under continuity assumptions,
- and fixed point sets are invariant under certain related constructions (e.g., iterates \(T^n\) share the same fixed points for many operator classes).
These properties are important because they allow iterative algorithms to be analyzed relative to the distance from the fixed point set rather than to an individual fixed point.
3.4 Stability and perturbation viewpoints
Because nonexpansive mappings may fail to be strictly contractive, small perturbations can have nontrivial effects on convergence behavior. Modern viewpoints in the field often frame stability in terms of:
- continuity of solutions under changes in the operator,
- robustness of iterative schemes under errors in evaluation,
- and resilience to relaxation parameters.
A common theme is that although iterates may not converge quickly, they can still remain controlled and approach fixed points when perturbations satisfy summability or vanishing conditions.
4 Iterative Methods and Convergence
4.1 Picard iteration for nonexpansive maps
The Picard iteration applies \(T\) repeatedly: \[ x_{n+1}=T x_n. \] For contractions, Picard iterates converge strongly to the unique fixed point. For nonexpansive maps, convergence may fail or only occur under additional hypotheses (e.g., existence of fixed points plus compactness, or special geometric conditions). Even when convergence does not hold for every starting point, subsequences or weak limits are often studied.
4.2 Krasnosel’skiĭ–Mann iteration
A standard approach for nonexpansive maps is Krasnosel’skiĭ–Mann iteration, which introduces relaxation: \[ x_{n+1} = (1-\alpha_n) x_n + \alpha_n\, T x_n, \] where \(\alpha_n\in(0,1)\). The averaging introduced by relaxation can prevent oscillations and often yields convergence under assumptions like:
- nonexpansiveness of \(T\),
- boundedness of the orbit,
- and conditions on the relaxation sequence \((\alpha_n)\), such as \(\sum \alpha_n(1-\alpha_n)=\infty\) in some formulations.
4.3 Halpern-type iterations (overview)
Halpern-type methods blend the iterates with an external anchor point \(u\): \[ x_{n+1} = \alpha_n u + (1-\alpha_n) T x_n. \] These schemes frequently produce convergence without requiring strict contractivity, particularly in Hilbert spaces and under suitable step-size conditions. Conceptually, the anchor point guides the sequence toward a fixed point while the map’s nonexpansive behavior maintains stability.
4.4 Role of weak versus strong convergence
In Hilbert and Banach spaces, convergence can be interpreted in different senses:
| - strong convergence: \(\|x_n-x^\ast\|\to 0\), |
|---|
- weak convergence: \(x_n\rightharpoonup x^\ast\), meaning convergence of inner products (or functionals).
For nonexpansive maps, weak convergence is often more accessible and may be the natural outcome. Strong convergence can require additional regularity, compactness, or structural assumptions such as uniform convexity and suitable properties of the operator (e.g., firm nonexpansiveness or demiregularity in some frameworks).
5 Geometric and Analytical Tools
5.1 Convexity, uniform convexity, and nonexpansiveness
Geometry of the underlying space heavily influences convergence. Convexity notions control how distances behave under averages of points:
- In convex sets, nonexpansive maps interact with line segments to support Fejér-type monotonicity arguments.
- Uniform convexity strengthens weak-to-strong convergence implications: bounded sequences that converge weakly and satisfy additional norm conditions can converge strongly.
These properties are crucial when proving that iterates generated by nonexpansive operators approach a fixed point rather than merely converging weakly.
5.2 Hilbert space structure and projection operators
Hilbert spaces provide inner product structure and a powerful projection theory. For closed convex sets \(C\), the orthogonal projection \(P_C\) is nonexpansive and often firmly nonexpansive. Such operators serve as building blocks for algorithms:
- projection onto feasible sets,
- proximal steps for regularizers,
- and resolvents of monotone operators.
The interplay between geometry (convexity) and operator inequalities (nonexpansiveness or firm nonexpansiveness) is central to many convergence proofs.
5.3 Variational inequalities perspective
Many problems in optimization and equilibrium can be expressed via variational inequalities or monotone inclusions. Nonexpansive operators often arise as resolvents or proximal maps associated with these formulations. From that viewpoint, fixed points correspond to solutions of variational inequality problems.
A variational inequality formulation translates the solution requirement into an inequality involving dual pairings or inner products. Nonexpansiveness then provides a mechanism to design iterations whose fixed points correspond to solutions.
5.4 Demiclosedness principles (conceptual summary)
Demiclosedness principles address the behavior of sequences under nonexpansive mappings. A typical conceptual statement is: if \(x_n\) converges weakly to \(x\), and \((I-T)x_n\) converges (often strongly) to \(0\), then \(x\) is a fixed point of \(T\).
This idea is a key tool in extending convergence from approximate fixed points (where \(Tx_n\approx x_n\)) to exact fixed points. It helps justify why limit points of iterative sequences produced by nonexpansive operators are indeed solutions.
6 Special Cases and Constructions
6.1 Nonexpansive affine maps
An affine map \(T(x)=Ax+b\) on a normed space is nonexpansive precisely when its linear part satisfies an appropriate operator norm bound: \[
| \|A\|\le 1 |
|---|
\] in the induced operator norm, since the translation \(b\) cancels in differences \(T x-T y = A(x-y)\).
These maps are useful test cases because they allow explicit computation of iterates and spectra, while still exhibiting the full generality of nonexpansive behavior.
6.2 Nonexpansive resolvents and proximal mappings (framework)
A major source of nonexpansive operators is the resolvent of a monotone operator and the proximal mapping of a convex function. While the underlying definitions involve additional structures (monotonicity, convexity), the resulting operators often satisfy firm nonexpansiveness and hence are nonexpansive.
This framework ties operator theory to optimization: proximal and resolvent steps can be interpreted as “regularized” minimization procedures, and their fixed points correspond to solutions of inclusion or optimization problems.
6.3 Operators induced by convex functions
Given a convex, lower semicontinuous function \(\phi\), many gradient-like or subgradient-related constructions lead to nonexpansive mappings after applying suitable transformations (e.g., resolvents of subdifferentials, or proximal operators).
The guiding principle is that convexity yields monotonicity properties, which in turn produce nonexpansiveness/firm nonexpansiveness for operator transforms. This creates a systematic route from convex modeling to convergent iterative schemes.
6.4 Compositions and sums (conditions and behavior)
Nonexpansiveness is not generally preserved under arbitrary composition or summation. However, several structured operations maintain good behavior:
- compositions of specific averaged/nonexpansive classes can remain averaged,
- sums may be nonexpansive under constraints on step sizes and the Lipschitz or monotonicity properties of components,
- and convex combinations are often benign because averaging typically reduces or controls distance growth.
In practice, algorithms are designed to fit these stability-preserving patterns, enabling convergence proofs for composite update rules.
7 Applications and Model Problems
7.1 Equilibrium and variational problem formulations
Equilibrium problems, such as those requiring satisfaction of inequality constraints, can be reformulated in operator terms where solutions correspond to fixed points of nonexpansive mappings. Nonexpansive operators capture the idea of updating a candidate state without amplifying discrepancies.
This connection underpins broad modeling patterns: rather than solving a difficult equation directly, one seeks a fixed point of an operator derived from the equilibrium conditions.
7.2 Signal processing and regularization (general motivation)
In signal processing, regularization methods often generate iterative schemes where each step is a nonexpansive transformation (or can be approximated by one). The nonexpansive property helps ensure that the algorithm does not magnify noise-related perturbations beyond a controlled level.
While specific applications vary widely, the recurring structure is:
- map an iterate toward data fidelity,
- map it toward regularity or constraints,
- and combine the effects using operators with controlled Lipschitz behavior.
7.3 Optimization algorithms with nonexpansive steps
Many optimization routines, particularly in proximal-gradient and splitting methods, rely on nonexpansive or averaged operators. For instance, proximal steps are typically firmly nonexpansive under convexity assumptions, while gradient steps can be nonexpansive after selecting step sizes consistent with Lipschitz constants.
As a result, the overall update map often falls into a class of averaged or nonexpansive operators, enabling convergence analyses based on fixed point theory.
7.4 Mechanics of convergence proofs (outline)
Convergence arguments for nonexpansive maps often use a combination of:
- boundedness of iterates,
- distance decrease in a suitable sense (e.g., Fejér monotonicity with respect to the fixed point set),
- existence of weak cluster points via compactness or reflexivity,
- identification of cluster points as fixed points using demiclosedness principles,
- and then upgrading convergence (weak to strong) under additional geometric or regularity assumptions.
This “template” varies by setting, but it reflects how nonexpansiveness controls the geometry of iterative sequences.
8 Technical Variants and Extensions
8.1 Asymptotically nonexpansive mappings (overview)
An asymptotically nonexpansive mapping relaxes the strict distance control of nonexpansiveness by allowing a small expansion factor that tends to \(1\) as the iteration progresses (or as points vary in a limiting regime). Such operators appear naturally when algorithms are implemented with approximations or when models are imperfect.
The goal is to retain enough control to establish convergence toward fixed points even when each step is only approximately nonexpansive.
8.2 Local nonexpansiveness and step-size constraints
Sometimes a map is guaranteed to be nonexpansive only on a restricted region or under a constraint such as a bound on step size. In optimization, for example, the operator associated with a gradient step may be nonexpansive only when the step size does not exceed a threshold derived from the Lipschitz constant of the gradient.
Local nonexpansiveness still supports convergence proofs provided the iterates remain inside the region where the property holds.
8.3 Set-valued extensions (nonexpansive correspondences)
The concept extends to set-valued maps \(F:X\rightrightarrows Y\). A nonexpansive correspondence typically uses a set distance such as the Hausdorff metric or a related notion defined through selections. Fixed point theory then concerns points \(x\) for which \(x\in F(x)\).
Set-valued extensions arise in differential inclusions and variational frameworks where exact single-valued update rules are replaced by feasible sets of responses.
8.4 Nonexpansive mappings in Banach versus Hilbert spaces
Hilbert spaces offer inner product identities that strengthen inequalities and support firm nonexpansiveness tools. Banach spaces, lacking an inner product, require alternative geometric conditions (e.g., uniform convexity, smoothness, or structural properties related to fixed point theorems).
As a result, many results parallel the Hilbert case but differ in the specific assumptions and the typical mode of convergence that can be concluded.