A preconditioned block Arnoldi method for large scale Lyapunov and algebraic Riccati equations

In the present paper, we propose a preconditioned Newton–Block Arnoldi method for solving large continuous time algebraic Riccati equations. Such equations appear in control theory, model reduction, circuit simulation amongst other problems. At each step of the Newton process, we solve a large Lyapunov matrix equation with a low rank right hand side. These equations are solved by using the block Arnoldi process associated with a preconditioner based on the alternating direction implicit iteration method. We give some theoretical results and report numerical tests to show the effectiveness of the proposed approach.     

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.     

An Arnoldi based algorithm for large algebraic Riccati equations

In the present work, we present a numerical method for the computation of approximate solutions for large continuous-time algebraic Riccati equations. The proposed method is a method of projection onto a matrix Krylov subspace. We use a matrix Arnoldi process to construct an orthonormal basis. We give some theoretical results and numerical experiments for large problems.     

Quasi-Newton methods in infinite-dimensional spaces and application to matrix equations

In the first part of this paper, we give a survey on convergence rates analysis of quasi-Newton methods in infinite Hilbert spaces for nonlinear equations. Then, in the second part we apply quasi-Newton methods in their Hilbert formulation to solve matrix equations. So, we prove, under natural assumptions, that quasi-Newton methods converge locally and superlinearly; the global convergence is also studied. For numerical calculations, we propose new formulations of these methods based on the matrix representation of the dyadic operator and the vectorization of matrices. Finally, we apply our results to algebraic Riccati equations.     

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.      

Block Arnoldi-based methods for large scale discrete-time algebraic Riccati equations

In the present paper, we present block Arnoldi-based methods for the computation of low rank approximate solutions of large discrete-time algebraic Riccati equations (DARE). The proposed methods are projection methods onto block or extended block Krylov subspaces. We give new upper bounds for the norm of the error obtained by applying these block Arnoldi-based processes. We also introduce the Newton method combined with the block Arnoldi algorithm and present some numerical experiments with comparisons between these methods.     

Block Arnoldi-based methods for large scale discrete-time algebraic Riccati equations

In the present paper, we present block Arnoldi-based methods for the computation of low rank approximate solutions of large discrete-time algebraic Riccati equations (DARE). The proposed methods are projection methods onto block or extended block Krylov subspaces. We give new upper bounds for the norm of the error obtained by applying these block Arnoldi-based processes. We also introduce the Newton method combined with the block Arnoldi algorithm and present some numerical experiments with comparisons between these methods.     

Alternately linearized implicit iteration methods for the minimal nonnegative solutions of the nonsymmetric algebraic Riccati equations

For the non‐symmetric algebraic Riccati equations, we establish a class of alternately linearized implicit (ALI) iteration methods for computing its minimal non‐negative solutions by technical combination of alternate splitting and successive approximating of the algebraic Riccati operators. These methods include one iteration parameter, and suitable choices of this parameter may result in fast convergent iteration methods. Under suitable conditions, we prove the monotone convergence and estimate the asymptotic convergence factor of the ALI iteration matrix sequences. Numerical experiments show that the ALI iteration methods are feasible and effective, and can outperform the Newton iteration method and the fixed‐point iteration methods. Besides, we further generalize the known fixed‐point iterations, obtaining an extensive class of relaxed splitting iteration methods for solving the non‐symmetric algebraic Riccati equations. Copyright © 2006 John Wiley & Sons, Ltd.     

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.     

Newton Generalized Hessenberg method for solving nonlinear systems of equations

In this paper, we give and analyze a Finite Difference version of the Generalized Hessenberg (FDGH) method. The obtained results show that applying this method in solving a linear system is equivalent to applying the Generalized Hessenberg method to a perturbed system. The finite difference version of the Generalized Hessenberg method is used in the context of solving nonlinear systems of equations using an inexact Newton method. The local convergence of the finite difference versions of the Newton Generalized Hessenberg method is studied. We obtain theoretical results that generalize those obtained for Newton-Arnoldi and Newton-GMRES methods. Numerical examples are given in order to compare the performances of the finite difference versions of the Newton-GMRES and Newton-CMRH methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

