On the effect of nonlinearity and Jacobian initialization on the convergence of the generalized Broyden quasi-Newton method

Toon Demeester, Nicolas Delaissé, E. Harald van Brummelen, Rob Haelterman, Joris Degroote

Research output: Contribution to journalArticlepeer-review

Abstract

This article investigates two aspects of the generalized Broyden quasi-Newton method that have a major impact on its convergence: the initial approximation of the Jacobian and the presence of nonlinearities in the secant conditions. After reformulating the common representation of generalized Broyden, a straightforward interpretation is given. This leads to a natural extension of the method in which an application-dependent physics-based surrogate model is used as initial approximation of the (inverse) Jacobian. A carefully chosen surrogate has the potential to greatly reduce the required number of iterations. The behavior of generalized Broyden depends strongly on the parameter that determines how many secant conditions are satisfied by the Jacobian approximation. Respecting all secant conditions reduces it to Anderson acceleration; a single one to Broyden's original method. An analysis demonstrates that these two variants behave very differently when nonlinearities are present in the secant conditions: they are ignored by Broyden, but can destabilize Anderson. On the other hand, the analysis shows that Broyden tends to neglect small linear information, possibly reducing convergence speed. To mitigate stability problems with Anderson acceleration, a practical method to detect and remove nonlinear secant information is introduced next. Finally, we solve a steady free-surface-flow problem using several generalized Broyden variants, testing the influence of the surrogate, the nonlinearities and the combination thereof. The results agree with the theoretical predictions, showing large differences in convergence behavior. Furthermore, the proposed method effectively negates the problems related to nonlinearities in this case.

Original languageEnglish
Pages (from-to)4054-4072
Number of pages19
JournalInternational Journal for Numerical Methods in Engineering
Volume123
Issue number17
DOIs
Publication statusPublished - 15 Sept 2022

Keywords

  • Anderson acceleration
  • Broyden's method
  • free-surface flow
  • quasi-Newton
  • surrogate model

Fingerprint

Dive into the research topics of 'On the effect of nonlinearity and Jacobian initialization on the convergence of the generalized Broyden quasi-Newton method'. Together they form a unique fingerprint.

Cite this