August 2017, 11(4): 703-720. doi: 10.3934/ipi.2017033

Convergence of the gradient method for ill-posed problems

Industrial Mathematics Institute, Johannes Kepler University Linz, Altenbergerstrasse 69,4040 Linz, Austria

Received  June 2016 Revised  May 2017 Published  June 2017

We study the convergence of the gradient descent method for solving ill-posed problems where the solution is characterized as a global minimum of a differentiable functional in a Hilbert space. The classical least-squares functional for nonlinear operator equations is a special instance of this framework, and the gradient method then reduces to Landweber iteration. The main result of this article is a proof of weak and strong convergence under new nonlinearity conditions that generalize the classical tangential cone conditions.

Citation: Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033
References:
[1]

K. J. Arrow and A. C. Enthoven, Quasi-concave programming, Econometrica, 29 (1961), 779-800. doi: 10.2307/1911819.

[2]

M. Avriel, W. E. Diewert, S. Schaible and I. Zang, Generalized Concavity, vol. 63 of Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898719437.ch1.

[3]

A. Bakushinsky and A. Goncharsky, Ill-posed Problems: Theory and Applications, vol. 301 of Mathematics and its Applications, Kluwer Academic Publishers Group, Dordrecht, 1994. doi: 10.1007/978-94-011-1026-6.

[4]

A. B. Bakushinsky and M. Y. Kokurin, Iterative Methods for Approximate Solution of Inverse Problems, vol. 577 of Mathematics and Its Applications (New York), Springer, Dordrecht, 2004.

[5]

A. Bakushinsky and A. Smirnova, A posteriori stopping rule for regularized fixed point iterations, Nonlinear Anal., 64 (2006), 1255-1261. doi: 10.1016/j.na.2005.06.031.

[6]

A. Bakushinsky and A. Smirnova, Iterative regularization and generalized discrepancy principle for monotone operator equations, Numer. Funct. Anal. Optim., 28 (2007), 13-25. doi: 10.1080/01630560701190315.

[7]

A. B. Bakushinsky, M. Y. Kokurin and A. Smirnova, Iterative Methods for Ill-Posed Problems, vol. 54 of Inverse and Ill-posed Problems Series, Walter de Gruyter GmbH & Co. KG, Berlin, 2011.

[8]

F. E. Browder and W. V. Petryshyn, Construction of fixed points of nonlinear mappings in Hilbert space, J. Math. Anal. Appl., 20 (1967), 197-228. doi: 10.1016/0022-247X(67)90085-6.

[9]

A. -P. Calderón, On an inverse boundary value problem, in Seminar on Numerical Analysis and its Applications to Continuum Physics (Rio de Janeiro, 1980), Soc. Brasil. Mat., Rio de Janeiro, 1980, 65-73.

[10]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, vol. 375 of Mathematics and its Applications, Kluwer, Dordrecht, 1996. doi: 10.1007/978-94-009-1740-8.

[11]

M. HaltmeierA. Leitão and O. Scherzer, Kaczmarz methods for regularizing nonlinear ill-posed equations. Ⅰ. Convergence analysis, Inverse Probl. Imaging, 1 (2007), 289-298. doi: 10.3934/ipi.2007.1.289.

[12]

M. Hanke, A regularizing Levenberg-Marquardt scheme, with applications to inverse groundwater filtration problems, Inverse Problems, 13 (1997), 79-95. doi: 10.1088/0266-5611/13/1/007.

[13]

M. HankeA. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems, Numer. Math., 72 (1995), 21-37. doi: 10.1007/s002110050158.

[14]

T. Hein and K. S. Kazimierski, Accelerated Landweber iteration in Banach spaces Inverse Problems, 26 (2002), Art. 055002, 17 pages. doi: 10.1088/0266-5611/26/5/055002.

[15]

N. S. Hoang and A. G. Ramm, Dynamical systems gradient method for solving nonlinear equations with monotone operators, Acta Appl. Math., 106 (2009), 473-499. doi: 10.1007/s10440-008-9308-1.

