On inexact Newton methods based on doubling iteration scheme for non‐symmetric algebraic Riccati equations

Newton iteration method can be used to find the minimal non‐negative solution of a certain class of non‐symmetric algebraic Riccati equations. However, a serious bottleneck exists in efficiency and storage for the implementation of the Newton iteration method, which comes from the use of some direct methods in exactly solving the involved Sylvester equations. In this paper, instead of direct methods, we apply a fast doubling iteration scheme to inexactly solve the Sylvester equations. Hence, a class of inexact Newton iteration methods that uses the Newton iteration method as the outer iteration and the doubling iteration scheme as the inner iteration is obtained. The corresponding procedure is precisely described and two practical methods of monotone convergence are algorithmically presented. In addition, the convergence property of these new methods is studied and numerical results are given to show their feasibility and effectiveness for solving the non‐symmetric algebraic Riccati equations. Copyright © 2010 John Wiley & Sons, Ltd.     

一个阶为2+\sqrt{6}的Newton改进算法

针对非线性方程求单根问题,提出了一种新的Newton预测-校正格式.通过每步迭代增加计算一个函数值和一阶导数值,使得每步迭代需要估计两个函数值和两个一阶导数值.与标准的Newton算法的二阶收敛速度相比,新算法具有更高阶的收敛速度2+\sqrt{6}.通过测试函数对新算法进行测试, 与相关算法比较,表明算法在迭代次数、运算时间及最优值方面都具有较明显的优势. 最后,将这种新格式推广到多维向量值函数, 采用泰勒公式证明了其收敛性,并给出了两个二维算例来验证其收敛的有效性.     

On Newton's method

In this note we discuss Newton's method in a setting somewhat more restrictive than customary. In this setting, however, we claim to have proved superlinear convergence of the Newton process without assuming twice differentiability or Lipschitz continuity of the first derivative of the operator. A further feature is that the iteration to be discussed is not initially but is eventually the Newton process. With this feature global rather than local convergence is achieved.This research was supported by the Boeing Scientific Research Laboratories and by Grant AF-AFOSR 937-65.     

PICARD ITERATION FOR NONSMOOTH EQUATIONS

1. IntroductionConsider the following nonsmooth equationsF(x) = 0 (l)where F: R" - R" is LipsChitz continuous. A lot of work has been done and is bellg doneto deal with (1). It is basicly a genera1ization of the cIassic Newton method [8,10,11,14],Newton-lthe methods[1,18] and quasiNewton methods [6,7]. As it is discussed in [7], the latter,quasiNewton methods, seem to be lindted when aPplied to nonsmooth caJse in that a boundof the deterioration of uPdating matrir can not be maintained w…     

Monotone convergence of Newton-like methods for M-matrix algebraic Riccati equations

For the algebraic Riccati equation whose four coefficient matrices form a nonsingular M-matrix or an irreducible singular M-matrix K, the minimal nonnegative solution can be found by Newton’s method and the doubling algorithm. When the two diagonal blocks of the matrix K have both large and small diagonal entries, the doubling algorithm often requires many more iterations than Newton’s method. In those cases, Newton’s method may be more efficient than the doubling algorithm. This has motivated us to study Newton-like methods that have higher-order convergence and are not much more expensive each iteration. We find that the Chebyshev method of order three and a two-step modified Chebyshev method of order four can be more efficient than Newton’s method. For the Riccati equation, these two Newton-like methods are actually special cases of the Newton–Shamanskii method. We show that, starting with zero initial guess or some other suitable initial guess, the sequence generated by the Newton–Shamanskii method converges monotonically to the minimal nonnegative solution.We also explain that the Newton-like methods can be used to great advantage when solving some Riccati equations involving a parameter.     

Truncated-newtono algorithms for large-scale unconstrained optimization

