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.     

A theoretical analysis on efficiency of some Newton-PCG methods

In this paper, we study the efficiency issue of inexact Newton-type methods for smooth unconstrained optimization problems under standard assumptions from theoretical point of view by discussing a concrete Newton-PCG algorithm. In order to compare the algorithm with Newton's method, a ratio between the measures of their approximate efficiencies is investigated. Under mild conditions, it is shown that first, this ratio is larger than 1, which implies that the Newton-PCG algorithm is more efficient than Newton's method, and second, this ratio increases when the dimension n of the problem increases and tends to infinity at least at a rate In n/In 2 when n→∞, which implies that in theory the Newton-PCG algorithm is much more efficient for middle- and large-scale problems. These theoretical results are also supported by our preliminary numerical experiments.     

Theoretical Efficiency of an Inexact Newton Method

We propose a local algorithm for smooth unconstrained optimization problems with n variables. The algorithm is the optimal combination of an exact Newton step with Choleski factorization and several inexact Newton steps with preconditioned conjugate gradient subiterations. The preconditioner is taken as the inverse of the Choleski factorization in the previous exact Newton step. While the Newton method is converging precisely with Q-order 2, this algorithm is also precisely converging with Q-order 2. Theoretically, its average number of arithmetic operations per step is much less than the corresponding number of the Newton method for middle-scale and large-scale problems. For instance, when n=200, the ratio of these two numbers is less than 0.53. Furthermore, the ratio tends to zero approximately at a rate of log 2/logn when n approaches infinity.     

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.     

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.     

Indefinitely preconditioned inexact Newton method for large sparse equality constrained non-linear programming problems

An inexact Newton algorithm for large sparse equality constrained non-linear programming problems is proposed. This algorithm is based on an indefinitely preconditioned smoothed conjugate gradient method applied to the linear KKT system and uses a simple augmented Lagrangian merit function for Armijo type stepsize selection. Most attention is devoted to the termination of the CG method, guaranteeing sufficient descent in every iteration and decreasing the number of required CG iterations, and especially, to the choice of a suitable preconditioner. We investigate four preconditioners, which have 2 × 2 block structure, and prove theoretically their good properties. The efficiency of the inexact Newton algorithm, together with a comparison of various preconditioners and strategies, is demonstrated by using a large collection of test problems. © 1998 John Wiley & Sons, Ltd.     

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.     

New Version of the Newton Method for Nonsmooth Equations

In this paper, an inexact Newton scheme is presented which produces a sequence of iterates in which the problem functions are differentiable. It is shown that the use of the inexact Newton scheme does not reduce the convergence rate significantly. To improve the algorithm further, we use a classical finite-difference approximation technique in this context. Locally superlinear convergence results are obtained under reasonable assumptions. To globalize the algorithm, we incorporate features designed to improve convergence from an arbitrary starting point. Convergence results are presented under the condition that the generalized Jacobian of the problem function is nonsingular. Finally, implementations are discussed and numerical results are presented.     

A smoothing inexact Newton method for P 0 nonlinear complementarity problem

We first propose a new class of smoothing functions for the nonlinear complementarity function which contains the well-known Chen-Harker-Kanzow-Smale smoothing function and Huang-Han-Chen smoothing function as special cases, and then present a smoothing inexact Newton algorithm for the P ₀ nonlinear complementarity problem. The global convergence and local superlinear convergence are established. Preliminary numerical results indicate the feasibility and efficiency of the algorithm.     

Two‐step Newton‐type methods for solving inverse eigenvalue problems

In this paper, we apply the two‐step Newton method to solve inverse eigenvalue problems, including exact Newton, Newton‐like, and inexact Newton‐like versions. Our results show that both two‐step Newton and two‐step Newton‐like methods converge cubically, and the two‐step inexact Newton‐like method is super quadratically convergent. Numerical implementations demonstrate the effectiveness of new algorithms.     

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.     

求解拟可微方程组的非精确牛顿法

本文首次给出拟可微方程的非精确牛顿算法 ,其适定性是基于广义的 Kakutani不动点定理得到的 ,并证明了算法产生的序列是局部收敛的且具有线性收敛速度     

非线性互补问题非精确逐次逼近法的全局收敛性

本文针对非线性互补问题,提出了与其等价的非光滑方程的非精确逐次逼近算法,并在一定条件下证明了该算法的全局收敛性。     

A modified damped Newton method for linear complementarity problems

We present a modified damped Newton method for solving large sparse linear complementarity problems, which adopts a new strategy for determining the stepsize at each Newton iteration. The global convergence of the new method is proved when the system matrix is a nondegenerate matrix. We then apply the matrix splitting technique to this new method, deriving an inexact splitting method for the linear complementarity problems. The global convergence of the resulting inexact splitting method is proved, too. Numerical results show that the new methods are feasible and effective for solving the large sparse linear complementarity problems.     

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.     

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.     

An interior point algorithm with inexact step computation in function space for state constrained optimal control

We consider an interior point method in function space for PDE constrained optimal control problems with state constraints. Our emphasis is on the construction and analysis of an algorithm that integrates a Newton path-following method with adaptive grid refinement. This is done in the framework of inexact Newton methods in function space, where the discretization error of each Newton step is controlled by adaptive grid refinement in the innermost loop. This allows to perform most of the required Newton steps on coarse grids, such that the overall computational time is dominated by the last few steps. For this purpose we propose an a-posteriori error estimator for a problem suited norm.     

Inexact subgradient methods for quasi-convex optimization problems

In this paper, we consider a generic inexact subgradient algorithm to solve a nondifferentiable quasi-convex constrained optimization problem. The inexactness stems from computation errors and noise, which come from practical considerations and applications. Assuming that the computational errors and noise are deterministic and bounded, we study the effect of the inexactness on the subgradient method when the constraint set is compact or the objective function has a set of generalized weak sharp minima. In both cases, using the constant and diminishing stepsize rules, we describe convergence results in both objective values and iterates, and finite convergence to approximate optimality. We also investigate efficiency estimates of iterates and apply the inexact subgradient algorithm to solve the Cobb–Douglas production efficiency problem. The numerical results verify our theoretical analysis and show the high efficiency of our proposed algorithm, especially for the large-scale problems.     

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