[16]

N. S. Hoang and A. G. Ramm, The dynamical systems method for solving nonlinear equations with monotone operators, Asian-Eur. J. Math., 3 (2010), 57-105. doi: 10.1142/S1793557110000064.

[17]

Q. Jin, A general convergence analysis of some Newton-type methods for nonlinear inverse problems, SIAM J. Numer. Anal., 49 (2011), 549-573. doi: 10.1137/100804231.

[18]

B. Kaltenbacher, Some Newton-type methods for the regularization of nonlinear ill-posed problems, Inverse Problems, 13 (1997), 729-753. doi: 10.1088/0266-5611/13/3/012.

[19]

B. Kaltenbacher, A. Neubauer and O. Scherzer, Iterative Regularization Methods for Nonlinear Ill-Posed Problems, vol. 6 of Radon Series on Computational and Applied Mathematics, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. doi: 10.1515/9783110208276.

[20]

A. Neubauer, On Landweber iteration for nonlinear ill-posed problems in Hilbert scales, Numer. Math., 85 (2000), 309-328. doi: 10.1007/s002110050487.

[21]

A. Neubauer, Some generalizations for Landweber iteration for nonlinear ill-posed problems, Journal Inverse and Ill-posed Problems, 24 (2016), 393-406. doi: 10.1515/jiip-2015-0086.

[22]

S. S. PereverzyevR. Pinnau and N. Siedow, Regularized fixed-point iterations for nonlinear inverse problems, Inverse Problems, 22 (2006), 1-22. doi: 10.1088/0266-5611/22/1/001.

[23]

A. G. Ramm, Dynamical systems method for ill-posed equations with monotone operators, Commun. Nonlinear Sci. Numer. Simul., 10 (2005), 935-940. doi: 10.1016/j.cnsns.2003.07.002.

[24]

O. Scherzer, Convergence criteria of iterative methods based on Landweber iteration for solving nonlinear problems, J. Math. Anal. Appl., 194 (1995), 911-933. doi: 10.1006/jmaa.1995.1335.

[25]

T. Schuster, B. Kaltenbacher, B. Hofmann and K. S. Kazimierski, Regularization Methods in Banach Spaces, vol. 10 of Radon Series on Computational and Applied Mathematics, Walter de Gruyter GmbH & Co. KG, Berlin, 2012. doi: 10.1515/9783110255720.

[26]

V. V. Vasin, Convergence of gradient-type methods for nonlinear equations, Dokl. Akad. Nauk, 359 (1998), 7-9.

show all references

References:
[1]

K. J. Arrow and A. C. Enthoven, Quasi-concave programming, Econometrica, 29 (1961), 779-800. doi: 10.2307/1911819.

[2]

M. Avriel, W. E. Diewert, S. Schaible and I. Zang, Generalized Concavity, vol. 63 of Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898719437.ch1.

[3]

A. Bakushinsky and A. Goncharsky, Ill-posed Problems: Theory and Applications, vol. 301 of Mathematics and its Applications, Kluwer Academic Publishers Group, Dordrecht, 1994. doi: 10.1007/978-94-011-1026-6.

[4]

A. B. Bakushinsky and M. Y. Kokurin, Iterative Methods for Approximate Solution of Inverse Problems, vol. 577 of Mathematics and Its Applications (New York), Springer, Dordrecht, 2004.

[5]

A. Bakushinsky and A. Smirnova, A posteriori stopping rule for regularized fixed point iterations, Nonlinear Anal., 64 (2006), 1255-1261. doi: 10.1016/j.na.2005.06.031.

[6]

A. Bakushinsky and A. Smirnova, Iterative regularization and generalized discrepancy principle for monotone operator equations, Numer. Funct. Anal. Optim., 28 (2007), 13-25. doi: 10.1080/01630560701190315.

[7]

A. B. Bakushinsky, M. Y. Kokurin and A. Smirnova, Iterative Methods for Ill-Posed Problems, vol. 54 of Inverse and Ill-posed Problems Series, Walter de Gruyter GmbH & Co. KG, Berlin, 2011.

