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.     

An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems

We discuss local convergence of Newton’s method to a singular solution x ^* of the nonlinear equations F(x) =  0, for $F:{\mathbb{R}}^n \rightarrow {\mathbb{R}}^n$ . It is shown that an existing proof of Griewank, concerning linear convergence to a singular solution x ^* from a starlike domain around x ^* for F twice Lipschitz continuously differentiable and x ^* satisfying a particular regularity condition, can be adapted to the case in which F′ is only strongly semismooth at the solution. Further, Newton’s method can be accelerated to produce fast linear convergence to a singular solution by overrelaxing every second Newton step. These results are applied to a nonlinear-equations reformulation of the nonlinear complementarity problem (NCP) whose derivative is strongly semismooth when the function f arising in the NCP is sufficiently smooth. Conditions on f are derived that ensure that the appropriate regularity conditions are satisfied for the nonlinear-equations reformulation of the NCP at x ^*.     

Convergence of a generalized Newton and an inexact generalized Newton algorithms for solving nonlinear equations with nondifferentiable terms

In this paper, we consider two versions of the Newton-type method for solving a nonlinear equations with nondifferentiable terms, which uses as iteration matrices, any matrix from B-differential of semismooth terms. Local and global convergence theorems for the generalized Newton and inexact generalized Newton method are proved. Linear convergence of the algorithms is obtained under very mild assumptions. The superlinear convergence holds under some conditions imposed on both terms of equation. Some numerical results indicate that both algorithms works quite well in practice.      

Stability of a Cubically Convergent Method for Generalized Equations

In Geoffroy et al, Acceleration of convergence in Dontchev's iterative method for solving variational inclusions Serdica Math. J. 29 (2003), pp. 45–54] we showed the convergence of a cubic method for solving generalized equations of the form 0 ∈ f(x) +- G(x) where f is a function and G stands for a set-valued map. We investigate here the stability of such a method with respect to some perturbations. More precisely, we consider the perturbed equation y ∈ f(x) +- G(x) and we show that the pseudo-Lipschitzness of the map (f +- G)⁻¹ is closely tied to the uniformity of our method in the sense that the attraction region does not depend on small perturbations of the parameter y. Finally, we provide an enhanced version of the convergence theorem established by Geoffroy, et al.     

A novel cubically convergent iterative method for computing complex roots of nonlinear equations

A fast and simple iterative method with cubic convergent is proposed for the determination of the real and complex roots of any function F(x) = 0. The idea is based upon passing a defined function G(x) tangent to F(x) at an arbitrary starting point. Choosing G(x) in the form of x^k or k^x, where k is obtained for the best correlation with the function F(x), gives an added freedom, which in contrast to all existing methods, accelerates the convergence. Also, this new method can find complex roots just by a real initial guess. This is in contrast to many other methods like the famous Newton method that needs complex initial guesses for finding complex roots. The proposed method is compared to some new and famous methods like Newton method and a modern solver that is fsolve command in MATLAB. The results show the effectiveness and robustness of this new method as compared to other methods.     

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.     

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 partial synchronization of iterative methods

The rapidly growing field of parallel computing systems promotes the study of parallel algorithms, with the Monte Carlo method and asynchronous iterations being among the most valuable types. These algorithms have a number of advantages. There is no need for a global time in a parallel system (no need for synchronization), and all computational resources are efficiently loaded (the minimum processor idle time). The method of partial synchronization of iterations for systems of equations was proposed by the authors earlier. In this article, this method is generalized to include the case of nonlinear equations of the form x = F(x), where x is an unknown column vector of length n, and F is an operator from ?ⁿ into ?ⁿ. We consider operators that do not satisfy conditions that are sufficient for the convergence of asynchronous iterations, with simple iterations still converging. In this case, one can specify such an incidence of the operator and such properties of the parallel system that asynchronous iterations fail to converge. Partial synchronization is one of the effective ways to solve this problem. An algorithm is proposed that guarantees the convergence of asynchronous iterations and the Monte Carlo method for the above class of operators. The rate of convergence of the algorithm is estimated. The results can prove useful for solving high-dimensional problems on multiprocessor computational systems.     

