A hybrid-line-and-curve search globalization technique for inexact Newton methods

The backtracking line search (LS) is one of the most commonly used techniques for enhancing the robustness of Newton-type methods. The Newton method consists of two key steps: search and update. LS tries to find a decreasing-most updated point along with Newton's search direction with an appropriate damping factor from the current approximation. The determination of Newton's search direction relies only on current information. When Newton's search direction is a weak descent direction, the damping factor determined by LS can be unacceptably small, which often happens for the numerical solution of large, sparse systems of equations with strong local nonlinearity. As a result, the solution process falls into the vicious cycle between no update and almost the same search direction. The intermediate solution is trapped within the same region without any progress. This work proposes a new globalization strategy, namely, the hybrid line and curve search (HLCS) technique for Newton-type methods to resolve their potential failure problems when line-search is used. If the classical line search fails, we activate the curve search phase. In that case, we first decompose the solution space into two orthogonal subspaces based on the predicted value obtained from Newton's search direction, referred to “good” and “bad” subspaces. The bad one corresponds to the components causing the violation of the sufficient decrease condition. Next, we project the original predicted value on the good subspace and then perform the nonlinear elimination process to obtain the corrected solution on the bad subspace. Hopefully, the new update can satisfy the sufficient decrease condition to enhance the convergence of inexact Newton. As proof of concept, we present three numerical examples to illustrate the effectiveness of our proposed inexact Newton-HLCS approach.