Proof of A Perturbed Maximum Principle of Borwein-Preiss Type in a Real Hilbert Space

Notation and constants. Put $\varepsilon=\mu\lambda^{2}$, a positive real number, and define sequences of positive real numbers by

By claim 4 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series and claim 1 of Elementary Properties of Series of Real Numbers, the series $\sum_{k=1}^{\infty}\mu_{k}$ converges with

Since $0\le\tfrac{1}{8}\le\tfrac{1}{2}$, claim 5 of Properties of Natural Number Powers in a Field gives $\bigl(\tfrac{1}{8}\bigr)^{k}\le\bigl(\tfrac{1}{2}\bigr)^{k}$, so by claim 3 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series the series $\sum_{k=1}^{\infty}\delta_{k}$ converges with $\sum_{k=1}^{\infty}\delta_{k}\le\varepsilon$. Also $\delta_{k+1}\le\delta_{k}$ for every $k$, by the same monotonicity of powers.

Indices. Every $k\in\mathbb{N}$ is either $1$ or of the form $m+1$ with $m\in\mathbb{N}$: the set of $k$ with this property contains $1$ and contains $S(m)=m+1$ whenever it contains $m$, hence is all of $\mathbb{N}$ by induction as in Natural Numbers. Moreover, if $n,k\in\mathbb{N}$ satisfy $n+1\le k$, then $k=m+1$ for some $m$ with $n\le m$. Indeed $k\ne1$: if $k=1$ then $n+1\le1$, while $1\le n$ by claim 4 of Properties of the Order on the Natural Numbers and $n\le n+1$ by claims 5 and 1 of that lemma, so transitivity gives $n\le1$ and $n+1\le n$, hence $n=n+1$ by claim 2 and therefore $n<n$, which claim 2 excludes. So $k=m+1$ for some $m\in\mathbb{N}$; and if $n\le m$ failed, then $m<n$ by claim 3, hence $m\le n$ and $m+1\le n+1$ by claims 1 and 6, while $m+1\ne n+1$ because $S$ is injective by Natural Numbers, so $n+1\le m+1$ and $m+1\le n+1$ would force $m+1=n+1$ by claim 2, a contradiction.

A tail estimate. Let $(w_{k})_{k\in\mathbb{N}}$ be nonnegative real numbers such that $\sum_{k=1}^{\infty}\mu_{k}w_{k}$ converges, let $n\in\mathbb{N}$, and let $M$ be a nonnegative real with $w_{k}\le M$ for every $k$ with $n\le k$. Then

Indeed, one shows by induction on $m$ that $n\le m$ implies

for $m=1$ we have $n=1$ by claims 4 and 2 of Properties of the Order on the Natural Numbers and both sides vanish; and if $n\le m+1$ then either $n=m+1$, when both sides vanish, or $n\le m$ by claim 5 of that lemma, and adding $\mu_{m+1}w_{m+1}\le\mu_{m+1}M$, valid by claim 5 of Elementary Arithmetic in an Ordered Field, to the inductive hypothesis gives the statement for $m+1$. Letting $m$ tend to infinity and using claim 1 of Order Properties of Limits of Real Sequences together with the displayed value of the tail of $\sum\mu_{k}$ yields the estimate.

Construction of the centres. Let $\mathcal{T}$ be the set of pairs $(n,v)$ with $n\in\mathbb{N}$ and $v:[n]\to A$ a map with $v_{1}=x_{0}$; it is nonempty, since $A$ contains $x_{0}$. For $(n,v)\in\mathcal{T}$ define $\Psi^{v}:A\to\mathbb{R}$ by

The subtracted finite sum is nonnegative by claim 5 of Properties of Finite Sums, so $\Psi^{v}\le\Phi$ and $\Psi^{v}$ is bounded above; as $A$ is nonempty, $\sup_{x\in A}\Psi^{v}(x)$ exists.

Let $R$ be the set of pairs $\bigl((n,v),(n',v')\bigr)$ in $\mathcal{T}\times\mathcal{T}$ with $n'=n+1$, with $v'_{k}=v_{k}$ for every $k\in[n]$, and with