A modified Newton method for solving non-symmetric algebraic Riccati equations arising in transport theory

Liang Bao ^{The non-symmetric algebraic Riccati equation arising in transporttheory can be rewritten as a vector equation and the minimalpositive solution of the non-symmetric algebraic Riccati equationcan be obtained by solving the vector equation. In this paper,we apply the modified Newton method to solve the vector equation.Some convergence results are presented. Numerical tests showthat the modified Newton method is feasible and effective, andoutperforms the Newton method.}     

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.     

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.     

An improved inexact Newton method

For unconstrained optimization, an inexact Newton algorithm is proposed recently, in which the preconditioned conjugate gradient method is applied to solve the Newton equations. In this paper, we improve this algorithm by efficiently using automatic differentiation and establish a new inexact Newton algorithm. Based on the efficiency coefficient defined by Brent, a theoretical efficiency ratio of the new algorithm to the old algorithm is introduced. It has been shown that this ratio is greater than 1, which implies that the new algorithm is always more efficient than the old one. Furthermore, this improvement is significant at least for some cases. This theoretical conclusion is supported by numerical experiments.      

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.     

Versions of inexact Kleinman-Newton methods for Riccati equations

Optimal control problems involving PDEs often lead in practice to the numerical computation of feedback laws for an optimal control. This is achieved through the solution of a Riccati equation which can be large scale, since the discretized problems are large scale and require special attention in their numerical solution. The Kleinman-Newton method is a classical way to solve an algebraic Riccati equation. We look at two versions of an extension of this method to an inexact Newton method. It can be shown that these two implementable versions of Newton's method are identical in the exact case, but differ substantially for the inexact Newton method. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

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

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

Two new variants of nonlinear inexact Uzawa algorithms for saddle-point problems

Summary. In this paper, we consider some nonlinear inexact Uzawa methods for iteratively solving linear saddle-point problems. By means of a new technique, we first give an essential improvement on the convergence results of Bramble-Paschiak-Vassilev for a known nonlinear inexact Uzawa algorithm. Then we propose two new algorithms, which can be viewed as a combination of the known nonlinear inexact Uzawa method with the classical steepest descent method and conjugate gradient method respectively. The two new algorithms converge under very practical conditions and do not require any apriori estimates on the minimal and maximal eigenvalues of the preconditioned systems involved, including the preconditioned Schur complement. Numerical results of the algorithms applied for the Stokes problem and a purely linear system of algebraic equations are presented to show the efficiency of the algorithms. Received December 8, 1999 / Revised version received September 8, 2001 / Published online March 8, 2002 RID="*" ID="*" The work of this author was partially supported by a grant from The Institute of Mathematical Sciences, CUHK RID="**" ID="**" The work of this author was partially supported by Hong Kong RGC Grants CUHK 4292/00P and CUHK 4244/01P     

Solutions for the Linear-Quadratic Control Problem of Markov Jump Linear Systems

The paper is concerned with recursive methods for obtaining the stabilizing solution of coupled algebraic Riccati equations arising in the linear-quadratic control of Markovian jump linear systems by solving at each iteration uncoupled algebraic Riccati equations. It is shown that the new updates carried out at each iteration represent approximations of the original control problem by control problems with receding horizon, for which some sequences of stopping times define the terminal time. Under this approach, unlike previous results, no initialization conditions are required to guarantee the convergence of the algorithms. The methods can be ordered in terms of number of iterations to reach convergence, and comparisons with existing methods in the current literature are also presented. Also, we extend and generalize current results in the literature for the existence of the mean-square stabilizing solution of coupled algebraic Riccati equations.