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.     

Sensitivity analysis of the algebraic Riccati equations

Summary. In this paper, some sharp perturbation bounds for the Hermitian positive semi-definite solution to an algebraic Riccati equation are developed. A further analysis for these bounds is done. This analysis shows that there is, presumably, some intrinsic relation between the sensitivity of the solution to the algebraic Riccati equation and the distance of the spectrum of the closed-loop matrix from the imaginary axis. Received December 16, 1994     

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.     

Transforming algebraic Riccati equations into unilateral quadratic matrix equations

The problem of reducing an algebraic Riccati equation XCX − AX − XD + B = 0 to a unilateral quadratic matrix equation (UQME) of the kind PX ² + QX + R = 0 is analyzed. New transformations are introduced which enable one to prove some theoretical and computational properties. In particular we show that the structure preserving doubling algorithm (SDA) of Anderson (Int J Control 28(2):295–306, 1978) is in fact the cyclic reduction algorithm of Hockney (J Assoc Comput Mach 12:95–113, 1965) and Buzbee et al. (SIAM J Numer Anal 7:627–656, 1970), applied to a suitable UQME. A new algorithm obtained by complementing our transformations with the shrink-and-shift technique of Ramaswami is presented. The new algorithm is accurate and much faster than SDA when applied to some examples concerning fluid queue models.     

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.     

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.}     

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.     

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.     

Positive semigroups and algebraic Riccati equations in Banach spaces

We generalize Wonham’s theorem on solvability of algebraic operator Riccati equations to Banach spaces, namely there is a unique stabilizing solution to \(A^*P+PA-PBB^*P+C^*C=0\) when (A, B) is exponentially stabilizable and (C, A) is exponentially detectable. The proof is based on a new approach that treats the linear part of the equation as the generator of a positive semigroup on the space of symmetric operators from a Banach space to its dual, and the quadratic part as an order concave map. A direct analog of global Newton’s iteration for concave functions is then used to approximate the solution, the approximations converge in the strong operator topology, and the convergence is monotone. The linearized equations are the well-known Lyapunov equations of the form \(A^*P+PA=-Q\), and semigroup stability criterion in terms of them is also generalized.     

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.     

A reduction technique for discrete generalized algebraic and difference Riccati equations

This paper proposes a reduction technique for the generalized Riccati difference equation arising in optimal control and optimal filtering. This technique relies on a study on the generalized discrete algebraic Riccati equation. In particular, an analysis on the eigenstructure of the corresponding extended symplectic pencil enables to identify a subspace in which all the solutions of the generalized discrete algebraic Riccati equation are coincident. This subspace is the key to derive a decomposition technique for the generalized Riccati difference equation. This decomposition isolates a “nilpotent” part, which converges to a steady-state solution in a finite number of steps, from another part that can be computed by iterating a reduced-order generalized Riccati difference equation.     

Newton's method for overdetermined systems of equations

Complexity theoretic aspects of continuation methods for the solution of square or underdetermined systems of polynomial equations have been studied by various authors. In this paper we consider overdetermined systems where there are more equations than unknowns. We study Newton's method for such a system.

     

Newton's method for fully parameterized generalized equations

ABSTRACT

In this paper, our efforts are dedicated to study the application of Newton's method to a fully parameterized generalized equation in which both single-valued and set-valued functions depend on the parameter. We established results concerning parametric properties of the associated sequences of Newton's iterates, which follows the general format of the implicit function theorem paradigm.     

On Newton's method for solving generalized equations

In this paper, we study the convergence properties of a Newton-type method for solving generalized equations under a majorant condition. To this end, we use a contraction mapping principle. More precisely, we present semi-local convergence analysis of the method for generalized equations involving a set-valued map, the inverse of which satisfying the Aubin property. Our analysis enables us to obtain convergence results under Lipschitz, Smale and Nesterov-Nemirovski's self-concordant conditions.     

A noniterative algebraic solution for Riccati equations satisfying two-point boundary-value problems

A noniterative algebraic method is presented for solving differential Riccati equations which satisfy two-point boundary-value problems. This class of numerical problems arises in quadratic optimization problems where the cost functionals are composed of both continuous and discrete state penalties, leading to piecewise periodic feedback gains. The necessary condition defining the solution for the two-point boundary value problem is cast in the form of a discrete-time algebraic Riccati equation, by using a formal representation for the solution of the differential Riccati equation. A numerical example is presented which demonstrates the validity of the approach.The authors would like to thank Dr. Fernando Incertis, IBM Madrid Scientific Center, who reviewed this paper and pointed out that the two-point boundary-value necessary condition could be manipulated into the form of a discrete-time Riccati equation. His novel approach proved to be superior to the authors' previously proposed iterative continuation method.     

The King-Werner method for solving nonsymmetric algebraic Riccati equation

For the nonsymmetric algebraic Riccati equation arising from transport theory, we concern about solving its minimal positive solution. In [1], Lu transferred the equation into a vector form and pointed out that the minimal positive solution of the matrix equation could be obtained via computing that of the vector equation. In this paper, we use the King-Werner method to solve the minimal positive solution of the vector equation and give the convergence and error analysis of the method. Numerical tests show that the King-Werner method is feasible to determine the minimal positive solution of the vector equation.     

On algebraic Riccati equations associated with M-matrices

We consider the algebraic Riccati equation for which the four coefficient matrices form an M-matrix K. When K is a nonsingular M-matrix or an irreducible singular M-matrix, the Riccati equation is known to have a minimal nonnegative solution and several efficient methods are available to find this solution. In this paper we are mainly interested in the case where K is a reducible singular M-matrix. Under a regularity assumption on the M-matrix K, we show that the Riccati equation still has a minimal nonnegative solution. We also study the properties of this particular solution and explain how the solution can be found by existing methods.