On the order optimality of the regularization via inexact Newton iterations

Inexact Newton regularization methods have been proposed by Hanke and Rieder for solving nonlinear ill-posed inverse problems. Every such a method consists of two components: an outer Newton iteration and an inner scheme providing increments by regularizing local linearized equations. The method is terminated by a discrepancy principle. In this paper we consider the inexact Newton regularization methods with the inner scheme defined by Landweber iteration, the implicit iteration, the asymptotic regularization and Tikhonov regularization. Under certain conditions we obtain the order optimal convergence rate result which improves the suboptimal one of Rieder. We in fact obtain a more general order optimality result by considering these inexact Newton methods in Hilbert scales.     

Improved local convergence analysis of the Landweber iteration in Banach spaces

Archiv der Mathematik - The convergence analysis of the Landweber iteration for solving inverse problems in Banach spaces via Hölder stability estimates is well studied by de Hoop et al....     

An implicit Landweber method for nonlinear ill-posed operator equations

In this paper, we are interested in the solution of nonlinear inverse problems of the form F(x)=y. We propose an implicit Landweber method, which is similar to the third-order midpoint Newton method in form, and consider the convergence behavior of the implicit Landweber method. Using the discrepancy principle as a stopping criterion, we obtain a regularization method for ill-posed problems. We conclude with numerical examples confirming the theoretical results, including comparisons with the classical Landweber iteration and presented modified Landweber 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.     

Convergence of inexact inverse iteration with application to preconditioned iterative solves

In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results. AMS subject classification (2000)  65F15, 65F10     

Towards a general convergence theory for inexact Newton regularizations

We develop a general convergence analysis for a class of inexact Newton-type regularizations for stably solving nonlinear ill-posed problems. Each of the methods under consideration consists of two components: the outer Newton iteration and an inner regularization scheme which, applied to the linearized system, provides the update. In this paper we give a novel and unified convergence analysis which is not confined to a specific inner regularization scheme but applies to a multitude of schemes including Landweber and steepest decent iterations, iterated Tikhonov method, and method of conjugate gradients.     

On the convergence radius of the modified Newton method for multiple roots under the center–Hölder condition

It is very important to enlarge the convergence ball of an iterative method. Recently, the convergence radius of the modified Newton method for finding multiple roots of nonlinear equations has been presented by Ren and Argyros when the involved function is Hölder and center–Hölder continuous. Different from the technique and the hypothesis used by them, in this paper, we also investigate the convergence radius of the modified Newton method under the condition that the derivative $f^{(m)}$ of function f satisfies the center–Hölder continuous condition. The radius given here is larger than that given by Ren and Argyros. The uniqueness ball of solution is also discussed. Some examples are given to show applications of our theorem.     

Inexact inverse subspace iteration for generalized eigenvalue problems

n this paper, we present an inexact inverse subspace iteration method for computing a few eigenpairs of the generalized eigenvalue problem Ax=λBx. We first formulate a version of inexact inverse subspace iteration in which the approximation from one step is used as an initial approximation for the next step. We then analyze the convergence property, which relates the accuracy in the inner iteration to the convergence rate of the outer iteration. In particular, the linear convergence property of the inverse subspace iteration is preserved. Numerical examples are given to demonstrate the theoretical results.     

On the convergence of an inexact Gauss–Newton trust-region method for nonlinear least-squares problems with simple bounds

We introduce an inexact Gauss–Newton trust-region method for solving bound-constrained nonlinear least-squares problems where, at each iteration, a trust-region subproblem is approximately solved by the Conjugate Gradient method. Provided a suitable control on the accuracy to which we attempt to solve the subproblems, we prove that the method has global and asymptotic fast convergence properties. Some numerical illustration is also presented.     

Nonlinear scalarizing functions in set optimization problems

In this paper, we obtain Hölder continuity of the nonlinear scalarizing function for l-type less order relation, which is introduced by Hernández and Rodríguez-Marín (J. Math. Anal. Appl. 2007;325:1–18). Moreover, we introduce the nonlinear scalarizing function for u-type less order relation and establish continuity, convexity and Hölder continuity of the nonlinear scalarizing function for u-type less order relation. As applications, we firstly obtain Lipschitz continuity of solution mapping to the parametric equilibrium problems and then establish Lipschitz continuity of strongly approximate solution mappings for l-type less order relation, u-type less order relation and set less order relation to the parametric set optimization problems by using convexity and Hölder continuity of the nonlinear scalarizing functions.     

Inexact Interior-Point Method

In this paper, we introduce an inexact interior-point algorithm for a constrained system of equations. The formulation of the problem is quite general and includes nonlinear complementarity problems of various kinds. In our convergence theory, we interpret the inexact interior-point method as an inexact Newton method. This enables us to establish a global convergence theory for the proposed algorithm. Under the additional assumption of the invertibility of the Jacobian at the solution, the superlinear convergence of the iteration sequence is proved.     

