A Globally Convergent Inexact Newton Method for Systems of Monotone Equations
A Globally Convergent Inexact Newton Method for Systems of Monotone Equations
复制标题
DOI：
10.1007/978-1-4757-6388-1_18
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
M. Solodov;B. F. Svaiter
中科院分区：
文献类型：
--
作者：
M. Solodov;B. F. Svaiter
我们提出了一个算法求解系统的单调方程，结合牛顿，邻近点，投影方法。该算法的一个重要性质是整个迭代序列总是全局收敛到系统的解，而无需任何额外的正则性假设。此外，在标准假设下，局部超线性收敛速度。与牛顿方法的经典全局化策略相反，在计算步长时，我们不使用旨在降低某些价值函数值的线性插值。相反，在近似牛顿方向上的线性插值被用来构造一个适当的超平面，该超平面将当前的解集与解集分开。这一步之后是将当前矩阵投影到这个超平面上，这确保了算法的全局收敛。我们的方法的每次迭代的计算成本是相同的数量级的经典阻尼牛顿法。关键的优点是，我们的方法是真正的全球收敛。特别是，它不能被困在价值函数的稳定点。所提出的算法的动机是在[25]中提出的混合投影-邻近点方法。
We propose an algorithm for solving systems of monotone equations which combines Newton, proximal point, and projection methodologies. An important property of the algorithm is that the whole sequence of iterates is always globally convergent to a solution of the system without any additional regularity assumptions. Moreover, under standard assumptions the local superlinear rate of convergence is achieved. As opposed to classical globalization strategies for Newton methods, for computing the stepsize we do not use linesearch aimed at decreasing the value of some merit function. Instead, linesearch in the approximate Newton direction is used to construct an appropriate hyperplane which separates the current iterate from the solution set. This step is followed by projecting the current iterate onto this hyperplane, which ensures global convergence of the algorithm. Computational cost of each iteration of our method is of the same order as that of the classical damped Newton method. The crucial advantage is that our method is truly globally convergent. In particular, it cannot get trapped in a stationary point of a merit function. The presented algorithm is motivated by the hybrid projection-proximal point method proposed in [25].