We present an algorithm for large-scale unconstrained optimization based onNewton's method. In large-scale optimization, solving the Newton equations at each iteration can be expensive and may not be justified when far from a solution. Instead, an inaccurate solution to the Newton equations is computed using a conjugate gradient method. The resulting algorithm is shown to have strong convergence properties and has the unusual feature that the asymptotic convergence rate is a user specified parameter which can be set to anything between linear and quadratic convergence. Some numerical results on a 916 vriable test problem are given. Finally, we contrast the computational behavior of our algorithm with Newton's method and that of a nonlinear conjugate gradient algorithm. This research was supported in part by DOT Grant CT-06-0011, NSF Grant ENG-78-21615 and grants from the Norwegian Research Council for Sciences and the Humanities and the Norway-American Association. This paper was originally presented at the TIMS-ORSA Joint National Meeting, Washington, DC, May 1980.     

关于变分不等式的Kantorovich定理

将Kantorovich定理推广到变分不等式,从而使得Newton迭代的收敛性、问题解的存在唯一性均可通过初始点处的可计算的条件来判断．     

Some iterative methods for the largest positive definite solution to a class of nonlinear matrix equation

In this paper, we propose some inversion-free iteration methods for finding the largest positive definite solution of a class of nonlinear matrix equation. Then, we consider the properties of the solution for this nonlinear matrix equation. Also, we establish Newton’s iteration method for finding the largest positive definite solution and prove its quadratic convergence. Furthermore, we derive the semi-local convergence of the Newton’s iteration method. Finally, some numerical examples are presented to illustrate the effectiveness of the theoretical results and the behavior of the considered methods.     

An efficient nonlinear iteration scheme for nonlinear parabolic–hyperbolic system

A nonlinear iteration method named the Picard–Newton iteration is studied for a two-dimensional nonlinear coupled parabolic–hyperbolic system. It serves as an efficient method to solve a nonlinear discrete scheme with second spatial and temporal accuracy. The nonlinear iteration scheme is constructed with a linearization–discretization approach through discretizing the linearized systems of the original nonlinear partial differential equations. It can be viewed as an improved Picard iteration, and can accelerate convergence over the standard Picard iteration. Moreover, the discretization with second-order accuracy in both spatial and temporal variants is introduced to get the Picard–Newton iteration scheme. By using the energy estimate and inductive hypothesis reasoning, the difficulties arising from the nonlinearity and the coupling of different equation types are overcome. It follows that the rigorous theoretical analysis on the approximation of the solution of the Picard–Newton iteration scheme to the solution of the original continuous problem is obtained, which is different from the traditional error estimate that usually estimates the error between the solution of the nonlinear discrete scheme and the solution of the original problem. Moreover, such approximation is independent of the iteration number. Numerical experiments verify the theoretical result, and show that the Picard–Newton iteration scheme with second-order spatial and temporal accuracy is more accurate and efficient than that of first-order temporal accuracy.     

Radial basis collocation method and quasi‐Newton iteration for nonlinear elliptic problems

This work presents a radial basis collocation method combined with the quasi‐Newton iteration method for solving semilinear elliptic partial differential equations. The main result in this study is that there exists an exponential convergence rate in the radial basis collocation discretization and a superlinear convergence rate in the quasi‐Newton iteration of the nonlinear partial differential equations. In this work, the numerical error associated with the employed quadrature rule is considered. It is shown that the errors in Sobolev norms for linear elliptic partial differential equations using radial basis collocation method are bounded by the truncation error of the RBF. The combined errors due to radial basis approximation, quadrature rules, and quasi‐Newton and Newton iterations are also presented. This result can be extended to finite element or finite difference method combined with any iteration methods discussed in this work. The numerical example demonstrates a good agreement between numerical results and analytical predictions. The numerical results also show that although the convergence rate of order 1.62 of the quasi‐Newton iteration scheme is slightly slower than rate of order 2 in the Newton iteration scheme, the former is more stable and less sensitive to the initial guess. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

A convergence analysis of an inexact Newton-Landweber iteration method for nonlinear problem

In this paper, we study the convergence and the convergence rates of an inexact Newton–Landweber iteration method for solving nonlinear inverse problems in Banach spaces. Opposed to the traditional methods, we analyze an inexact Newton–Landweber iteration depending on the Hölder continuity of the inverse mapping when the data are not contaminated by noise. With the namely Hölder-type stability and the Lipschitz continuity of DF, we prove convergence and monotonicity of the residuals defined by the sequence induced by the iteration. Finally, we discuss the convergence rates.     

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.     

Newton Methods for Solving Two Classes of Nonsmooth Equations

