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

Hung-Yuan Fan, Peter Chang Yi Weng, Eric King Wah Chu

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)245-272
Number of pages28
JournalNumerical Algorithms
Volume71
Issue number2
DOIs
Publication statusPublished - 2016 Feb 1

Fingerprint

Riccati equations
Stochastic Control
Riccati Equation
Stein Equation
Lyapunov
Lyapunov Equation
Numerical Solution
Generalized Equation
Newton-Raphson method
Modified Newton Method
Mathematical operators
Stochastic Optimal Control
Operator Matrix
Requirements
Large-scale Problems
Sparse matrix
Convergence Analysis
Data storage equipment
Error Analysis
Newton Methods

Keywords

  • Algebraic Riccati equation
  • Bilinear model order reduction
  • Generalized Lyapunov equation
  • Generalized Stein equation
  • Large-scale problem
  • Newton’s method
  • Rational Riccati equation
  • Smith method
  • Stochastic Algebraic Riccati equation
  • Stochastic optimal control

ASJC Scopus subject areas

  • Applied Mathematics

Cite this

Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control. / Fan, Hung-Yuan; Weng, Peter Chang Yi; Chu, Eric King Wah.

In: Numerical Algorithms, Vol. 71, No. 2, 01.02.2016, p. 245-272.

Research output: Contribution to journalArticle

Fan, Hung-Yuan ; Weng, Peter Chang Yi ; Chu, Eric King Wah. / Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control. In: Numerical Algorithms. 2016 ; Vol. 71, No. 2. pp. 245-272.
@article{a2ad733141a14fd0874a11f596b424cb,
title = "Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control",
abstract = "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.",
keywords = "Algebraic Riccati equation, Bilinear model order reduction, Generalized Lyapunov equation, Generalized Stein equation, Large-scale problem, Newton’s method, Rational Riccati equation, Smith method, Stochastic Algebraic Riccati equation, Stochastic optimal control",
author = "Hung-Yuan Fan and Weng, {Peter Chang Yi} and Chu, {Eric King Wah}",
year = "2016",
month = "2",
day = "1",
doi = "10.1007/s11075-015-9991-8",
language = "English",
volume = "71",
pages = "245--272",
journal = "Numerical Algorithms",
issn = "1017-1398",
publisher = "Springer Netherlands",
number = "2",

}

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

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

VL - 71

SP - 245

EP - 272

JO - Numerical Algorithms

JF - Numerical Algorithms

SN - 1017-1398

IS - 2

ER -