TY - JOUR

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

AU - Cai, Shang Rong

AU - Hwang, Feng Nan

N1 - Publisher Copyright:
© 2021 IMACS

PY - 2022/3

Y1 - 2022/3

N2 - 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.

AB - 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.

KW - Curve search

KW - Inexact Newton method

KW - Line search backtracking technique

KW - Nonlinear elimination

UR - http://www.scopus.com/inward/record.url?scp=85120359559&partnerID=8YFLogxK

U2 - 10.1016/j.apnum.2021.11.011

DO - 10.1016/j.apnum.2021.11.011

M3 - 期刊論文

AN - SCOPUS:85120359559

SN - 0168-9274

VL - 173

SP - 79

EP - 93

JO - Applied Numerical Mathematics

JF - Applied Numerical Mathematics

ER -