Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-22T08:50:54.205Z Has data issue: false hasContentIssue false
  • English
  • Français

The “global” convergence of Broyden-like methods with suitable line search

Published online by Cambridge University Press:  17 February 2009

Anderas Griewank
Anderas Griewank
Affiliation:
Centre for Mathematical Analysis, Australian National University, G.P.O. Box 4, Canberra A.C.T. 2600, Australia.
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Iterative methods for solving a square system of nonlinear equations g(x) = 0 often require that the sum of squares residual γ (x) ≡ ½∥g(x)∥2 be reduced at each step. Since the gradient of γ depends on the Jacobian ∇g, this stabilization strategy is not easily implemented if only approximations Bk to ∇g are available. Therefore most quasi-Newton algorithms either include special updating steps or reset Bk to a divided difference estimate of ∇g whenever no satisfactory progress is made. Here the need for such back-up devices is avoided by a derivative-free line search in the range of g. Assuming that the Bk are generated from an rbitrary B0 by fixed scale updates, we establish superlinear convergence from within any compact level set of γ on which g has a differentiable inverse function g−1.

Type
Research Article
Information
The ANZIAM Journal , Volume 28 , Issue 1 , July 1986 , pp. 75 - 92
Copyright
Copyright © Australian Mathematical Society 1986

References

[1]Al-Baali, M. and Fletcher, R., “An efficient line search for nonlinear least squares”, Numerical Analysis Report NA/78, Univ. of Dundee, 1984.Google Scholar
[2]Allgower, E. and Georg, K., “Simplical and continuation methods for approximating fixed points and solutions to systems of equations”, SIAM Rev. 22 (1980), 28–85.CrossRefGoogle Scholar
[3]Dennis, J. E. and Moré, J. J., “Quasi-Newton methods, motivation and theory”, SIAM Rev. 19 (1977), 46–89.CrossRefGoogle Scholar
[4]Dennis, J. E. and Walker, J. F., “Convergence theorems for least change secant update methods”, SIAM J. Numer. Anal. 18, (1982), 949–987.CrossRefGoogle Scholar
[5]Goldstein, A. A., “On steepest descent”, SIAM J. Control Optim. 3 (1965), 147–151.Google Scholar
[6]Griewank, A., “The local convergence of Broyden's method on Lipschitzian problems in Hilbert spaces”, to appear in SIAM J. Numer. Anal.Google Scholar
[7]Griewank, A. and Toint, Ph. L., “Local convergence analysis for partitioned quasi-Newton updates”, Numer. Math. 39 (1982), 429–448.CrossRefGoogle Scholar
[8]Hart, W. F. and Soul, S. O. W., “Quasi-Newton methods for discretized nonlinear boundary problems”, Journal Institute of Maths. Applications 11 (1973), 351–359.Google Scholar
[9]Keller, H. B., “Numerical solution of two point boundary value problems”, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, 1976.Google Scholar
[10]Lindström, P. and Wedin, P. A., “A new line search algorithm for nonlinear least squares problems”, Report UMINF-82–81, University of Umea, 1981.Google Scholar
[11]Ortega, J. C. and Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970).Google Scholar
[12]Osborne, M. R., “An efficient weak line search with guaranteed termination”, MRC Technical Summary Report # 1870, University of Wisconsin, 1978.Google Scholar
[13]Powell, M. J. D., “A hybrid method for nonlinear equations” in Numerical Methods for Nonlinear Algebraic Equations, (ed. Rabinowitz, P.), (Gordon and Breach, London, 1970).Google Scholar
[14]Schubert, L. K., “Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian”, Math. Comp. 24, (1970), 27–30.CrossRefGoogle Scholar
[15]Warth, W. and Werner, J., “Effiziente Schrittweitenfunktionen bei unrestringierten Opti - mierungsaufgaben”, Computing, 19 (1) (1977), 59–72.CrossRefGoogle Scholar
[16]Wolfe, P., “Convergence conditions for ascent methods”, SIAM Rev. 11 (2) (04 1969).CrossRefGoogle Scholar