Accelerating Newton-type Methods in the Presence of Critical Solutions

牛顿型方法是有效求解非线性方程组及其相关问题的核心技术之一。这是因为在适当的假设下，这些方法能够快速收敛。目前对这些方法的研究旨在将它们的适用性扩展到新的或更难的问题类。这里的一个重要问题是非孤立解的问题。证明了当满足适当的Lipschitzian误差界条件时，特殊设计的牛顿型方法对具有非孤立解的问题类具有局部快速(超线性)收敛速度。在这些方法中有稳定化的序列二次规划技术、Levenberg-MarQuardt算法和最近的LP-牛顿法，但是众所周知，在存在非孤立解的情况下，牛顿型方法有很强的收敛到违反这种误差界条件的解的趋势。这些解决方案称为关键解决方案。最近几次将这种牛顿型方法全球化的尝试都面临着一个主要困难，那就是它们往往不能给临界点留下大的吸引域。因此，该项目的主要目标在于开发和建立新的技术，以在存在临界解的情况下实现快速局部收敛。为了实现这一目标，我们打算解决具体的主要研究目标。对于由约束优化产生的具有非唯一乘子的最优系统，我们打算发展一种新的技术，以合理的代价修改生成的乘子估计，使它们足够远离临界点。对于具有更一般结构的非线性方程组，我们打算考虑满足一定2-正则性条件的临界解。这一温和的条件强制了一种结构化的收敛模式，特别是将允许我们局部地识别发生超线性收敛恶化的子空间。通常，这个子空间的维度很小。我们打算利用这一点来构建新的算法技术，目标是快速局部收敛。为了支持前面的目标，我们的目标是开发工具，以确保融合到关键解决方案。与我们的主要目标的影响具有很强相关性的一个研究目标是将本地技术嵌入到相关的全球化框架中，从而产生可实现的算法。在此基础上，对新技术和新算法进行了计算研究和比较。

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.