For every $(n,v)\in\mathcal{T}$ such a successor exists: by claim 3 of Approximation Property of the Supremum and the Infimum in $\mathbb{R}$ there is $a\in A$ with $\sup_{x\in A}\Psi^{v}(x)-\delta_{n}<\Psi^{v}(a)$, and the map $v':[n+1]\to A$ with $v'_{k}=v_{k}$ for $k\in[n]$ and $v'_{n+1}=a$ is well defined, because every element of $[n+1]$ either lies in $[n]$ or equals $n+1$ by claim 5 of Properties of the Order on the Natural Numbers.

By Axiom of Dependent Choice, applied to $\mathcal{T}$, to $R$ and to the element $(1,v^{1})$ with $v^{1}_{1}=x_{0}$, there is a sequence $\bigl((n_{m},v^{m})\bigr)_{m\in\mathbb{N}}$ in $\mathcal{T}$ with $(n_{1},v^{1})$ as its first term and consecutive terms related by $R$. Then $n_{m}=m$ for every $m$, by induction. Define $x_{k}=v^{k}_{k}$ for $k\in\mathbb{N}$; by induction on $m$, $v^{m}_{k}=x_{k}$ for every $k\in[m]$. Writing

we therefore have $x_{1}=x_{0}$, $x_{k}\in A$ for every $k$, and

Also $\Psi_{n+1}\le\Psi_{n}\le\Phi$ pointwise, since the additional subtracted terms are nonnegative, so $\sigma_{n+1}\le\sigma_{n}\le\sup_{x\in A}\Phi(x)$; and $\Psi_{n+1}(x_{n+1})=\Psi_{n}(x_{n+1})$, because the extra term $\mu_{n+1}|x_{n+1}-x_{n+1}|^{2}$ vanishes.

The step estimate. Write $D_{j}=|x_{j+1}-x_{j}|$. We claim that $D_{j}\le4\lambda\bigl(\tfrac{1}{2}\bigr)^{j}$ for every $j\in\mathbb{N}$.

For $j=1$: by $(*)$ and $\Psi_{1}(x_{1})=\Phi(x_{1})$ we get $\Psi_{1}(x_{2})\ge\sigma_{1}-\delta_{1}\ge\Psi_{1}(x_{1})-\delta_{1}=\Phi(x_{1})-\delta_{1}$, while $\Psi_{1}(x_{2})=\Phi(x_{2})-\mu_{1}D_{1}^{2}\le\Phi(x_{1})+\varepsilon-\mu_{1}D_{1}^{2}$ by the hypothesis on $x_{0}=x_{1}$. Hence $\mu_{1}D_{1}^{2}\le\varepsilon+\delta_{1}\le2\varepsilon$, and since $\mu_{1}=\mu\bigl(\tfrac{1}{2}\bigr)$,

For $j=n+1$: by $(*)$ at $n+1$ and $\Psi_{n+1}(x_{n+1})=\Psi_{n}(x_{n+1})$,

while $(*)$ at $n$ gives $\Psi_{n}(x_{n+1})\ge\sigma_{n}-\delta_{n}\ge\Psi_{n}(x_{n+2})-\delta_{n}$. Combining,

so, dividing by $\mu_{n+1}=\mu\bigl(\tfrac{1}{2}\bigr)^{n+1}$ and using claim 3 of Properties of Natural Number Powers in a Field,

In both cases the two numbers compared are nonnegative, so claim 1 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field and trichotomy give $D_{j}\le4\lambda\bigl(\tfrac{1}{2}\bigr)^{j}$, as claimed, since by the index observation every $j$ is $1$ or of the form $n+1$.

Convergence of the centres. Apply claim 5 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series with the weights $\bigl(\tfrac{1}{2}\bigr)^{k}$, the bound $M=4\lambda$ and the numbers $w_{k}=D_{k}\bigl/\bigl(\tfrac{1}{2}\bigr)^{k}$, which satisfy $0\le w_{k}\le4\lambda$ by the step estimate: the series $\sum_{k=1}^{\infty}D_{k}$ converges and, writing $T$ for its sum and $T_{n}$ for its partial sums,

Moreover $T\le4\lambda$: by the step estimate $0\le D_{k}\le4\lambda\bigl(\tfrac{1}{2}\bigr)^{k}$, and the series with terms $4\lambda\bigl(\tfrac{1}{2}\bigr)^{k}$ converges with sum $4\lambda$ by claim 1 of Elementary Properties of Series of Real Numbers, so claim 3 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series applies. Thus $\sum_{k=1}^{\infty}(x_{k+1}-x_{k})$ converges absolutely, hence converges by claim 5 of Elementary Properties of Series in a Real Inner Product Space, and therefore $(x_{k})_{k\in\mathbb{N}}$ converges by claim 3 of that lemma. Let $\bar{x}$ denote its limit in $H$.

