Accelerating Newton-type Methods in the Presence of Critical Solutions

在存在关键解决方案的情况下加速牛顿型方法

• 批准号: 409756759
• 负责人: Professor Dr. Andreas Fischer
• 金额: --
• 依托单位: Faculty of Computational Mathematics and Cybernetics
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/409756759?language=en
• 关键词: Accelerating; Newton; type; Methods; Presence

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.

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