Accelerating Newton-type Methods in the Presence of Critical Solutions

点击翻译按钮获取中文摘要

Newton-type methods are one of the central techniques for the efficient solution of systems of nonlinear equations and of related problems. This is due to the fast convergence of these methods under appropriate assumptions. Current research on these methods aims at broadening their applicability to new or more difficult problem classes. An important issue here are problems with nonisolated solutions. A local fast (superlinear) convergence rate has been shown for specially designed Newton-type methods for problem classes with nonisolated solutions if a suitable Lipschitzian error bound condition is satisfied. Among these methods are stabilized sequential quadratic programming techniques, Levenberg-Marquardt algorithms, and the recent LP-Newton method.However, it is well-recognized that, in the presence of nonisolated solutions, Newton-type methods have a strong tendency to converge to solutions at which such an error bound condition is violated. These solutions are called critical. Several recent attempts to globalize such Newton-type methods face the principal difficulty that they often cannot leave large domains of attraction to critical points. Then, the fast convergence of the Newton-type methods is usually lost, and the advantages of methods specially designed for the case of nonisolated solutions get lost as well.Therefore, the main goal of the project consists in the development and foundation of new techniques to achieve fast local convergence in spite of the presence of critical solutions. To reach this goal we intend to tackle specific main research objectives. For optimality systems with nonunique multipliers, arising from constrained optimization, we intend to develop a new technique that, with a reasonable expense, modifies the generated multiplier estimates so that they are staying sufficiently far away from criticality. For systems of nonlinear equations with a more general structure, we intend to consider critical solutions satisfying a certain 2-regularity condition. This mild condition enforces a structured convergence pattern and, in particular, shall allow us to locally identify the subspace where the deterioration of the superlinear convergence takes place. Usually this subspace has a small dimension. We intend to exploit this to construct new algorithmic techniques with the aim of fast local convergence. To support the previous goals we aim at developing tools which certify convergence to a critical solution. A research objective with strong relevance for the impact of our main goal is to embed the local techniques into relevant globalization frameworks, resulting in implementable algorithms. Together with this, a computational study and comparison of the new techniques and algorithms is intended.