[8]

F. E. Browder and W. V. Petryshyn, Construction of fixed points of nonlinear mappings in Hilbert space, J. Math. Anal. Appl., 20 (1967), 197-228. doi: 10.1016/0022-247X(67)90085-6.

[9]

A. -P. Calderón, On an inverse boundary value problem, in Seminar on Numerical Analysis and its Applications to Continuum Physics (Rio de Janeiro, 1980), Soc. Brasil. Mat., Rio de Janeiro, 1980, 65-73.

[10]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, vol. 375 of Mathematics and its Applications, Kluwer, Dordrecht, 1996. doi: 10.1007/978-94-009-1740-8.

[11]

M. HaltmeierA. Leitão and O. Scherzer, Kaczmarz methods for regularizing nonlinear ill-posed equations. Ⅰ. Convergence analysis, Inverse Probl. Imaging, 1 (2007), 289-298. doi: 10.3934/ipi.2007.1.289.

[12]

M. Hanke, A regularizing Levenberg-Marquardt scheme, with applications to inverse groundwater filtration problems, Inverse Problems, 13 (1997), 79-95. doi: 10.1088/0266-5611/13/1/007.

[13]

M. HankeA. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems, Numer. Math., 72 (1995), 21-37. doi: 10.1007/s002110050158.

[14]

T. Hein and K. S. Kazimierski, Accelerated Landweber iteration in Banach spaces Inverse Problems, 26 (2002), Art. 055002, 17 pages. doi: 10.1088/0266-5611/26/5/055002.

[15]

N. S. Hoang and A. G. Ramm, Dynamical systems gradient method for solving nonlinear equations with monotone operators, Acta Appl. Math., 106 (2009), 473-499. doi: 10.1007/s10440-008-9308-1.

[16]

N. S. Hoang and A. G. Ramm, The dynamical systems method for solving nonlinear equations with monotone operators, Asian-Eur. J. Math., 3 (2010), 57-105. doi: 10.1142/S1793557110000064.

[17]

Q. Jin, A general convergence analysis of some Newton-type methods for nonlinear inverse problems, SIAM J. Numer. Anal., 49 (2011), 549-573. doi: 10.1137/100804231.

[18]

B. Kaltenbacher, Some Newton-type methods for the regularization of nonlinear ill-posed problems, Inverse Problems, 13 (1997), 729-753. doi: 10.1088/0266-5611/13/3/012.

[19]

B. Kaltenbacher, A. Neubauer and O. Scherzer, Iterative Regularization Methods for Nonlinear Ill-Posed Problems, vol. 6 of Radon Series on Computational and Applied Mathematics, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. doi: 10.1515/9783110208276.

[20]

A. Neubauer, On Landweber iteration for nonlinear ill-posed problems in Hilbert scales, Numer. Math., 85 (2000), 309-328. doi: 10.1007/s002110050487.

[21]

A. Neubauer, Some generalizations for Landweber iteration for nonlinear ill-posed problems, Journal Inverse and Ill-posed Problems, 24 (2016), 393-406. doi: 10.1515/jiip-2015-0086.

[22]

S. S. PereverzyevR. Pinnau and N. Siedow, Regularized fixed-point iterations for nonlinear inverse problems, Inverse Problems, 22 (2006), 1-22. doi: 10.1088/0266-5611/22/1/001.

[23]

A. G. Ramm, Dynamical systems method for ill-posed equations with monotone operators, Commun. Nonlinear Sci. Numer. Simul., 10 (2005), 935-940. doi: 10.1016/j.cnsns.2003.07.002.

[24]

O. Scherzer, Convergence criteria of iterative methods based on Landweber iteration for solving nonlinear problems, J. Math. Anal. Appl., 194 (1995), 911-933. doi: 10.1006/jmaa.1995.1335.

[25]