By induction, $|x_{m+1}-x_{1}|\le T_{m}\le T\le4\lambda$ for every $m$, using The Norm Metric of a Real Inner Product Space: Triangle Inequalities, Limits and Continuity §triangle in the inductive step and claim 2 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series for $T_{m}\le T$; since $|x_{1}-x_{1}|=0$, we get $|x_{k}-x_{1}|\le4\lambda$ for every $k$. Similarly, by induction on $m$ one obtains, for $n\le m$,

the case $m=n$ being trivial and the step using the triangle inequality. By the index observation, this gives

Since $\bigl||x_{k}-x_{1}|-|\bar{x}-x_{1}|\bigr|\le|x_{k}-\bar{x}|$ by The Norm Metric of a Real Inner Product Space: Triangle Inequalities, Limits and Continuity §reverse-triangle, the sequence $(|x_{k}-x_{1}|)$ converges to $|\bar{x}-x_{1}|$, so claim 1 of Order Properties of Limits of Real Sequences gives $|\bar{x}-x_{1}|\le4\lambda$; the same argument applied to $(**)$ gives $|\bar{x}-x_{n+1}|\le4\lambda\bigl(\tfrac{1}{2}\bigr)^{n}$.

The centre $\bar{y}$ and the collapse of the perturbation. Since $|\mu_{k}x_{k}|=\mu_{k}|x_{k}|\le\mu_{k}\bigl(|x_{1}|+4\lambda\bigr)$, claim 3 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series shows that $\sum_{k=1}^{\infty}|\mu_{k}x_{k}|$ converges, so $\sum_{k=1}^{\infty}\mu_{k}x_{k}$ converges by claim 5 of Elementary Properties of Series in a Real Inner Product Space. Define

The map $\mathbb{R}\to H$ sending $s$ to $s\,x_{1}$ is linear and bounded, so claim 6 of Elementary Properties of Series in a Real Inner Product Space, together with claim 8 of that lemma, gives $\sum_{k=1}^{\infty}\mu_{k}x_{1}=\mu x_{1}$. Hence, by claim 1 of Elementary Properties of Series in a Real Inner Product Space, the series $\sum_{k=1}^{\infty}\mu_{k}(x_{k}-x_{1})$ converges with sum $\mu\bar{y}-\mu x_{1}$, and by claim 5 of that lemma and claim 3 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series,

so $|\bar{y}-x_{1}|\le4\lambda$. Together with $|\bar{x}-x_{1}|\le4\lambda$, $x_{1}=x_{0}$ and The Norm Metric of a Real Inner Product Space: Triangle Inequalities, Limits and Continuity §triangle, this proves claim 1 of the theorem, the bound $|\bar{x}-\bar{y}|\le8\lambda$ following from $|\bar{x}-x_{0}|+|x_{0}-\bar{y}|\le8\lambda$.

Next, let $x\in A$ and put $w_{k}(x)=|x-x_{k}|^{2}$. By The Norm Metric of a Real Inner Product Space: Triangle Inequalities, Limits and Continuity §triangle, $|x-x_{k}|\le|x-x_{1}|+4\lambda$, so the $w_{k}(x)$ are nonnegative and bounded by $M(x)=\bigl(|x-x_{1}|+4\lambda\bigr)^{2}$; by claim 5 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series the series $\sum_{k=1}^{\infty}\mu_{k}w_{k}(x)$ converges. By Elementary Identities in a Real Inner Product Space §expansion,

The series $\sum_{k=1}^{\infty}\mu_{k}|x|^{2}$ converges to $\mu|x|^{2}$ by claim 1 of Elementary Properties of Series of Real Numbers; the series $\sum_{k=1}^{\infty}\mu_{k}|x_{k}|^{2}$ converges, by claim 3 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series, to a real number $K$; and by claim 7 of Elementary Properties of Series in a Real Inner Product Space, applied to the convergent series $\sum_{k=1}^{\infty}\mu_{k}x_{k}$ and the vector $x$, together with conditions (a) and (c) of Real Inner Product Space §inner-product,

