Stochastic Approximation Method for Fixed Point Problems

Affiliation(s)

Department of Mathematics, The Technion-Israel Institute of Technology, Haifa, Israel.

The Abdus Salam International Centre for Theoretical Physics, Trieste, Italy.

Department of Mathematical Sciences, Shawnee State University, Portsmouth, USA.

Department of Mathematics, The Technion-Israel Institute of Technology, Haifa, Israel.

The Abdus Salam International Centre for Theoretical Physics, Trieste, Italy.

Department of Mathematical Sciences, Shawnee State University, Portsmouth, USA.

ABSTRACT

We study iterative processes of stochastic approximation for finding fixed points of weakly contractive and nonexpansive operators in Hilbert spaces under the condition that operators are given with random errors. We prove mean square convergence and convergence almost sure (a.s.) of iterative approximations and establish both asymptotic and nonasymptotic estimates of the convergence rate in degenerate and non-degenerate cases. Previously the stochastic approximation algorithms were studied mainly for optimization problems.

We study iterative processes of stochastic approximation for finding fixed points of weakly contractive and nonexpansive operators in Hilbert spaces under the condition that operators are given with random errors. We prove mean square convergence and convergence almost sure (a.s.) of iterative approximations and establish both asymptotic and nonasymptotic estimates of the convergence rate in degenerate and non-degenerate cases. Previously the stochastic approximation algorithms were studied mainly for optimization problems.

Cite this paper

Y. Alber, C. Chidume and J. Li, "Stochastic Approximation Method for Fixed Point Problems,"*Applied Mathematics*, Vol. 3 No. 12, 2012, pp. 2123-2132. doi: 10.4236/am.2012.312A293.

Y. Alber, C. Chidume and J. Li, "Stochastic Approximation Method for Fixed Point Problems,"

References

[1] M. T. Wasan, “Stochastic Approximation,” Cambridge University Press, Cambridge, 1969.

[2] M. B. Nevelson and R. Z. Hasminsky, “Stochastic Approximation and Recursive Estimation,” AMS Providence, Rhode Island, 1973.

[3] Ya. Alber and S. Shilman, “Nonasymptotic Estimates of the Convergence Rate of Stochastic Iterative Algorithms,” Automation and Remote Control, Vol. 42, 1981, pp. 32-41.

[4] Ya. Alber and S. Shilman, “General Nonasymptotic Estimates of the Convergence Rate of Iterative Stochastic Algorithms,” USSR Computational Mathematics and Mathematical Physics, Vol. 25, No. 2, 1985, pp. 13-20. doi:10.1016/0041-5553(85)90099-0

[5] K. Barty, J.-S. Roy and C. Strugarek, “Hilbert-Valued Perturbed Subgradient Algorithms,” Mathematics of Operation Research, Vol. 32, No. 3, 2007, pp. 551-562. doi:10.1287/moor.1070.0253

[6] X. Chen and H. White, “Asymptotic Properties of Some Projection-Based Robbins-Monro Procedures in a Hilbert Space,” Studies in Nonlinear Dynamics & Econometrics, Vol. 6, No. 1, 2002, pp. 1-53. doi:10.2202/1558-3708.1000

[7] Ya. I. Alber and A. N. Iusem, “Extension of Subgradient Techniques for Nonsmooth Optimization in Banach Spaces,” Set-Valued Analysis, Vol. 9, No. 4, 2001, pp. 315-335. doi:10.1023/A:1012665832688

[8] Ya. Alber, A. Iusem and M. Solodov, “On the Projection Subgradient Method for Nonsmooth Convex Optimization in a Hilbert Space,” Mathematical Programming, Vol. 81, No. 1, 1998, pp. 23-35. doi:10.1007/BF01584842

[9] A. P. Dempster, N. M. Laird and D. B. Rubin, “Maximal Likelihood from Incomplete Data via the EM Algorithm,” Journal of the Royal Statistical Society, Vol. 39, No. 1, 1977, pp. 185-197.

[10] W. Rudin, “Real and Complex Analysis,” McGraw-Hill, New York, 1978.

[11] Ya. I. Alber and S. Guerre-Delabriere, “Principle of Weakly Contractive Maps in Hilbert Spaces,” Operator Theory, Advances and Applications, Vol. 98, 1997, pp. 7-22.

[12] Ya. I. Alber, “Recurrence Relations and Variational Inequalities,” Soviet Mathematics Doklady, Vol. 27, 1983, pp. 511-517.