T. Schuster, B. Kaltenbacher, B. Hofmann and K. S. Kazimierski, Regularization Methods in Banach Spaces, vol. 10 of Radon Series on Computational and Applied Mathematics, Walter de Gruyter GmbH & Co. KG, Berlin, 2012. doi: 10.1515/9783110255720.

[26]

V. V. Vasin, Convergence of gradient-type methods for nonlinear equations, Dokl. Akad. Nauk, 359 (1998), 7-9.

[1]

Plamen Stefanov, Yang Yang. Multiwave tomography with reflectors: Landweber's iteration. Inverse Problems & Imaging, 2017, 11 (2) : 373-401. doi: 10.3934/ipi.2017018

[2]

David Maxwell. Kozlov-Maz'ya iteration as a form of Landweber iteration. Inverse Problems & Imaging, 2014, 8 (2) : 537-560. doi: 10.3934/ipi.2014.8.537

[3]

Kenrick Bingham, Yaroslav Kurylev, Matti Lassas, Samuli Siltanen. Iterative time-reversal control for inverse problems. Inverse Problems & Imaging, 2008, 2 (1) : 63-81. doi: 10.3934/ipi.2008.2.63

[4]

Gabriel Peyré, Sébastien Bougleux, Laurent Cohen. Non-local regularization of inverse problems. Inverse Problems & Imaging, 2011, 5 (2) : 511-530. doi: 10.3934/ipi.2011.5.511

[5]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965

[6]

Barbara Kaltenbacher, Ivan Tomba. Enhanced choice of the parameters in an iteratively regularized Newton-Landweber iteration in Banach space. Conference Publications, 2015, 2015 (special) : 686-695. doi: 10.3934/proc.2015.0686

[7]

Bernadette N. Hahn. Dynamic linear inverse problems with moderate movements of the object: Ill-posedness and regularization. Inverse Problems & Imaging, 2015, 9 (2) : 395-413. doi: 10.3934/ipi.2015.9.395

[8]

Thorsten Hohage, Mihaela Pricop. Nonlinear Tikhonov regularization in Hilbert scales for inverse boundary value problems with random noise. Inverse Problems & Imaging, 2008, 2 (2) : 271-290. doi: 10.3934/ipi.2008.2.271

[9]

Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems & Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171

[10]

Luca Rondi. On the regularization of the inverse conductivity problem with discontinuous conductivities. Inverse Problems & Imaging, 2008, 2 (3) : 397-409. doi: 10.3934/ipi.2008.2.397

[11]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171

[12]

Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627

[13]

Johnathan M. Bardsley. A theoretical framework for the regularization of Poisson likelihood estimation problems. Inverse Problems & Imaging, 2010, 4 (1) : 11-17. doi: 10.3934/ipi.2010.4.11

[14]

Colin Guillarmou, Antônio Sá Barreto. Inverse problems for Einstein manifolds. Inverse Problems & Imaging, 2009, 3 (1) : 1-15. doi: 10.3934/ipi.2009.3.1

[15]

Sergei Avdonin, Pavel Kurasov. Inverse problems for quantum trees. Inverse Problems & Imaging, 2008, 2 (1) : 1-21. doi: 10.3934/ipi.2008.2.1

[16]

Maciej Zworski. A remark on inverse problems for resonances. Inverse Problems & Imaging, 2007, 1 (1) : 225-227. doi: 10.3934/ipi.2007.1.225

[17]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79

[18]

Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141

[19]

D. Novikov and S. Yakovenko. Tangential Hilbert problem for perturbations of hyperelliptic Hamiltonian systems. Electronic Research Announcements, 1999, 5: 55-65.

[20]

Janne M.J. Huttunen, J. P. Kaipio. Approximation errors in nonstationary inverse problems. Inverse Problems & Imaging, 2007, 1 (1) : 77-93. doi: 10.3934/ipi.2007.1.77

2017 Impact Factor: 1.465

Metrics

  • PDF downloads (6)
  • HTML views (23)
  • Cited by (1)

Other articles
by authors

[Back to Top]