Global convergence of quasi-Newton methods based on adjoint Broyden updates
type: Item
instance of: scholarly article
title: Global convergence of quasi-Newton methods based on adjoint Broyden updates
zbMATH Open document ID: 1163.65025
author: Sebastian Schlenkrich
author: Andrea Walther
published in: Applied Numerical Mathematics
publication date: 2009-04-15T00:00:00Z
review text: For solving a system of nonlinear equations, the authors propose an iterative quasi-Newton type method. It is known that the Newton method converges quadratically if the Jacobian of the functions from the left hand side of the system is non-singular. However it requires the reapeted evaluation of the whole Jacobian and its factorization or the inverse for each iterate. This computational effort can be reduced by approximating the Jacobian blow-rank updates, for example by projected updates from Broyden's method [see \textit{C. G. Broyden}, Math. Comput. 19, 577--593 (1965; Zbl 0131.13905)]. In this paper the authors propose the nested use of adjoint Broyden updates in combination with monitoring the angle between the quasi-Newton direction and the stepest descent direction. This yields finite convergence after \(n\) steps for affine problems and local \(q\)-superlinear convergence for general nonlinear problems. The local convergence of the quasi-Newton iterations using adjoint Broyden updates is proved. A nested update algorithm is proposed. The basic structure of this algorithm is a quasi-Newton method with adjoint Broyden residual updates. The computational effort of the method is evaluated in terms of function evaluations and linear algebra operations. The nested update algorithm is compared with Newton's method and with Broyden's method. Numerical results are performed in case of three test functions.
reviewed by: Iulian Coroian
Mathematics Subject Classification ID: 65H10
zbMATH DE Number: 5543924
zbMATH Keywords: quasi-Newton methods
zbMATH Keywords: adjoint based updates
zbMATH Keywords: automatic differentiation
zbMATH Keywords: global convergence
zbMATH Keywords: system of nonlinear equations
zbMATH Keywords: Broyden's method
zbMATH Keywords: superlinear convergence
zbMATH Keywords: local convergence
zbMATH Keywords: numerical results
describes a project that uses: CUTEr
describes a project that uses: minpack
describes a project that uses: ADOL-C
describes a project that uses: SQPlab
describes a project that uses: PLCP
describes a project that uses: CUTE
MaRDI profile type: Publication
full work available at URL: j.apnum.2008.05.007
OpenAlex ID: W2009833619
cites work: Triangular factors of modified matrices
cites work: CUTE
cites work: Numerical optimization. Theoretical and practical aspects. Transl. from the French
cites work: A Class of Methods for Solving Nonlinear Simultaneous Equations
cites work: A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods
cites work: Q3915921
cites work: Q4700556
cites work: Q5689624
cites work: The “global” convergence of Broyden-like methods with suitable line search
cites work: Q4954403
cites work: Algorithm 755: ADOL-C
cites work: Optimalr-order of an adjoint Broyden method without the assumption of linearly independent steps
cites work: On constrained optimization by adjoint based quasi-Newton methods
cites work: Q3992442
cites work: Numerical Optimization
cites work: On the local convergence of adjoint Broyden methods
cites work: Q2844221
DOI: 10.1016/J.APNUM.2008.05.007
Recommended article: Local and superlinear convergence for truncated iterated projections methods
Recommended article: A Quasi-Newton Method Employing Direct Secant Updates of Matrix Factorizations
Recommended article: Q4604449
Recommended article: On the local convergence of adjoint Broyden methods
Recommended article: A matrix-free quasi-Newton method for solving large-scale nonlinear systems
Recommended article: Q4285067
Recommended article: A variation of Broyden class methods using Householder adaptive transforms
Recommended article: A new quasi-Newton method based on adjoint Broyden updates for symmetric nonlinear equations
Recommended article: Practical quasi-Newton methods for solving nonlinear systems
Recommended article: On The convergence of the quasi-gauss-newton methods for solving nonlinear systems
description: scientific article; zbMATH DE number 5543924