Iterative Methods for a Linearly Perturbed Algebraic Matrix Riccati Equation Arising in Stochastic Control

We start with a discussion of coupled algebraic Riccati equations arising in the study of linear-quadratic optimal control problems for Markov jump linear systems. Under suitable assumptions, this system of equations has a unique positive semidefinite solution, which is the solution of practical interest. The coupled equations can be rewritten as a single linearly perturbed matrix Riccati equation with special structures. We study the linearly perturbed Riccati equation in a more general setting and obtain a class of iterative methods from different splittings of a positive operator involved in the Riccati equation. We prove some special properties of the sequences generated by these methods and determine and compare the convergence rates of these methods. Our results are then applied to the coupled Riccati equations of jump linear systems. We obtain linear convergence of the Lyapunov iteration and the modified Lyapunov iteration, and confirm that the modified Lyapunov iteration indeed has faster convergence than the original Lyapunov iteration.     

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.     

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.     

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.     

Temporal Difference Methods for the Maximal Solution of Discrete-Time Coupled Algebraic Riccati Equations

In this paper, we present an iterative technique for deriving the maximal solution of a set of discrete-time coupled algebraic Riccati equations, based on temporal difference methods, which are related to the optimal control of Markovian jump linear systems and have been studied extensively over the last few years. We trace a parallel with the theory of temporal difference algorithms for Markovian decision processes to develop a -policy iteration like algorithm for the maximal solution of these equations. For the special cases in which =0 and =1, we have the situation in which the algorithm reduces to the iterations of the Riccati difference equations (value iteration) and quasilinearization method (policy iteration), respectively. The advantage of the proposed method is that an appropriate choice of between 0 and 1 can speed up the convergence of the policy evaluation step of the policy iteration method by using value iteration.     

Computation of the stabilizing solution of game theoretic Riccati equation arising in stochastic <Emphasis Type="Italic">H</Emphasis><Subscript> ∞ </Subscript> control problems

In this paper, the problem of the numerical computation of the stabilizing solution of the game theoretic algebraic Riccati equation is investigated. The Riccati equation under consideration occurs in connection with the solution of the H _∞ control problem for a class of stochastic systems affected by state dependent and control dependent white noise. The stabilizing solution of the considered game theoretic Riccati equation is obtained as a limit of a sequence of approximations constructed based on stabilizing solutions of a sequence of algebraic Riccati equations of stochastic control with definite sign of the quadratic part. The efficiency of the proposed algorithm is demonstrated by several numerical experiments.     

The matrix sign function and computations in systems

The matrix sign function has several interesting properties which form the basis of new solution algorithms for problems which occur frequently in systems and control theory applications. Presented in this paper are new algorithms, based on the matrix sign function, for the solution of algebraic matrix Riccati equations, Lyapunov equations, coupled Riccati equations, spectral factorization, matrix square roots, pole assignment, and the algebraic eigenvalue-eigenvector problem. Examples of the application of each algorithm are also presented.     

Characterization of kernel functions associated with operator algebraic Riccati equations for linear delay systems

In infinite time quadratic control and stochastic filtering problems for linear delay systems, operator algebraic Riccati equations play a very important role. However, since these are abstract operator equations, it is very useful, in analyzing their structure, to be able to characterize the kernel functions associated with the solutions of the operator Riccati equations. The kernel functions are given by the unique solution of a set of coupled differential equations. By comparing these kernel equations with similar ones available in the literature, it is shown that this characterization result is somewhat stronger than previously known results. Possible extentions to systems with control, observation, as well as state delays are also pointed out.     

Solving the algebraic Riccati equation with the matrix sign function

This paper presents some improvements to the matrix-sign-function algorithm for the algebraic Riccati equation. A simple reorganization changes nonsymmetric matrix inversions into symmetric matrix inversions. Scaling accelerates convergence of the basic iteration and yields a new quadratic formula for certain 2-by-2 algebraic Riccati equations. Numerical experience suggests the algorithm be supplemented with a refinement strategy similar to iterative refinement for systems of linear equations. Refinement also produces an error estimate. The resulting procedure is numerically stable. It compares favorably with current Schur vector-based algorithms.     

A New Approach to Linearly Perturbed Riccati Equations Arising in Stochastic Control

In this paper a linearly perturbed version of the well-known matrix Riccati equations which arise in certain stochastic optimal control problems is studied. Via the concepts of mean square stabilizability and mean square detectability we improve previous results on both the convergence properties of the linearly perturbed Riccati differential equation and the solutions of the linearly perturbed algebraic Riccati equation. Furthermore, our approach unifies, in some way, the study for this class of Riccati equations with the one for classical theory, by eliminating a certain inconvenient assumption used in previous works (e.g., [10] and [26]). The results are derived under relatively weaker assumptions and include, inter alia, the following: (a) An extension of Theorem 4.1 of [26] to handle systems not necessarily observable. (b) The existence of a strong solution, subject only to the mean square stabilizability assumption. (c) Conditions for the existence and uniqueness of stabilizing solutions for systems not necessarily detectable. (d) Conditions for the existence and uniqueness of mean square stabilizing solutions instead of just stabilizing. (e) Relaxing the assumptions for convergence of the solution of the linearly perturbed Riccati differential equation and deriving new convergence results for systems not necessarily observable. Accepted 30 July 1996     

On the numerical solution of large-scale sparse discrete-time Riccati equations

