Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Trust region algorithms and timestep selection

Higham, D.J. (1999) Trust region algorithms and timestep selection. SIAM Journal on Numerical Analysis, 37 (1). pp. 194-210. ISSN 0036-1429

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

Unconstrained optimization problems are closely related to systems of ordinary differential equations (ODEs) with gradient structure. In this work, we prove results that apply to both areas. We analyze the convergence properties of a trust region, or Levenberg--Marquardt, algorithm for optimization. The algorithm may also be regarded as a linearized implicit Euler method with adaptive timestep for gradient ODEs. From the optimization viewpoint, the algorithm is driven directly by the Levenberg--Marquardt parameter rather than the trust region radius. This approach is discussed, for example, in [R. Fletcher, Practical Methods of Optimization, 2nd ed., John Wiley, New York, 1987], but no convergence theory is developed. We give a rigorous error analysis for the algorithm, establishing global convergence and an unusual, extremely rapid, type of superlinear convergence. The precise form of superlinear convergence is exhibited---the ratio of successive displacements from the limit point is bounded above and below by geometrically decreasing sequences. We also show how an inexpensive change to the algorithm leads to quadratic convergence. From the ODE viewpoint, this work contributes to the theory of gradient stability by presenting an algorithm that reproduces the correct global dynamics and gives very rapid local convergence to a stable steady state.

Item type: Article
ID code: 182
Keywords: global convergence, gradientsystem, Levenberg--Marquardt, quadratic convergence, steady state, superlinear convergence, unconstrained optimization, applied mathematics, computer science, Electronic computers. Computer science, Mathematics, Numerical Analysis
Subjects: Science > Mathematics > Electronic computers. Computer science
Science > Mathematics
Department: Faculty of Science > Mathematics and Statistics
Related URLs:
    Depositing user: Ms Sarah Scott
    Date Deposited: 02 Mar 2006
    Last modified: 04 Sep 2014 10:04
    URI: http://strathprints.strath.ac.uk/id/eprint/182

    Actions (login required)

    View Item