The inexact, inexact perturbed, and quasi-Newton methods are equivalent models

A classical model of Newton iterations which takes into account some error terms is given by the quasi-Newton method, which assumes perturbed Jacobians at each step. Its high convergence orders were characterized by Dennis and Moré [Math. Comp. 28 (1974), 549-560]. The inexact Newton method constitutes another such model, since it assumes that at each step the linear systems are only approximately solved; the high convergence orders of these iterations were characterized by Dembo, Eisenstat and Steihaug [SIAM J. Numer. Anal. 19 (1982), 400-408]. We have recently considered the inexact perturbed Newton method [J. Optim. Theory Appl. 108 (2001), 543-570] which assumes that at each step the linear systems are perturbed and then they are only approximately solved; we have characterized the high convergence orders of these iterates in terms of the perturbations and residuals.

In the present paper we show that these three models are in fact equivalent, in the sense that each one may be used to characterize the high convergence orders of the other two. We also study the relationship in the case of linear convergence and we deduce a new convergence result.

     

Variational iteration technique for solving nonlinear equations

In this paper, we use the variational iteration technique to suggest some new iterative methods for solving nonlinear equations f(x)=0. We also discuss the convergence criteria of these new iterative methods. Comparison with other similar methods is also given. These new methods can be considered as an alternative to the Newton method. We also give several examples to illustrate the efficiency of these methods. This technique can be used to suggest a wide class of new iterative methods for solving system of nonlinear equations.     

Uniformity and inexact version of a proximal method for metrically regular mappings

We study stability properties of a proximal point algorithm for solving the inclusion 0∈T(x) when T is a set-valued mapping that is not necessarily monotone. More precisely we show that the convergence of our algorithm is uniform, in the sense that it is stable under small perturbations whenever the set-valued mapping T is metrically regular at a given solution. We present also an inexact proximal point method for strongly metrically subregular mappings and show that it is super-linearly convergent to a solution to the inclusion 0∈T(x).     

A quadratically convergent method for minimizing a sum of euclidean norms

We consider the problem of minimizing a sum of Euclidean norms. \(F(x) = \sum\nolimits_{i = 1}^m {||r_i } (x)||\) here the residuals {r _i(x)} are affine functions fromR ⁿ toR ¹ (n≥1≥2,m>-2). This arises in a number of applications, including single-and multi-facility location problems. The functionF is, in general, not differentiable atx if at least oner _i (x) is zero. Computational methods described in the literature converge quite slowly if the solution is at such a point. We present a new method which, at each iteration, computes a direction of search by solving the Newton system of equations, projected, if necessary, into a linear manifold along whichF is locally differentiable. A special line search is used to obtain the next iterate. The algorithm is closely related to a method recently described by Calamai and Conn. The new method has quadratic convergence to a solutionx under given conditions. The reason for this property depends on the nature of the solution. If none of the residuals is zero at^* x, thenF is differentiable at^* x and the quadratic convergence follows from standard properties of Newton's method. If one of the residuals, sayr _i ^* x), is zero, then, as the iteration proceeds, the Hessian ofF becomes extremely ill-conditioned. It is proved that this illconditioning, instead of creating difficulties, actually causes quadratic convergence to the manifold (x?r _i (x)=0}. If this is a single point, the solution is thus identified. Otherwise it is necessary to continue the iteration restricted to this manifold, where the usual quadratic convergence for Newton's method applies. If several residuals are zero at^* x, several stages of quadratic convergence take place as the correct index set is constructed. Thus the ill-conditioning property accelerates the identification of the residuals which are zero at the solution. Numerical experiments are presented, illustrating these results.     

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)     

Smale's α-theory for inexact Newton methods under the γ-condition

