Inexact Perturbed Newton Methods and Applications to a Class of Krylov Solvers

Inexact Newton methods are variant of the Newton method in which each step satisfies only approximately the linear system (Ref. 1). The local convergence theory given by the authors of Ref. 1 and most of the results based on it consider the error terms as being provided only by the fact that the linear systems are not solved exactly. The few existing results for the general case (when some perturbed linear systems are considered, which in turn are not solved exactly) do not offer explicit formulas in terms of the perturbations and residuals. We extend this local convergence theory to the general case, characterizing the rate of convergence in terms of the perturbations and residuals.The Newton iterations are then analyzed when, at each step, an approximate solution of the linear system is determined by the following Krylov solvers based on backward error minimization properties: GMRES, GMBACK, MINPERT. We obtain results concerning the following topics: monotone properties of the errors in these Newton–Krylov iterates when the initial guess is taken 0 in the Krylov algorithms; control of the convergence orders of the Newton–Krylov iterations by the magnitude of the backward errors of the approximate steps; similarities of the asymptotical behavior of GMRES and MINPERT when used in a converging Newton method. At the end of the paper, the theoretical results are verified on some numerical examples.     

A perturbed version of an inexact generalized Newton method for solving nonsmooth equations

In this paper, we present the combination of the inexact Newton method and the generalized Newton method for solving nonsmooth equations F(x)?=?0, characterizing the local convergence in terms of the perturbations and residuals. We assume that both iteration matrices taken from the B-differential and vectors F(x ^(k)) are perturbed at each step. Some results are motivated by the approach of C?tina? regarding to smooth equations. We study the conditions, which determine admissible magnitude of perturbations to preserve the convergence of method. Finally, the utility of these results is considered based on some variant of the perturbed inexact generalized Newton method for solving some general optimization problems.     

On the semilocal convergence of inexact Newton methods in Banach spaces

We provide two types of semilocal convergence theorems for approximating a solution of an equation in a Banach space setting using an inexact Newton method [I.K. Argyros, Relation between forcing sequences and inexact Newton iterates in Banach spaces, Computing 63 (2) (1999) 134–144; I.K. Argyros, A new convergence theorem for the inexact Newton method based on assumptions involving the second Fréchet-derivative, Comput. Appl. Math. 37 (7) (1999) 109–115; I.K. Argyros, Forcing sequences and inexact Newton iterates in Banach space, Appl. Math. Lett. 13 (1) (2000) 77–80; I.K. Argyros, Local convergence of inexact Newton-like iterative methods and applications, Comput. Math. Appl. 39 (2000) 69–75; I.K. Argyros, Computational Theory of Iterative Methods, in: C.K. Chui, L. Wuytack (Eds.), in: Studies in Computational Mathematics, vol. 15, Elsevier Publ. Co., New York, USA, 2007; X. Guo, On semilocal convergence of inexact Newton methods, J. Comput. Math. 25 (2) (2007) 231–242]. By using more precise majorizing sequences than before [X. Guo, On semilocal convergence of inexact Newton methods, J. Comput. Math. 25 (2) (2007) 231–242; Z.D. Huang, On the convergence of inexact Newton method, J. Zheijiang University, Nat. Sci. Ed. 30 (4) (2003) 393–396; L.V. Kantorovich, G.P. Akilov, Functional Analysis, Pergamon Press, Oxford, 1982; X.H. Wang, Convergence on the iteration of Halley family in weak condition, Chinese Sci. Bull. 42 (7) (1997) 552–555; T.J. Ypma, Local convergence of inexact Newton methods, SIAM J. Numer. Anal. 21 (3) (1984) 583–590], we provide (under the same computational cost) under the same or weaker hypotheses: finer error bounds on the distances involved; an at least as precise information on the location of the solution. Moreover if the splitting method is used, we show that a smaller number of inner/outer iterations can be obtained.     

A smoothing inexact Newton method for nonlinear complementarity problems

In this article, we propose a new smoothing inexact Newton algorithm for solving nonlinear complementarity problems (NCP) base on the smoothed Fischer-Burmeister function. In each iteration, the corresponding linear system is solved only approximately. The global convergence and local superlinear convergence are established without strict complementarity assumption at the NCP solution. Preliminary numerical results indicate that the method is effective for large-scale NCP.     

Convergence behaviour of inexact Newton methods

In this paper we investigate local convergence properties of inexact Newton and Newton-like methods for systems of nonlinear equations. Processes with modified relative residual control are considered, and new sufficient conditions for linear convergence in an arbitrary vector norm are provided. For a special case the results are affine invariant.

     

On the convergence of inexact Newton methods for discrete-time algebraic Riccati equations