Hence, by claim 1 of Elementary Properties of Series of Real Numbers and Elementary Identities in a Real Inner Product Space §expansion once more,

with $C_{0}$ independent of $x$. Writing

we therefore have $\Psi_{\infty}=\Psi-C_{0}$ on $A$, where $\Psi(x)=\Phi(x)-\mu|x-\bar{y}|^{2}$. Since the partial sums of a series of nonnegative terms are at most its sum, by claim 2 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series, we also have $\Psi_{\infty}\le\Psi_{n}$ on $A$ for every $n$.

The residuals. Fix $n\in\mathbb{N}$ and put

Since $w_{n+1}(x_{n+1})=0$, the partial sums up to $n$ and up to $n+1$ agree, so $R_{n}$ is also the tail beyond $n+1$. By $(**)$, $w_{k}(x_{n+1})\le16\lambda^{2}\bigl(\tfrac{1}{4}\bigr)^{n}$ for every $k$ with $n+1\le k$, so the tail estimate, applied with the index $n+1$, gives

Put $\rho_{n}=R_{n}+\delta_{n}$. Since $\bigl(\tfrac{1}{4}\bigr)^{n}\le1$ we get $R_{n}\le16\lambda^{2}\mu\bigl(\tfrac{1}{2}\bigr)^{n}$, so $(R_{n})$ and $(\delta_{n})$, hence $(\rho_{n})$, converge to $0$ by claim 4 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series, claims 1 and 3 of Arithmetic of Limits of Real Sequences and claim 2 of Order Properties of Limits of Real Sequences. Moreover, dividing the two bounds by $\mu_{n+1}=\mu\bigl(\tfrac{1}{2}\bigr)^{n+1}$,

so $\rho_{n}\bigl/\mu_{n+1}\le18\lambda^{2}\bigl(\tfrac{1}{4}\bigr)^{n}$, and this sequence converges to $0$.

Near-optimality, and $\bar{x}\in A$. By $(*)$ and $\Psi_{n+1}(x_{n+1})=\Psi_{n}(x_{n+1})$ we have $\sigma_{n+1}\ge\Psi_{n+1}(x_{n+1})=\Psi_{n}(x_{n+1})\ge\sigma_{n}-\delta_{n}$. By induction, $\sigma_{n+1}\ge\sigma_{1}-\sum_{k=1}^{n}\delta_{k}$ for every $n$, and since $\sum_{k=1}^{n}\delta_{k}\le\sum_{k=1}^{\infty}\delta_{k}\le\varepsilon$ by claim 2 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series, and $\sigma_{1}\ge\Psi_{1}(x_{1})=\Phi(x_{1})\ge\sup_{x\in A}\Phi(x)-\varepsilon$, we obtain

the case $m=1$ being the bound on $\sigma_{1}$ itself and the remaining cases following from the index observation.

Since $\Psi_{n}\le\Phi$, $(*)$ gives $\Phi(x_{n+1})\ge\Psi_{n}(x_{n+1})\ge\sigma_{n}-\delta_{n}\ge\sup_{x\in A}\Phi(x)-2\varepsilon-\delta_{n}$. Let $\eta$ be positive and choose $M\in\mathbb{N}$ with $\delta_{n}<\eta$ for $M\le n$. The sequence $(y_{m})_{m\in\mathbb{N}}$ with $y_{m}=x_{M+m+1}$ lies in $A$ and converges to $\bar{x}$, because $M\le M+m$ for every $m$ and $(x_{k})$ converges to $\bar{x}$; and $\Phi(y_{m})\ge\sup_{x\in A}\Phi(x)-2\varepsilon-\eta$ for every $m$. By claim 1 of Functions with Closed Superlevel Sets: Sequential Characterisation, Semicontinuity, Perturbation and Limits, $\bar{x}\in A$ and $\Phi(\bar{x})\ge\sup_{x\in A}\Phi(x)-2\varepsilon-\eta$. As $\eta$ was arbitrary, Comparison of Real Numbers with Arbitrary Positive Slack gives

which is claim 3 of the theorem.