The present paper is concerned with the convergence problem of inexact Newton methods. Assuming that the nonlinear operator satisfies the γ-condition, a convergence criterion for inexact Newton methods is established which includes Smale's type convergence criterion. The concept of an approximate zero for inexact Newton methods is proposed in this paper and the criterion for judging an initial point being an approximate zero is established. Consequently, Smale's α-theory is generalized to inexact Newton methods. Furthermore, a numerical example is presented to illustrate the applicability of our main results.     

Local path-following property of inexact interior methods in nonlinear programming

We study the local behavior of a primal-dual inexact interior point methods for solving nonlinear systems arising from the solution of nonlinear optimization problems or more generally from nonlinear complementarity problems. The algorithm is based on the Newton method applied to a sequence of perturbed systems that follows by perturbation of the complementarity equations of the original system. In case of an exact solution of the Newton system, it has been shown that the sequence of iterates is asymptotically tangent to the central path (Armand and Benoist in Math. Program. 115:199?C222, 2008). The purpose of the present paper is to extend this result to an inexact solution of the Newton system. We give quite general conditions on the different parameters of the algorithm, so that this asymptotic property is satisfied. Some numerical tests are reported to illustrate our theoretical results.     

On the singular Weyl-Titchmarsh function of perturbed spherical Schrödinger operators

We investigate the singular Weyl-Titchmarsh m-function of perturbed spherical Schrödinger operators (also known as Bessel operators) under the assumption that the perturbation q(x) satisfies xq(x)∈L¹(0,1). We show existence plus detailed properties of a fundamental system of solutions which are entire with respect to the energy parameter. Based on this we show that the singular m-function belongs to the generalized Nevanlinna class and connect our results with the theory of super singular perturbations.     

A globally convergent inexact Newton method with a new choice for the forcing term

In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s _k of the Newton’s system J(x _k )s=−F(x _k ) is found. This means that s _k must satisfy a condition like ‖F(x _k )+J(x _k )s _k ‖≤η _k ‖F(x _k )‖ for a forcing term η _k ∈[0,1). Possible choices for η _k have already been presented. In this work, a new choice for η _k is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms 32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas. Supported by FAPESP, CNPq, PRONEX-Optimization.     

Generalized Newton’s method based on graphical derivatives

This paper concerns developing a numerical method of the Newton type to solve systems of nonlinear equations described by nonsmooth continuous functions. We propose and justify a new generalized Newton algorithm based on graphical derivatives, which have never been used to derive a Newton-type method for solving nonsmooth equations. Based on advanced techniques of variational analysis and generalized differentiation, we establish the well-posedness of the algorithm, its local superlinear convergence, and its global convergence of the Kantorovich type. Our convergence results hold with no semismoothness and Lipschitzian assumptions, which is illustrated by examples. The algorithm and main results obtained in the paper are compared with well-recognized semismooth and B-differentiable versions of Newton’s method for nonsmooth Lipschitzian equations.     

A Newton-like method and its application

In this paper we prove an existence and uniqueness theorem for solving the operator equation F(x)+G(x)=0, where F is a Gateaux differentiable continuous operator while the operator G satisfies a Lipschitz-condition on an open convex subset of a Banach space. As corollaries, a theorem of Tapia on a weak Newton's method and the classical convergence theorem for modified Newton-iterates are deduced. An existence theorem for a generalized Euler-Lagrange equation in the setting of Sobolev space is obtained as a consequence of the main theorem. We also obtain a class of Gateaux differentiable operators which are nowhere Frechet differentiable. Illustrative examples are also provided.     

Two-step relaxation Newton algorithm for solving nonlinear algebraic equations

We introduce a new algorithm, namely two-step relaxation Newton, for solving algebraic nonlinear equations f(x)=0. This new algorithm is derived by combining two different relaxation Newton algorithms introduced by Wu et al. (Appl. Math. Comput. 201:553–560, 2008), and therefore with special choice of the so called splitting function it can be implemented simultaneously, stably with much less memory storage and CPU time compared with the Newton–Raphson method. Global convergence of this algorithm is established and numerical experiments show that this new algorithm is feasible and effective, and outperforms the original relaxation Newton algorithm and the Newton–Raphson method in the sense of iteration number and CPU time.