In this paper, we present a convergence analysis of the inexact Newton method for solving Discrete-time algebraic Riccati equations (DAREs) for large and sparse systems. The inexact Newton method requires, at each iteration, the solution of a symmetric Stein matrix equation. These linear matrix equations are solved approximatively by the alternating directions implicit (ADI) or Smith?s methods. We give some new matrix identities that will allow us to derive new theoretical convergence results for the obtained inexact Newton sequences. We show that under some necessary conditions the approximate solutions satisfy some desired properties such as the d-stability. The theoretical results developed in this paper are an extension to the discrete case of the analysis performed by Feitzinger et al. (2009) [8] for the continuous-time algebraic Riccati equations. In the last section, we give some numerical experiments.     

The relationship between the models of perturbed Newton iterations,with applications

The quasi-Newton method and the inexact Newton method are classical models of Newton iterates which take into account certain error terms. We have recently introduced the inexact perturbed Newton method, which takes into account all the possible sources of perturbations. We show that these models are in fact equivalent, in the sense that each one may be used to characterize the high convergence orders of the other two. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A kantorovich-type theorem for inexact newton methods

Under Kantorovich-type assumptions, a general convergence theorem for inexact Newton methods (i.e., iterative procedures in which the Newton equations are solved approximately) is given. The results cover several situations already considered in the literature.     

Affine invariant local convergence theorems for inexact Newton-like methods

Affine invariant sufficient conditions are given for two local convergence theorems involving inexact Newton-like methods. The first uses conditions on the first Fréchet-derivative whereas the second theorem employs hypotheses on the second. Radius of convergence as well as rate of convergence results are derived. Results involving superlinear convergence and known to be true for inexact Newton methods are extended here. Moreover, we show that under hypotheses on the second Fréchet-derivative our radius of convergence is larger than the corresponding one in [10]. This allows a wider choice for the initial guess. A numerical example is also provided to show that our radius of convergence is larger than the one in [10].     

Affine scaling inexact generalized Newton algorithm with interior backtracking technique for solving bound-constrained semismooth equations

We develop and analyze an affine scaling inexact generalized Newton algorithm in association with nonmonotone interior backtracking line technique for solving systems of semismooth equations subject to bounds on variables. By combining inexact affine scaling generalized Newton with interior backtracking line search technique, each iterate switches to inexact generalized Newton backtracking step to strict interior point feasibility. The global convergence results are developed in a very general setting of computing trial steps by the affine scaling generalized Newton-like method that is augmented by an interior backtracking line search technique projection onto the feasible set. Under some reasonable conditions we establish that close to a regular solution the inexact generalized Newton method is shown to converge locally p-order q-superlinearly. We characterize the order of local convergence based on convergence behavior of the quality of the approximate subdifferentials and indicate how to choose an inexact forcing sequence which preserves the rapid convergence of the proposed algorithm. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases.     

A choice of forcing terms in inexact Newton method

Inexact Newton method is one of the effective tools for solving systems of nonlinear equations. In each iteration step of the method, a forcing term, which is used to control the accuracy when solving the Newton equations, is required. The choice of the forcing terms is of great importance due to their strong influence on the behavior of the inexact Newton method, including its convergence, efficiency, and even robustness. To improve the efficiency and robustness of the inexact Newton method, a new strategy to determine the forcing terms is given in this paper. With the new forcing terms, the inexact Newton method is locally Q-superlinearly convergent. Numerical results are presented to support the effectiveness of the new forcing terms.     

An inexact Newton method for nonlinear two-point boundary-value problems

The method of quasilinearization for nonlinear two-point boundary-value problems is an application of Newton's method to a nonlinear differential operator equation. Since the linear boundary-value problem to be solved at each iteration must be discretized, it is natural to consider quasilinearization in the framework of an inexact Newton method. More importantly, each linear problem is only a local model of the nonlinear problem, and so it is inefficient to try to solve the linear problems to full accuracy. Conditions on size of the relative residual of the linear differential equation can then be specified to guarantee rapid local convergence to the solution of the nonlinear continuous problem. If initial-value techniques are used to solve the linear boundary-value problems, then an integration step selection scheme is proposed so that the residual criteria are satisfied by the approximate solutions. Numerical results are presented that demonstrate substantial computational savings by this type of economizing on the intermediate problems.This work was supported in part by DOE Contract DE-AS05-82-ER13016 and NSF Grant RII-89-17691 and was part of the author's doctoral thesis at Rice University. It is a pleasure to thank the author's thesis advisors, Professor R. A. Tapia and Professor J. E. Dennis, Jr.     

A nonmonotone Jacobian smoothing inexact Newton method for NCP

In this paper we propose Jacobian smoothing inexact Newton method for nonlinear complementarity problems (NCP) with derivative-free nonmonotone line search. This nonmonotone line search technique ensures globalization and is a combination of Grippo-Lampariello-Lucidi (GLL) and Li-Fukushima (LF) strategies, with the aim to take into account their advantages. The method is based on very well known Fischer-Burmeister reformulation of NCP and its smoothing Kanzow’s approximation. The mixed Newton equation, which combines the semismooth function with the Jacobian of its smooth operator, is solved approximately in every iteration, so the method belongs to the class of Jacobian smoothing inexact Newton methods. The inexact search direction is not in general a descent direction and this is the reason why nonmonotone scheme is used for globalization. Global convergence and local superlinear convergence of method are proved. Numerical performances are also analyzed and point out that high level of nonmonotonicity of this line search rule enables robust and efficient method.     