$\bar{x}$ maximises $\Psi$. The map $H\to\mathbb{R}$, $x\mapsto\mu|x-\bar{y}|^{2}+C_{0}$, is continuous: $\bigl||x-\bar{y}|-|x'-\bar{y}|\bigr|\le|x-x'|$ by The Norm Metric of a Real Inner Product Space: Triangle Inequalities, Limits and Continuity §reverse-triangle, so $x\mapsto|x-\bar{y}|$ is continuous, and the assertion follows from Continuity Between Metric Spaces is Equivalent to Sequential Continuity with claims 1, 2 and 3 of Arithmetic of Limits of Real Sequences. Since $\Psi_{\infty}(x)=\Phi(x)-\bigl(\mu|x-\bar{y}|^{2}+C_{0}\bigr)$, claim 3 of Functions with Closed Superlevel Sets: Sequential Characterisation, Semicontinuity, Perturbation and Limits shows that $\Psi_{\infty}$ has closed superlevel sets in $H$.

Let $x\in A$ and $n\in\mathbb{N}$. Then

using $(*)$ for the third inequality. Let $\eta$ be positive and choose $M$ with $\rho_{n}<\eta$ for $M\le n$; then $\Psi_{\infty}(x_{n+1})\ge\Psi_{\infty}(x)-\eta$ for such $n$. The sequence $(y_{m})$ with $y_{m}=x_{M+m+1}$ lies in $A$, converges to $\bar{x}$, and satisfies $\Psi_{\infty}(y_{m})\ge\Psi_{\infty}(x)-\eta$ for every $m$, so claim 1 of Functions with Closed Superlevel Sets: Sequential Characterisation, Semicontinuity, Perturbation and Limits gives $\Psi_{\infty}(\bar{x})\ge\Psi_{\infty}(x)-\eta$. As $\eta$ was arbitrary, Comparison of Real Numbers with Arbitrary Positive Slack gives $\Psi_{\infty}(\bar{x})\ge\Psi_{\infty}(x)$, and hence $\Psi(\bar{x})\ge\Psi(x)$, for every $x\in A$.

Sequential strictness. Since $x_{n+1}\in A$, the previous paragraph gives $\Psi_{\infty}(x_{n+1})\le\Psi_{\infty}(\bar{x})$, so the displayed chain yields

Let $z\in A$ and $n\in\mathbb{N}$. By claim 2 of Series of Nonnegative Real Numbers, Comparison, and the Geometric Series, the sum of $\sum_{k=1}^{\infty}\mu_{k}w_{k}(z)$ is at least its $(n+1)$-st partial sum, so

and since $\Psi_{n}(z)\le\sigma_{n}\le\Psi_{\infty}(\bar{x})+\rho_{n}$ we obtain

Now let $(z_{m})_{m\in\mathbb{N}}$ be a sequence in $A$ such that $(\Psi(z_{m}))$ converges to $\Psi(\bar{x})$; equivalently, $(\Psi_{\infty}(z_{m}))$ converges to $\Psi_{\infty}(\bar{x})$, the two functions differing by the constant $C_{0}$. Put $\theta_{m}=\Psi_{\infty}(\bar{x})-\Psi_{\infty}(z_{m})$, a nonnegative sequence converging to $0$.

Let $\eta$ be positive. Since $\bigl(18\lambda^{2}\bigl(\tfrac{1}{4}\bigr)^{n}\bigr)$ and $\bigl(4\lambda\bigl(\tfrac{1}{2}\bigr)^{n}\bigr)$ converge to $0$, choose $n$ with

With this $n$ fixed, $\mu_{n+1}$ is a positive real number, so there is $M\in\mathbb{N}$ with $\theta_{m}\bigl/\mu_{n+1}<\tfrac{\eta^{2}}{16}$ for every $m$ with $M\le m$. For such $m$,

hence $|z_{m}-x_{n+1}|<\tfrac{\eta}{2}$ by claim 1 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field and trichotomy, and therefore, by The Norm Metric of a Real Inner Product Space: Triangle Inequalities, Limits and Continuity §triangle and $|\bar{x}-x_{n+1}|\le4\lambda\bigl(\tfrac{1}{2}\bigr)^{n}$,

As $\eta$ was an arbitrary positive real number, $(z_{m})$ converges to $\bar{x}$. Together with the maximality established above, this shows that $\Psi$ attains a sequentially strict maximum on $A$ at $\bar{x}$, which is claim 2 of the theorem.