TY - JOUR

T1 - Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control

AU - Fan, Hung Yuan

AU - Weng, Peter Chang Yi

AU - Chu, Eric King Wah

N1 - Funding Information:
We thank Prof. Peter Benner and Dr. Tobias Breiten (Max Planck Institute, Magdeburg) and Prof. Valeria Simoncini (Universit? di Bologna) for providing us with the data for Examples 1 and 4. We thank a referee for pointing out the possibility of the ?transient behaviour? in general and providing us with the illustrative example in Remark 1.1 in particular. The first author has been supported by the NSC, Taiwan (Grant Number NSC 102-2115-M-003-009) and the second author by Monash Graduate and International Postgraduate Research Scholarships and a Monash Postgraduate Publication Award. Part of the work was completed when the third author visited the Shanghai Key Laboratory of Contemporary Applied Mathematics at Fudan University and the National Taiwan Normal University.

PY - 2016/2/1

Y1 - 2016/2/1

N2 - We consider the numerical solution of the generalized Lyapunov and Stein equations in ℝn$\mathbb {R}^{n}$, arising respectively from stochastic optimal control in continuous- and discrete-time. Generalizing the Smith method, our algorithms converge quadratically and have an O(n3) computational complexity per iteration and an O(n2) memory requirement. For large-scale problems, when the relevant matrix operators are “sparse”, our algorithm for generalized Stein (or Lyapunov) equations may achieve the complexity and memory requirement of O(n) (or similar to that of the solution of the linear systems associated with the sparse matrix operators). These efficient algorithms can be applied to Newton’s method for the solution of the rational Riccati equations. This contrasts favourably with the naive Newton algorithms of O(n6) complexity or the slower modified Newton’s methods of O(n3) complexity. The convergence and error analysis will be considered and numerical examples provided.

AB - We consider the numerical solution of the generalized Lyapunov and Stein equations in ℝn$\mathbb {R}^{n}$, arising respectively from stochastic optimal control in continuous- and discrete-time. Generalizing the Smith method, our algorithms converge quadratically and have an O(n3) computational complexity per iteration and an O(n2) memory requirement. For large-scale problems, when the relevant matrix operators are “sparse”, our algorithm for generalized Stein (or Lyapunov) equations may achieve the complexity and memory requirement of O(n) (or similar to that of the solution of the linear systems associated with the sparse matrix operators). These efficient algorithms can be applied to Newton’s method for the solution of the rational Riccati equations. This contrasts favourably with the naive Newton algorithms of O(n6) complexity or the slower modified Newton’s methods of O(n3) complexity. The convergence and error analysis will be considered and numerical examples provided.

KW - Algebraic Riccati equation

KW - Bilinear model order reduction

KW - Generalized Lyapunov equation

KW - Generalized Stein equation

KW - Large-scale problem

KW - Newton’s method

KW - Rational Riccati equation

KW - Smith method

KW - Stochastic Algebraic Riccati equation

KW - Stochastic optimal control

UR - http://www.scopus.com/inward/record.url?scp=84955729541&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84955729541&partnerID=8YFLogxK

U2 - 10.1007/s11075-015-9991-8

DO - 10.1007/s11075-015-9991-8

M3 - Article

AN - SCOPUS:84955729541

VL - 71

SP - 245

EP - 272

JO - Numerical Algorithms

JF - Numerical Algorithms

SN - 1017-1398

IS - 2

ER -