A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems

A new algorithm for the solation of large-scale nonlinear complementarity problems is introduced. The algorithm is based on a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems with up to 10 000 variables are presented. Partially supported by Agenzia Spaziale Italiana, Roma, Italy.     

On the convergence of Broyden-like methods for nonlinear equations with nondifferentiable terms

In this paper, the author studies a Broyden-like method for solving nonlinear equations with nondifferentiable terms, which uses as updating matrices, approximations for Jacobian matrices of differentiable terms. Local and semilocal convergence theorems are proved. The results generalize those of Broyden, Dennis and Moré.     

Generalized equations and the generalized Newton method

We give some convergence results on the generalized Newton method (referred to by some authors as Newton's method) and the chord method when applied to generalized equations. The main results of the paper extend the classical Kantorovich results on Newton's method to (nonsmooth) generalized equations. Our results also extend earlier results on nonsmooth equations due to Eaves, Robinson, Josephy, Pang and Chan. We also propose inner-iterative schemes for the computation of the generalized Newton iterates. These schemes generalize popular iterative methods (Richardson's method, Jacobi's method and the Gauss-Seidel method) for the solution of linear equations and linear complementarity problems and are shown to be convergent under natural generalizations of classical convergence criteria. Our results are applicable to equations involving single-valued functions and also to a class of generalized equations which includes variational inequalities, nonlinear complementarity problems and some nonsmooth convex minimization problems.     

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.     

一类非光滑方程组的牛顿法及全局收敛性

借助于一种新的微分 - -微分 ,本文给出极大值函数及其光滑复合的非光滑方程组的牛顿法 .最后证明了该牛顿法具有全局收敛性 .     

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.     

Newton Methods for Quasidifferentiable Equations and Their Convergence

The Newton method and the inexact Newton method for solving quasidifferentiable equations via the quasidifferential are investigated. The notion of Q-semismoothness for a quasidifferentiable function is proposed. The superlinear convergence of the Newton method proposed by Zhang and Xia is proved under the Q-semismooth assumption. An inexact Newton method is developed and its linear convergence is shown.Project sponsored by Shanghai Education Committee Grant 04EA01 and by Shanghai Government Grant T0502.     

A new smoothing Newton method for solving constrained nonlinear equations

In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well.     

A uniparametric family of iterative processes for solving nondifferentiable equations

In this work we study a class of secant-like iterations for solving nonlinear equations in Banach spaces. We consider a condition for divided differences which generalizes the usual ones, i.e., Lipschitz and Hölder continuous conditions. A semilocal convergence result is obtained for nondifferentiable operators. For that, we use a technique based on a new system of recurrence relations to obtain domains of existence and uniqueness of the solution. Finally, we apply our results to the numerical solution of several examples.     

A robust Kantorovich’s theorem on the inexact Newton method with relative residual error tolerance

We prove that under semi-local assumptions, the inexact Newton method with a fixed   relative residual error tolerance converges Q$Q$-linearly to a zero of the nonlinear operator under consideration. Using this result we show that the Newton method for minimizing a self-concordant function or to find a zero of an analytic function can be implemented with a fixed relative residual error tolerance.     

Convergence of quasi-Newton method with new inexact line search

Quasi-Newton method is a well-known effective method for solving optimization problems. Since it is a line search method, which needs a line search procedure after determining a search direction at each iteration, we must decide a line search rule to choose a step size along a search direction. In this paper, we propose a new inexact line search rule for quasi-Newton method and establish some global convergent results of this method. These results are useful in designing new quasi-Newton methods. Moreover, we analyze the convergence rate of quasi-Newton method with the new line search rule.     

A wavelet adaptive Newton method for the solution of nonlinear equations

For the solution of nonlinear equations, we present an adaptive wavelet scheme, which couples an inexact Newton method and the idea of nonlinear wavelet approximation. In particular, we obtain a result of quadratic convergence.     

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 convergence of a new secant-like method for solving nonlinear equations

In this paper, we prove that the order of a new secant-like method presented recently with the so-called order of 2.618 is only 2.414. Some mistakes in the derivation leading to such a conclusion are pointed out. Meanwhile, under the assumption that the second derivative of the involved function is bounded, the convergence radius of the secant-like method is given, and error estimates matching its convergence order are also provided by using a generalized Fibonacci sequence.     

解奇异非光滑方程组的牛顿法和不精确牛顿法

本文主要解决奇异非光滑方程组的解法。应用一种新的次微分的外逆，我们提出了牛顿法和不精确牛顿法，它们的收敛性同时也得到了证明。这种方法能更容易在一引起实际应用中实现。这种方法可以看作是已存在的解非光滑方程组的方法的延伸。     

A new eighth-order iterative method for solving nonlinear equations

In this paper we present an improvement of the fourth-order Newton-type method for solving a nonlinear equation. The new Newton-type method is shown to converge of the order eight. Per iteration the new method requires three evaluations of the function and one evaluation of its first derivative and therefore the new method has the efficiency index of , which is better than the well known Newton-type methods of lower order. We shall examine the effectiveness of the new eighth-order Newton-type method by approximating the simple root of a given nonlinear equation. Numerical comparisons are made with several other existing methods to show the performance of the presented method.     

Various Newton-type iterative methods for solving nonlinear equations

The aim of the present paper is to introduce and investigate new ninth and seventh order convergent Newton-type iterative methods for solving nonlinear equations. The ninth order convergent Newton-type iterative method is made derivative free to obtain seventh-order convergent Newton-type iterative method. These new with and without derivative methods have efficiency indices 1.5518 and 1.6266, respectively. The error equations are used to establish the order of convergence of these proposed iterative methods. Finally, various numerical comparisons are implemented by MATLAB to demonstrate the performance of the developed methods.