MN-DPMHSS iteration method for systems of nonlinear equations with block two-by-two complex Jacobian matrices

Preconditioned modified Hermitian and skew-Hermitian splitting (PMHSS) method is an unconditionally convergent iteration method for solving large sparse complex symmetric systems of linear equation. Motivated by the PMHSS method, we develop a new method of solving a class of linear equations with block two-by-two complex coefficient matrix by introducing two coefficients, noted as DPMHSS. By making use of the DPMHH iteration as the inner solver to approximately solve the Newton equations, we establish modified Newton-DPMHSS (MN-DPMHSS) method for solving large systems of nonlinear equations. We analyze the local convergence properties under the Hölder continuous conditions, which is weaker than Lipschitz assumptions. Numerical results are given to confirm the effectiveness of our method.     

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.     

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.     

Convergence analysis for a family of improved super-Halley methods under general convergence condition

In this paper, we focus on the semilocal convergence for a family of improved super-Halley methods for solving non-linear equations in Banach spaces. Different from the results in Wang et al. (J Optim Theory Appl 153:779–793, 2012), the condition of Hölder continuity of third-order Fréchet derivative is replaced by its general continuity condition, and the latter is weaker than former. Moreover, the R-order of the methods is also improved. By using the recurrence relations, we prove a convergence theorem to show the existence-uniqueness of the solution. The R-order of these methods is analyzed with the third-order Fréchet derivative of the operator satisfies general continuity condition and Hölder continuity condition.     

Semilocal and global convergence of the Newton‐HSS method for systems of nonlinear equations

Newton‐HSS methods, which are variants of inexact Newton methods different from the Newton–Krylov methods, have been shown to be competitive methods for solving large sparse systems of nonlinear equations with positive‐definite Jacobian matrices (J. Comp. Math. 2010; 28 :235–260). In that paper, only local convergence was proved. In this paper, we prove a Kantorovich‐type semilocal convergence. Then we introduce Newton‐HSS methods with a backtracking strategy and analyse their global convergence. Finally, these globally convergent Newton‐HSS methods are shown to work well on several typical examples using different forcing terms to stop the inner iterations. Copyright © 2010 John Wiley & Sons, Ltd.     

A Neural Network-Based Policy Iteration Algorithm with Global $$H^2$$ -Superlinear Convergence for Stochastic Games on Domains

In this work, we propose a class of numerical schemes for solving semilinear Hamilton–Jacobi–Bellman–Isaacs (HJBI) boundary value problems which arise naturally from exit time problems of diffusion processes with controlled drift. We exploit policy iteration to reduce the semilinear problem into a sequence of linear Dirichlet problems, which are subsequently approximated by a multilayer feedforward neural network ansatz. We establish that the numerical solutions converge globally in the \(H^2\)-norm and further demonstrate that this convergence is superlinear, by interpreting the algorithm as an inexact Newton iteration for the HJBI equation. Moreover, we construct the optimal feedback controls from the numerical value functions and deduce convergence. The numerical schemes and convergence results are then extended to oblique derivative boundary conditions. Numerical experiments on the stochastic Zermelo navigation problem are presented to illustrate the theoretical results and to demonstrate the effectiveness of the method.

     

A filter line search algorithm based on an inexact Newton method for nonconvex equality constrained optimization

We propose an inexact Newton method with a filter line search algorithm for nonconvex equality constrained optimization. Inexact Newton’s methods are needed for large-scale applications which the iteration matrix cannot be explicitly formed or factored. We incorporate inexact Newton strategies in filter line search, yielding algorithm that can ensure global convergence. An analysis of the global behavior of the algorithm and numerical results on a collection of test problems are presented.     

Remarks on the Hölder continuity of solutions to elliptic equations in divergence form

The classical proofs of the De Giorgi–Nash–Moser Theorem are based on the iteration of some inequality through countably many concentric balls. In this note, we present a new approach to the Hölder continuity of solutions to elliptic equations in divergence form, which avoids any form of discrete iteration. In particular, we prove that a suitable energy function satisfies a differential inequality, whose integration yields a new proof of the crucial step in the regularity result.     

A New Gradient Method for Ill-Posed Problems

In this paper, we present a new gradient method for linear and nonlinear ill-posed problems F(x) = y. Combined with the discrepancy principle as stopping rule it is a regularization method that yields convergence to an exact solution if the operator F satisfies a tangential cone condition. If the exact solution satisfies smoothness conditions, then even convergence rates can be proven. Numerical results show that the new method in most cases needs less iteration steps than Landweber iteration, the steepest descent or minimal error method.