Trust Region Algorithms and Timestep Selection
Trust Region Algorithms and Timestep Selection
复制标题
DOI：
10.1137/s0036142998335972
复制
发表时间：
1999-11
期刊：
影响因子：
--
通讯作者：
D. Higham
中科院分区：
文献类型：
--
作者：
D. Higham
无约束优化问题与具有梯度结构的常微分方程（ODE）系统密切相关。在这项工作中，我们证明了适用于这两个领域的结果。我们分析信任域或 Levenberg-Marquardt 优化算法的收敛特性。该算法也可以被视为具有自适应梯度 ODE 时间步长的线性化隐式欧拉方法。从优化的角度来看，该算法直接由 Levenberg--Marquardt 参数驱动，而不是信任区域半径。例如，在 [R. Fletcher，实用优化方法，第二版，John Wiley，纽约，1987 年]，但没有发展出收敛理论。我们对该算法进行了严格的误差分析，建立了全局收敛和一种不寻常的、极其快速的超线性收敛。展示了超线性收敛的精确形式——从极限点开始的连续位移之比以几何递减序列为上下界。我们还展示了对算法的廉价改变如何导致二次收敛。从 ODE 的角度来看，这项工作通过提出一种算法来重现正确的全局动态并提供非常快速的局部收敛到稳定的稳态，从而对梯度稳定性理论做出了贡献。
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.