We discuss the numerical solution of large-scale discrete-time algebraic Riccati equations (DAREs) as they arise, e.g., in fully discretized linear-quadratic optimal control problems for parabolic partial differential equations (PDEs). We employ variants of Newton??s method that allow to compute an approximate low-rank factor of the solution of the DARE. The principal computation in the Newton iteration is the numerical solution of a Stein (aka discrete Lyapunov) equation in each step. For this purpose, we present a low-rank Smith method as well as a low-rank alternating-direction-implicit (ADI) iteration to compute low-rank approximations to solutions of Stein equations arising in this context. Numerical results are given to verify the efficiency and accuracy of the proposed algorithms.     

一类Riccati方程组对称自反解的两种迭代算法

针对源于Markov跳变线性二次控制问题中的一类对偶代数Riccati方程组,分别采用修正共轭梯度算法和正交投影算法作为非精确Newton算法的内迭代方法,建立求其对称自反解的非精确Newton-MCG算法和非精确Newton-OGP算法.两种迭代算法仅要求Riccati方程组存在对称自反解,对系数矩阵等没有附加限定.数值算例表明,两种迭代算法是有效的.     

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.     

Analysis and modificaton of Newton's method for algebraic Riccati equations

When Newton's method is applied to find the maximal symmetric solution of an algebraic Riccati equation, convergence can be guaranteed under moderate conditions. In particular, the initial guess need not be close to the solution. The convergence is quadratic if the Fréchet derivative is invertible at the solution. In this paper we examine the behaviour of the Newton iteration when the derivative is not invertible at the solution. We find that a simple modification can improve the performance of the Newton iteration dramatically.

     

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.     

Iterative and non-iterative methods for non-linear Volterra integro-differential equations

Iterative and non-iterative methods for the solution of nonlinear Volterra integro-differential equations are presented and their local convergence is proved. The iterative methods provide a sequence solution and make use of fixed-point theory, whereas the non-iterative ones result in series solutions and also make use of fixed-point principles. By means of integration by parts and use of certain integral identities, it is shown that the initial conditions that appear in the iterative methods presented here can be eliminated and the resulting iterative technique is identical to the variational iteration method which is derived here without making any use at all of Lagrange multipliers and constrained variations. It is also shown that the formulation presented here can be applied to initial-value problems in ordinary differential, Volterra’s integral and integro-differential, pantograph, and nonlinear and linear algebraic equations. A technique for improving/accelerating the convergence of the iterative methods presented here is also presented and results in a Lipschitz constant that may be varied as the iteration progresses. It is shown that this acceleration technique is related to preconditioning methods for the solution of linear algebraic equations. It is also argued that the non-iterative methods presented in this paper may not competitive with iterative ones because of possible cancellation errors, if implemented numerically. An analytical continuation procedure based on dividing the interval of integration into disjoint subintervals is also presented and its limitations are discussed.     

Transformations between discrete-time and continuous-time algebraic Riccati equations

We introduce a transformation between the discrete-time and continuous-time algebraic Riccati equations. We show that under mild conditions the two algebraic Riccati equations can be transformed from one to another, and both algebraic Riccati equations share common Hermitian solutions. The transformation also sets up the relations about the properties, commonly in system and control setting, that are imposed in parallel to the coefficient matrices and Hermitian solutions of two algebraic Riccati equations. The transformation is simple and all the relations can be easily derived. We also introduce a generalized transformation that requires weaker conditions. The proposed transformations may provide a unified tool to develop the theories and numerical methods for the algebraic Riccati equations and the associated system and control problems.     

Krylov subspace methods of Hessenberg based for algebraic Riccati equation

In this paper, we propose a class of special Krylov subspace methods to solve continuous algebraic Riccati equation (CARE), i.e., the Hessenberg-based methods. The presented approaches can obtain efficiently the solution of algebraic Riccati equation to some extent. The main idea is to apply Kleinman-Newton"s method to transform the process of solving algebraic Riccati equation into Lyapunov equation at every inner iteration. Further, the Hessenberg process of pivoting strategy combined with Petrov-Galerkin condition and minimal norm condition is discussed for solving the Lyapunov equation in detail, then we get two methods, namely global generalized Hessenberg (GHESS) and changing minimal residual methods based on the Hessenberg process (CMRH) for solving CARE, respectively. Numerical experiments illustrate the efficiency of the provided methods.     

Stein iterations for the coupled discrete-time Riccati equations

We consider a set of discrete-time coupled algebraic Riccati equations that arise in quadratic optimal control of Markovian jump linear systems. Two iterations for computing a symmetric (maximal) solution of this system are investigated. We construct sequences of the solutions of the decoupled Stein equations and show that these sequences converge to a solution of the considered system. Numerical experiments are given.     

Numerical approximations and regularizations of Riccati equations arising in hyperbolic dynamics with unbounded control operators

This paper provides an approximation theory for numerical computations of the solutions to algebraic Riccati equations arising in hyperbolic, boundary control problems. One of the difficulties in the approximation theory for Riccati equations is that many attractive numerical methods (such as standard finite elements) do not satisfy a uniform stabilizability condition, which is necessary for the stability of the approximate Riccati solutions. To deal with these problems, a regularizationapproximation technique, based on the introduction of special artificial terms to the dynamics of the original model, is proposed. The need for this regularization appears to be a distinct feature of hyperbolic (hyperbolic-like) equations, rather than parabolic (parabolic-like) problems where the smoothing effect of the dynamics is beneficial for the convergence and stability properties of approximate solutions to the associated Riccati equations (see [14]). The ultimate result demonstrates that the regularized, finite-dimensional feedback control yields near optimal performance and that the corresponding Riccati solution satisfies all the desired convergence properties. The general theory is illustrated by an example of a boundary control problem associated with the Kirchoff plate model. Some numerical results are provided for the given example.