Accelerating Newton-type Methods in the Presence of Critical Solutions

牛顿型方法是有效求解非线性方程组及相关问题的核心技术之一。这是由于在适当的假设下，这些方法的快速收敛。目前对这些方法的研究旨在扩大其适用性，以新的或更困难的问题类。这里的一个重要问题是非孤立解的问题。一个局部快速（超线性）收敛速度已被证明为专门设计的牛顿型方法的问题类与非孤立的解决方案，如果一个合适的Lipschitz误差界条件得到满足。在这些方法中有稳定的序列二次规划技术，Levenberg-Marquardt算法，以及最近的LP-Newton方法，然而，众所周知，在存在非孤立解的情况下，Newton型方法有很强的收敛到违反误差界条件的解的趋势。这些解决方案被称为关键。最近几次试图将这种牛顿型方法全球化的尝试面临的主要困难是，它们往往不能将大的吸引域留给临界点。然后，牛顿型方法的快速收敛通常会丢失，并且专门为非孤立解的情况设计的方法的优点也会丢失。因此，该项目的主要目标在于开发和建立新技术，以便在存在临界解的情况下实现快速局部收敛。为了实现这一目标，我们打算解决具体的主要研究目标。对于最优性系统与非唯一的乘数，所产生的约束优化，我们打算开发一种新的技术，以合理的费用，修改所产生的乘数估计，使他们保持足够远离临界。对于具有更一般结构的非线性方程组，我们打算考虑临界解满足一定的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.