On the local convergence of adjoint Broyden methods

• 成果类型: Article
• 署名作者: Schlenkrich, Sebastian; Griewank, Andreas; Walther, Andrea
• 署名单位: Technische Universitat Dresden; Humboldt University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-008-0232-y
• 发表日期: 2010
• 页码: 221-247
• 关键词: quasi-newton methods; algorithm; optimization

摘要

The numerical solution of nonlinear equation systems is often achieved by so-called quasi-Newton methods. They preserve the rapid local convergence of Newton's method at a significantly reduced cost per step by successively approximating the system Jacobian though low-rank updates. We analyze two variants of the recently proposed adjoint Broyden update, which for the first time combines the classical least change property with heredity on affine systems. However, the new update does require, the evaluation of so-called adjoint vectors, namely products of the transposed Jacobian with certain dual direction vectors. The resulting quasi-Newton method is linear contravariant in the sense of Deuflhard (Newton methods for nonlinear equations. Springer, Heidelberg, 2006) and it is shown here to be locally and q-superlinearly convergent. Our numerical results on a range of test problems demonstrate that the new method usually outperforms Newton's and Broyden's method in terms of runtime and iterations count, respectively.