Abstract Generated abstract
This paper studies the stability of relaxation processes for minimizing a differentiable functional on a convex domain in a real Hilbert space under strong monotonicity and Lipschitz type bounds on its derivative. It analyzes perturbed iterations with additive noise, measuring perturbations first by a relative quantity tied to level surfaces of the functional and then by absolute error. The authors give necessary and sufficient conditions for convergence of a relaxational perturbed process, including a divergence condition on accumulated relative error margins, and characterize linear convergence under a uniform contraction assumption. They also derive bounds showing when small absolute step errors yield convergence up to a prescribed accuracy, with corollaries relating the limiting error of the iterates to the limiting magnitude of the perturbations.
Full Text
UDC 518:517.948
MATHEMATICS
Yu. I. LYUBICH, G. D. MAISTROVSKII
ON THE STABILITY OF RELAXATION PROCESSES
(Presented by Academician L. V. Kantorovich, July 8, 1969)
Let \(\varphi(x)\) be a functional in a real Hilbert space, defined in some convex domain \(W\). Suppose that \(\varphi(x)\) has in \(W\) a derivative \(F(x)\) and
\[ m\|y\|^2 \leq (F(x+y)-Fx, y) \leq M\|y\|^2, \tag{1} \]
where \(M \geq m > 0\) are constants. We denote the minimum point of the functional by \(x^0\) and put \(\Delta(x)=\varphi(x)-\varphi(x^0)\). An operator \(\Gamma: W \to W\) will be called relaxation* if \(\varphi(\Gamma x)\leq \varphi(x)\) for all \(x \in W\).
Consider a process of the form
\[ x_{k+1}=\Gamma_k x_k \qquad (k=0,1,2,\ldots), \tag{2} \]
where \(\{\Gamma_k\}\) is a sequence of relaxation operators. We shall be interested in the behavior of the perturbed process
\[ z_{k+1}=\Gamma_k z_k+v_k \qquad (k=0,1,2,\ldots), \tag{3} \]
where \(\{v_k\}\) is noise. By convergence of a process we shall mean its convergence to the point \(x^0\), which, by virtue of (1), is equivalent to
\[ \lim_{k\to\infty}\Delta(x_k)=0. \]
We shall say that linear convergence takes place if
\[ \overline{\lim}_{k\to\infty}\frac{\Delta(z_{k+1})}{\Delta(z_k)}<1. \]
Everywhere below the family of operators \(\{\Gamma_k\}\) is assumed to be uniformly relaxation in the sense that
\[ S(\varepsilon)\equiv \sup_k\ \sup_{\Delta(x)\geq \varepsilon}\frac{\Delta(\Gamma_k x)}{\Delta(x)}<1 \qquad (\varepsilon>0) \tag{4} \]
(this condition is introduced by us only to simplify the formulations). The process (2) is relaxation, i.e. \(\varphi(x_{k+1})\leq \varphi(x_k)\) \((k=0,1,2,\ldots)\). The process (3) may already fail to be relaxation.
Consider the ray \(\Gamma_k z_k+\lambda v_k\) \((\lambda \geq 0)\) and denote by \(\tilde z_k\) the point of its intersection with the level surface \(\varphi(x)=\varphi(x_k)\). Put \(\tilde v_k=\tilde z_k-\Gamma_k z_k\). We shall characterize the magnitude of the perturbation \(v_k\) by the ratio
\[ \rho_k=\|v_k\|:\|\tilde v_k\|. \]
The relaxation property of the process (3) is, obviously, equivalent to the inequality \(\rho_k \leq 1\) \((k=0,1,2,\ldots)\).
Theorem 1. Let the perturbed process be relaxation. Then, for its convergence, it is necessary and sufficient that
\[ \sum_{k=0}^{\infty}(1-\rho_k)=\infty. \tag{5} \]
* With respect to the functional \(\varphi\).
To prove Theorem 1, note that Taylor’s formula implies
\[ \Delta(z_{k+1})-\Delta(z_k)=-(1-\rho_k)\{\Delta(z_k)-\Delta(\Gamma_k z_k)+a_k\rho_k\|\tilde v_k\|^2\}, \tag{6} \]
where \(\frac12 m\le a_k\le \frac12 M\). If the process does not converge, then by (4) there exists \(\mu<1\) such that \(\Delta(\Gamma_k z_k)\le \mu\Delta(z_k)\) \((k=0,1,2,\ldots)\). Therefore
\[ \Delta(z_{k+1})-\Delta(z_k)\le -(1-\rho_k)(1-\mu)\Delta(z_k) \qquad (k=0,1,2,\ldots), \tag{7} \]
whence, if (5) is satisfied, convergence follows. The contradiction proves the sufficiency of condition (5). On the other hand,
\[ \|\tilde v_k\|^2\le 8m^{-1}\Delta(z_k), \tag{8} \]
whence
\[ \Delta(z_{k+1})-\Delta(z_k)\ge -(1-\rho_k)(1+4h)\Delta(z_k), \tag{9} \]
where \(h=Mm^{-1}\) is the condition number. From (7) follows the necessity of condition (5).
Theorem 2. Let there exist a constant \(\mu<1\) such that
\[ \Delta(\Gamma_k x)\le \mu\Delta(x)\qquad (k=0,1,2,\ldots). \tag{10} \]
Then, for the linear convergence of the perturbed process* it is necessary and sufficient that
\[ \overline{\lim_{k\to\infty}}\rho_k<1. \tag{11} \]
This result follows immediately from estimates (7), (9). We note that condition (11), as a sufficient condition, can be replaced by the more effective condition
\[ \|v_k\|\le \frac{1-\sqrt{\mu}}{M}\|Fz_k\|\qquad (k=0,1,2,\ldots). \]
Until now we have measured the noise level in terms of relative error. Let us now consider the question of the influence of noise that is small in the sense of absolute error. In this case the relaxational nature of the perturbed process can no longer be assumed.
We shall say that the process \(\{z_k\}\) converges with accuracy up to \(\varepsilon\) if
\[ \overline{\lim_{k\to\infty}}\Delta(z_k)\le \varepsilon. \]
Put
\[ \delta_0(\varepsilon)=\sqrt{\varepsilon/2M}\bigl(1-\sqrt{S(\varepsilon/4)}\bigr),\qquad \delta_1(\varepsilon)=2\sqrt{2\varepsilon/m}. \]
Theorem 3. In order that the perturbed process converge with accuracy up to \(\varepsilon\), it is necessary that
\[ \overline{\lim_{k\to\infty}}\|v_k\|\le \delta_1(\varepsilon), \]
and sufficient that
\[ \overline{\lim_{k\to\infty}}\|v_k\|<\delta_0(\varepsilon). \]
The necessity follows from estimate (8). To prove sufficiency, take such a \(\rho<1\) that
\[ \|v_k\|\le \rho\delta_0(\varepsilon), \tag{12} \]
starting from \(k=k_0\). Then \(\rho_k\) can be estimated. Namely, if \(\Delta(z_k)>\frac14\varepsilon\), then \(\rho_k\le \rho\). Therefore it follows from Theorem 1 that \(\Delta(z_k)\le \varepsilon/4\) for some \(n\ge k_0\). By virtue of (12) and the inequality
\[ \Delta(z_{k+1})\le \Delta(z_k)+\sqrt{2M\Delta(z_k)}\|v_k\|+\frac12 M\|v_k\|^2 \]
* Still under the assumption that it is relaxational.
there is the implication
\[ \Delta(z_k)\leq \varepsilon/4 \Rightarrow \Delta(z_{k+1})\leq \varepsilon . \]
Consequently, \(\Delta(z_k)\leq \varepsilon\) \((k\geq n)\).
Remark. Under condition (10) one may set
\[ \delta_0(\varepsilon)=(1-\sqrt{\mu})\sqrt{2\varepsilon/M}, \qquad \delta_1(\varepsilon)=(1+\sqrt{\mu})\sqrt{2\varepsilon/m}. \]
Thus, the resulting error of the process has exactly the same order as the error of each step.
Corollary 1. If condition (10) is satisfied, then there exist constants \(c_0, c_1\), \((0<c_1<c_0)\), such that
\[ c_1 \varlimsup_{k\to\infty}\|v_k\| \leq \varlimsup_{k\to\infty}\|x_k-x^0\| \leq c_0 \varlimsup_{k\to\infty}\|v_k\|. \]
One may set
\[ c_1=1/(\sqrt{\mu}+1)\sqrt{h}, \qquad c_0=\sqrt{h}/(1-\sqrt{\mu}). \]
Corollary 2. For convergence of the perturbed process it is necessary and sufficient that
\[ \lim_{k\to\infty} v_k=0, \]
The general theorems obtained can be applied to the investigation of the stability of concrete processes. The stability of various concrete processes was studied in works \((^1\text{--}^{10})\).
Kharkov State University
named after A. M. Gorky
Physico-Technical Institute of Low Temperatures
of the Academy of Sciences of the Ukrainian SSR
Kharkov
Received
27 VI 1969
REFERENCES
\(^1\) M. Urabe, J. Sci. Hiros. Univ., A19, No. 3, 479 (1956).
\(^2\) I. M. Dereendyaev, Uch. zap. Permsk. univ., 16, No. 3, 43 (1958).
\(^3\) M. Urabe, J. Sci. Hiros. Univ., A26, No. 2, 77 (1962).
\(^4\) M. A. Krasnosel’skii, Ya. B. Rutitskii, DAN, 141, 785 (1962).
\(^5\) A. I. Zinchenko, Tr. seminara funktsional’n. analiza, Voronezh, 1963.
\(^6\) M. N. Yakovlev, DAN, 156, No. 3, 522 (1964).
\(^7\) E. I. Lin’kov, UMN, 19, No. 4, 227 (1964).
\(^8\) M. N. Yakovlev, Tr. Matem. inst. im. V. A. Steklova AN SSSR, 84, 8 (1965).
\(^9\) M. D. Babich, V. V. Ivanov, Zhurn. vychislit. matem. i matem. fiz., 7, No. 5, 988 (1967).
\(^10\) M. D. Babich, V. V. Ivanov, Ukr. matem. zhurn., 21, No. 7, 3 (1969).