[13] Ya. Alber, S. Guerre-Delabriere and L. Zelenko, “The Principle of Weakly Contractive Maps in Metric Spaces,” Communications on Applied Nonlinear Analysis, Vol. 5, No. 1, 1998, pp. 45-68.

[14] Ya. I. Alber, “New Results in Fixed Point Theory,” Preprint, Haifa Technion, 2000.

[15] J. Diestel, “The Geometry of Banach Spaces,” Lecture Notes in Mathematics, No. 485, Springer, Berlin, 1975.

[16] T. Figiel, “On the Moduli of Convexity and Smoothness,” Studia Mathematica, Vol. 56, No. 2, 1976, pp. 121-155.

[17] Ya. Alber and I. Ryazantseva, “Nonlinear Ill-Posed Problems of Monotone Type,” Springer, Berlin, 2006.

[18] M. Métivier, “Semimartingales,” De Gruyter, Berlin, 1982. doi:10.1515/9783110845563

[1] M. T. Wasan, “Stochastic Approximation,” Cambridge University Press, Cambridge, 1969.

[2] M. B. Nevelson and R. Z. Hasminsky, “Stochastic Approximation and Recursive Estimation,” AMS Providence, Rhode Island, 1973.

[3] Ya. Alber and S. Shilman, “Nonasymptotic Estimates of the Convergence Rate of Stochastic Iterative Algorithms,” Automation and Remote Control, Vol. 42, 1981, pp. 32-41.

[4] Ya. Alber and S. Shilman, “General Nonasymptotic Estimates of the Convergence Rate of Iterative Stochastic Algorithms,” USSR Computational Mathematics and Mathematical Physics, Vol. 25, No. 2, 1985, pp. 13-20. doi:10.1016/0041-5553(85)90099-0

[5] K. Barty, J.-S. Roy and C. Strugarek, “Hilbert-Valued Perturbed Subgradient Algorithms,” Mathematics of Operation Research, Vol. 32, No. 3, 2007, pp. 551-562. doi:10.1287/moor.1070.0253

[6] X. Chen and H. White, “Asymptotic Properties of Some Projection-Based Robbins-Monro Procedures in a Hilbert Space,” Studies in Nonlinear Dynamics & Econometrics, Vol. 6, No. 1, 2002, pp. 1-53. doi:10.2202/1558-3708.1000

[7] Ya. I. Alber and A. N. Iusem, “Extension of Subgradient Techniques for Nonsmooth Optimization in Banach Spaces,” Set-Valued Analysis, Vol. 9, No. 4, 2001, pp. 315-335. doi:10.1023/A:1012665832688

[8] Ya. Alber, A. Iusem and M. Solodov, “On the Projection Subgradient Method for Nonsmooth Convex Optimization in a Hilbert Space,” Mathematical Programming, Vol. 81, No. 1, 1998, pp. 23-35. doi:10.1007/BF01584842

[9] A. P. Dempster, N. M. Laird and D. B. Rubin, “Maximal Likelihood from Incomplete Data via the EM Algorithm,” Journal of the Royal Statistical Society, Vol. 39, No. 1, 1977, pp. 185-197.

[10] W. Rudin, “Real and Complex Analysis,” McGraw-Hill, New York, 1978.

[11] Ya. I. Alber and S. Guerre-Delabriere, “Principle of Weakly Contractive Maps in Hilbert Spaces,” Operator Theory, Advances and Applications, Vol. 98, 1997, pp. 7-22.

[12] Ya. I. Alber, “Recurrence Relations and Variational Inequalities,” Soviet Mathematics Doklady, Vol. 27, 1983, pp. 511-517.

[13] Ya. Alber, S. Guerre-Delabriere and L. Zelenko, “The Principle of Weakly Contractive Maps in Metric Spaces,” Communications on Applied Nonlinear Analysis, Vol. 5, No. 1, 1998, pp. 45-68.

[14] Ya. I. Alber, “New Results in Fixed Point Theory,” Preprint, Haifa Technion, 2000.

[15] J. Diestel, “The Geometry of Banach Spaces,” Lecture Notes in Mathematics, No. 485, Springer, Berlin, 1975.

[16] T. Figiel, “On the Moduli of Convexity and Smoothness,” Studia Mathematica, Vol. 56, No. 2, 1976, pp. 121-155.

[17] Ya. Alber and I. Ryazantseva, “Nonlinear Ill-Posed Problems of Monotone Type,” Springer, Berlin, 2006.

[18] M. Métivier, “Semimartingales,” De Gruyter, Berlin, 1982. doi:10.1515/9783110845563