The paper is devoted to two systems of nonsmooth equations. One is the system of equations of max-type functions and the other is the system of equations of smooth compositions of max-type functions. The Newton and approximate Newton methods for these two systems are proposed. The Q-superlinear convergence of the Newton methods and the Q-linear convergence of the approximate Newton methods are established. The present methods can be more easily implemented than the previous ones, since they do not require an element of Clarke generalized Jacobian, of B-differential, or of b-differential, at each iteration point.     

无罚函数和滤子的一个新的QP-free方法

通过构造一个等价于原约束问题一阶KKT条件的非光滑方程组, 提出一类新的QP-free方法. 在迭代中采用了无罚函数和无滤子线搜索方法, 在此基础上, 通过牛顿-拟牛顿迭代得到满足KKT最优条件的解, 并证明该算法是可实现、具有全局收敛性. 另外, 在较弱条件下可以证明该方法具有超线性收敛性.     

A globalization procedure for solving nonlinear systems of equations

A new globalization procedure for solving a nonlinear system of equationsF(x)=0 is proposed based on the idea of combining Newton step and the steepest descent step WITHIN each iteration. Starting with an arbitrary initial point, the procedure converges either to a solution of the system or to a local minimizer off(x)=1/2F(x) ^T F(x). Each iteration is chosen to be as close to a Newton step as possible and could be the Newton step itself. Asymptotically the Newton step will be taken in each iteration and thus the convergence is quadratic. Numerical experiments yield positive results. Further generalizations of this procedure are also discussed in this paper.     

Multistep approximation algorithms: Improved convergence rates through postconditioning with smoothing kernels

We show how certain widely used multistep approximation algorithms can be interpreted as instances of an approximate Newton method. It was shown in an earlier paper by the second author that the convergence rates of approximate Newton methods (in the context of the numerical solution of PDEs) suffer from a “loss of derivatives”, and that the subsequent linear rate of convergence can be improved to be superlinear using an adaptation of Nash–Moser iteration for numerical analysis purposes; the essence of the adaptation being a splitting of the inversion and the smoothing into two separate steps. We show how these ideas apply to scattered data approximation as well as the numerical solution of partial differential equations. We investigate the use of several radial kernels for the smoothing operation. In our numerical examples we use radial basis functions also in the inversion step. This revised version was published online in June 2006 with corrections to the Cover Date.     

MODIFIED NEWTON＇S ALGORITHM FOR COMPUTING THE GROUP INVERSES OF SINGULAR TOEPLITZ MATRICES

Newton＇s iteration is modified for the computation of the group inverses of singular Toeplitz matrices. At each iteration, the iteration matrix is approximated by a matrix with a low displacement rank. Because of the displacement structure of the iteration matrix, the matrix-vector multiplication involved in Newton＇s iteration can be done efficiently. We show that the convergence of the modified Newton iteration is still very fast. Numerical results are presented to demonstrate the fast convergence of the proposed method.     

垂直线性互补问题的一步全局线性和局部二次收敛光滑Newton法

基于凝聚函数,提出一个求解垂直线性互补问题的光滑Newton法.该算法具有以下优点:(i)每次迭代仅需解一个线性系统和实施一次线性搜索;(ⅱ)算法对垂直分块P0矩阵的线性互补问题有定义且迭代序列的每个聚点都是它的解.而且,对垂直分块P₀+R₀矩阵的线性互补问题,算法产生的迭代序列有界且其任一聚点都是它的解;(ⅲ)在无严格互补条件下证得算法即具有全局线性收敛性又具有局部二次收敛性.许多已存在的求解此问题的光滑Newton法都不具有性质(ⅲ).     

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.     

A minimum effort optimal control problem for the wave equation

A minimum effort optimal control problem for the undamped wave equation is considered which involves L ^∞-control costs. Since the problem is non-differentiable a regularized problem is introduced. Uniqueness of the solution of the regularized problem is proven and the convergence of the regularized solutions is analyzed. Further, a semi-smooth Newton method is formulated to solve the regularized problems and its superlinear convergence is shown. Thereby special attention has to be paid to the well-posedness of the Newton iteration. Numerical examples confirm the theoretical results.