Monotone operator

An operator $F$ on an inner product space is monotone whenfor every $v,w$. The gradient of every differentiable convex function is monotone.

An operator $G$ is $\beta$-cocoercive when $⟨Gz-Gw,z-w⟩\ge \beta \Vert Gz-Gw{\Vert }^2$ with $\beta >0$. This strengthens monotonicity and implies a Lipschitz constant $1/\beta$ by the Cauchy-Schwarz inequality. Gradient maps of smooth convex functions provide an important converse through the Baillon–Haddad theorem.

On the whole Euclidean space, an $L$-Lipschitz gradient of a convex function is $1/L$-cocoercive. Subtract the supporting affine function at one point, apply the descent lemma to a gradient step at the other point, then interchange the points and add. The conclusion needs convexity but no second derivative.

For an operator $A$, its resolvent with step $\tau >0$ is $J_{\tau A}=(I+\tau A{)}^{-1}$. A maximal monotone operator has an everywhere-defined single-valued firmly nonexpansive mapping as its resolvent. For $A=\partial f$, the resolvent is the proximal map of $\tau f$. This monotone-operator resolvent uses a different convention from the spectral resolvent of a linear operator.

A monotone operator is maximal when its graph has no proper enlargement that is still monotone. In Euclidean or Hilbert space, its resolvent of a monotone operator is single-valued and everywhere defined for every positive step. Subdifferentials of proper lower semicontinuous convex functions are fundamental examples.

A mapping $T$ on a normed vector space is nonexpansive when $\Vert T(v)-T(w)\Vert \le \Vert v-w\Vert$ for every $v,w$.

An operator is $\alpha$-averaged for $0<\alpha <1$ when $T=(1-\alpha )I+\alpha R$ for a nonexpansive mapping $R$. Averaging controls the update residual and enables fixed-point iteration. A firmly nonexpansive mapping is exactly a $1/2$-averaged operator.

In finite-dimensional Euclidean space, iterating an averaged operator with a nonempty fixed-point set converges in norm to a fixed point from every start. The averaged-operator inequality proves boundedness and a vanishing residual; compactness produces a fixed cluster point and Fejér monotonicity turns subsequential convergence into convergence of the full sequence. A fixed point must exist.

The defining averaging representation is equivalent to $\Vert Tz-Tw{\Vert }^2\le \Vert z-w{\Vert }^2-(1-\alpha )\Vert (I-T)z-(I-T)w{\Vert }^2/\alpha$. Expanding the norm of the convex combination proves both directions. Substituting a fixed point for $w$ gives Fejér monotonicity and summability of squared residuals.

A mapping $T$ on an inner product space is firmly nonexpansive whenEvery firmly nonexpansive mapping is nonexpansive, and the resolvent of a maximal monotone operator is firmly nonexpansive.

The proximal point algorithm seeks a zero of a monotone operator $F$ by repeatedly applying its resolvent:For $F=\partial f$, this is iteration of a proximal operator.

For two proximal maps $P_f,P_h$, define reflected maps $R_f=2P_f-I$ and $R_h=2P_h-I$. The Douglas--Rachford fixed-point map isBecause reflected proximal maps are nonexpansive, $T$ is firmly nonexpansive.

Finding a point in ${\bigcap }_{j=1}^{\ell }{C}_j$ is equivalent to intersecting the product $C_1\times \cdots \times C_{\ell }$ with the diagonal subspace in $({\mathbb{R}}^n{)}^{\ell }$. Projection onto the product is componentwise, while projection onto the diagonal replaces every component by their average.

Given a positive-definite matrix $M$, the preconditioned proximal point map isIt is firmly nonexpansive in the weighted inner product $⟨v,w{⟩}_M=⟨v,Mw⟩$ whenever $F$ is monotone.