<p>We survey the perturbed Newton method framework for smooth nonlinear equations, allowing sharp characterization of local convergence and rate of convergence to singular solutions possessing some 2-regularity properties. The framework covers a wide range of Newton-type methods in a unified manner, including, along with the basic Newton method, the Levenberg-Marquardt method and the LP-Newton method, among the others. We also discuss a linesearch-based globalization of convergence of these methods, and their possible acceleration by means of extrapolation, with asymptotic acceptance of the full step playing the key role for acceleration. These constructions and results are further extended to more general problem settings, such as constrained equations and piecewise smooth equations, allowing for applications to various reformulations of complementarity problems. The 2-regularity property in question is strongly related to the concept of critical solutions of nonlinear equations, which is further naturally tailored to the error bound property (or rather lack of it), and to stability of solutions subject to wide classes of perturbations. Finally, we trace the link of critical solutions of equations to critical Lagrange multipliers in optimization, which was the origin of these developments. Critical Lagrange multipliers have a major effect on behavior of the SQP methods, stabilized SQP, and multiplier (Augmented Lagrangian) methods for optimization and variational problems.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A General Perturbed Newtonian Framework and Critical Solutions of Nonlinear Equations

  • Alexey Izmailov,
  • Mikhail Solodov

摘要

We survey the perturbed Newton method framework for smooth nonlinear equations, allowing sharp characterization of local convergence and rate of convergence to singular solutions possessing some 2-regularity properties. The framework covers a wide range of Newton-type methods in a unified manner, including, along with the basic Newton method, the Levenberg-Marquardt method and the LP-Newton method, among the others. We also discuss a linesearch-based globalization of convergence of these methods, and their possible acceleration by means of extrapolation, with asymptotic acceptance of the full step playing the key role for acceleration. These constructions and results are further extended to more general problem settings, such as constrained equations and piecewise smooth equations, allowing for applications to various reformulations of complementarity problems. The 2-regularity property in question is strongly related to the concept of critical solutions of nonlinear equations, which is further naturally tailored to the error bound property (or rather lack of it), and to stability of solutions subject to wide classes of perturbations. Finally, we trace the link of critical solutions of equations to critical Lagrange multipliers in optimization, which was the origin of these developments. Critical Lagrange multipliers have a major effect on behavior of the SQP methods, stabilized SQP, and multiplier (Augmented Lagrangian) methods for optimization and variational problems.