Forcing sequences and inexact Newton iterates in Banach space

We use inexact Newton iterates to approximate a solution of a nonlinear equation in a Banach space. Solving a nonlinear equation using Newton iterates at each stage is very expensive in general. That is why we consider inexact Newton methods, where the Newton equations are solved only approximately and in some unspecified manner. In the elegant paper [1], natural assumptions under which the forcing sequence is uniformly less than one were given based on the first Fréchet-derivative of the operator involved. Here, we use assumption on the second Fréchet-derivative. This way, we essentially reproduce all results found earlier. However, our upper error bounds on the distances involved are smaller.     

On convergence rates of inexact Newton regularizations

Summary. REGINN is an algorithm of inexact Newton type for the regularization of nonlinear ill-posed problems [Inverse Problems 15 (1999), pp. 309–327]. In the present article convergence is shown under weak smoothness assumptions (source conditions). Moreover, convergence rates are established. Some computational illustrations support the theoretical results. Received March 12, 1999 / Published online October 16, 2000     

A note on inexact gradient and Hessian conditions for cubic regularized Newton’s method

The inexact cubic-regularized Newton’s method (CR) proposed by Cartis, Gould and Toint achieves the same convergence rate as exact CR proposed by Nesterov and Polyak, but the inexact condition is not implementable due to its dependence on a future variable. This note establishes the same convergence rate under a similar but implementable inexact condition, which depends on only current variables. Our proof bounds the function-value decrease over total iterations rather than each iteration in the previous studies.     

Fast convergence of an inexact interior point method for horizontal complementarity problems

In Andreani et al. (Numer. Algorithms 57:457–485, 2011), an interior point method for the horizontal nonlinear complementarity problem was introduced. This method was based on inexact Newton directions and safeguarding projected gradient iterations. Global convergence, in the sense that every cluster point is stationary, was proved in Andreani et al. (Numer. Algorithms 57:457–485, 2011). In Andreani et al. (Eur. J. Oper. Res. 249:41–54, 2016), local fast convergence was proved for the underdetermined problem in the case that the Newtonian directions are computed exactly. In the present paper, it will be proved that the method introduced in Andreani et al. (Numer. Algorithms 57:457–485, 2011) enjoys fast (linear, superlinear, or quadratic) convergence in the case of truly inexact Newton computations. Some numerical experiments will illustrate the accuracy of the convergence theory.     

Inner iterations in the shift-invert residual Arnoldi method and the Jacobi-Davidson method

We establish a general convergence theory of the Shift-Invert Residual Arnoldi(SIRA)method for computing a simple eigenvalue nearest to a given targetσand the associated eigenvector.In SIRA,a subspace expansion vector at each step is obtained by solving a certain inner linear system.We prove that the inexact SIRA method mimics the exact SIRA well,i.e.,the former uses almost the same outer iterations to achieve the convergence as the latter does if all the inner linear systems are iteratively solved with low or modest accuracy during outer iterations.Based on the theory,we design practical stopping criteria for inner solves.Our analysis is on one step expansion of subspace and the approach applies to the Jacobi-Davidson(JD)method with the fixed targetσas well,and a similar general convergence theory is obtained for it.Numerical experiments confirm our theory and demonstrate that the inexact SIRA and JD are similarly effective and are considerably superior to the inexact SIA.     

The convergence analysis of inexact Gauss–Newton methods for nonlinear problems

In this paper, inexact Gauss–Newton methods for nonlinear least squares problems are studied. Under the hypothesis that derivative satisfies some kinds of weak Lipschitz conditions, the local convergence properties of inexact Gauss–Newton and inexact Gauss–Newton like methods for nonlinear problems are established with the modified relative residual control. The obtained results can provide an estimate of convergence ball for inexact Gauss–Newton methods.     

Local convergence analysis of several inexact Newton-type algorithms for general nonlinear eigenvalue problems

We study the local convergence of several inexact numerical algorithms closely related to Newton’s method for the solution of a simple eigenpair of the general nonlinear eigenvalue problem $T(\lambda )v=0$ . We investigate inverse iteration, Rayleigh quotient iteration, residual inverse iteration, and the single-vector Jacobi–Davidson method, analyzing the impact of the tolerances chosen for the approximate solution of the linear systems arising in these algorithms on the order of the local convergence rates. We show that the inexact algorithms can achieve the same order of convergence as the exact methods if appropriate sequences of tolerances are applied to the inner solves. We discuss the connections and emphasize the differences between the standard inexact Newton’s method and these inexact algorithms. When the local symmetry of $T(\lambda )$ is present, the use of a nonlinear Rayleigh functional is shown to be fundamental in achieving higher order of convergence rates. The convergence results are illustrated by numerical experiments.