# Numerical Algorithms of the Discrete Coupled Algebraic Riccati Equation Arising in Optimal Control Systems

Authors: Li Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The discrete coupled algebraic Riccati equation (DCARE) has wide applications in robust control, optimal control, and so on. In this paper, we present two iterative algorithms for solving the DCARE. The two iterative algorithms contain both the iterative solution in the last iterative step and the iterative solution in the current iterative step. And, for different initial value, the iterative sequences are increasing and bounded in one algorithm and decreasing and bounded in another. They are all monotonous and convergent. Numerical examples demonstrate the convergence effect of the presented algorithms.


---

## Body

## 1. Introduction and Preliminaries

The discrete coupled Riccati equation is usually encountered in optimal control and filter design problems in control theory [1–9], particularly in the jump-linear quadratic optimal control problem [10]. Consider the following jump-linear system:(1)xk+1=Arkxk+Brkuk,0≤k≤N+,yk=Crkxk,with initial state x0=x0, r0=r0, where xk∈Rn is the plant state, uk∈Rm is the control vector, and yk∈Rq is the process output. Here, k is the time index, rk is the form process taking values in the finite set S=1,2,…,s, and rk is a finite-state discrete-time Markov chain with transition probabilities.(2)Prrk+1=jrk=i=e˜ij,1≤i,j≤s,e˜ii>0.Minimizing the cost criterion of system (1) reduces to solving coupled algebraic Riccati-like equations. After some transformation, the coupled algebraic Riccati-like equations turn the following discrete coupled algebraic Riccati equation (DCARE)(3)Pi=AiTFiAi−AiTFiBiI+BiTFiBi−1BiTFiAi+Qi,where Ai∈Rn×n is a constant matrix, Bi∈Rn×m, Qi∈Rn×n is a symmetric positive definite matrix, i∈S, Fi=Pi+∑j≠ieijPj is the coupled term, eij are real nonnegative constants defined as eij≡e˜ij/e˜ii with the properties e˜ij∈0,1, e˜ii>0, and ∑j∈Se˜ij=1, and Pi∈Rn×n denotes the symmetric positive definite solution of the DCARE. Applying Woodbury matrix equality(4)A−BD−1C−1=A−1+A−1BD−CA−1B−1CA−1,DCARE (3) turns to(5)Pi=AiTFi−1+BiBiT−1Ai+Qi.Because of the importance of Riccati equations in control theory and control engineering, a lot of research studies about Riccati equations have been devoted to this field, such as solution bounds [11–15], trace and eigenvalue bounds [16–23], and the existence and uniqueness [24–26]. Besides these results, numerical solutions of Riccati equations are very important and have been studied by many scholars [27–34] because the numerical solutions of the Riccati equations are necessary in some practical engineering, such as finding the optimal state feedback controller in the optimal control system. Especially, for the DCARE, fixed point iterative algorithms are given in [24–26]. Stein iterations are presented in [35] which are based on the properties of a Stein equation. Among these results, we find less work has been done to discuss the numerical solution of the DCARE. Considering the importance and necessity of the numerical solutions of the DCARE, we propose two algorithms to discuss the numerical solution of the DCARE.In this paper, we first propose an iterative algorithm with a parameter for solving the DCARE and prove its monotonically convergence. Second, we give an upper solution bound of the DCARE, by which another iterative algorithm is presented, and the proof of its monotonically convergence is given. For different initial values, the iterative sequences are increasing and bounded in one algorithm and decreasing and bounded in another. Last, numerical examples are given to illustrate the convergence effect of the two algorithms.We first introduce some symbol conventions.R denotes the real number field. Rn×m denotes the set of n×m real matrices. For X=xij∈Rn×n, let XT and X−1 denote the transpose and inverse of the matrix X, respectively. The inequality X>≥0 means X is a symmetric positive or semidefinite matrix, and the inequality X>≥Y means X−Y is a symmetric positive (semi-) definite matrix. The identity matrix with appropriate dimensions is represented by I.Lemma 1 (see [36]).
IfA,B∈Rn×n are symmetric positive definite matrices, then(6)A≥B,if and only ifB−1≥A−1.Lemma 2 (see [22]).
Let matricesA,X,R,Y∈Rn×n with X,Y>0, R≥0, and X>≥Y. Then,(7)ATX−1+R−1A>≥ATY−1+R−1A,with strict inequality if A is nonsingular, and X>Y.


## 2. Main Results

In [25, 26], the authors have derived several solution bounds by which iterative algorithms have been proposed, but there are many restrictions in these algorithms. In this part, we first present an iterative algorithm for DCARE (5) which do not have any restrictions.Algorithm 1.
Step 1: setPi0=Qi, Fi0=Qi+∑j≠ieijQj, 0≤ω, i=1,2,…,s.Step 2: compute(8)Pik+1=AiTFi−1k+BiBiT−1Ai+Qi,Fik+1=Pik+1+∑j=1i−1eijωPjk+1+1−ωPjk+∑j=i+1seijPjk+1,k=0,1,2,….
From Algorithm1, we get an increasing and bounded iterative sequence, which is convergent to the positive definite solution of DCARE (5).Theorem 1.
LetPi∗ be the positive definite solution of DCARE (5) and Qi>0. The iterative sequences Pik and Fik are generated by the iterative (8) with 0≤ω≤1, and then(9)Pi0≤Pi1≤Pi2≤⋯,limk⟶∞Pik=Pi∗,Fi0≤Fi1≤Fi2≤⋯,Fik≤Pi∗+∑j≠ieijPj∗.Proof.
SincePi∗ is positive definite solution of DCARE (5), then(10)Pi∗=AiTPi∗+∑j≠ieijPj∗−1+BiBiT−1Ai+Qi,so Pi∗≥Qi. Therefore,(11)Pi1=AiTFi−10+BiBiT−1Ai+Qi=AiTQi+∑j≠ieijQj−1+BiBiT−1Ai+Qi≤AiTPi∗+∑j≠ieijPj∗−1+BiBiT−1Ai+Qi=Pi∗,(12)Pi1=AiTFi−10+BiBiT−1Ai+Qi≥Qi=Pi0.
Sinceω−1≤0 and (12), we get(13)Fi0=Qi+∑j≠ieijQj=Pi0+∑j=1i−1eijωPj0+1−ωPj0+∑j=i+1seijPj0≤Pi1+∑j=1i−1eijωPj1+1−ωPj0+∑j=i+1seijPj1=Fi1=Pi1+∑j=1i−1eijPj1+ω−1Pj1−Pj0+∑j=i+1seijPj1≤Pi1+∑j=1i−1eijPj1+∑j=i+1seijPj1≤Pi∗+∑j≠ieijPj∗,
that is,(14)Fi0≤Fi1≤Pi∗+∑j≠ieijPj∗.
Suppose that(15)Pim−1≤Pim≤⋯≤Pi∗,(16)Fim−1≤Fim≤Pi∗+∑j≠ieijPj∗,m≤k,k≥1.
According to (16) and Lemma 2, we get(17)Pik+1=AiTFi−1k+BiBiT−1Ai+Qi≥AiTFi−1k−1+BiBiT−1Ai+Qi=Pik.(18)Pik+1=AiTFi−1k+BiBiT−1Ai+Qi≤AiTPi∗+∑j≠ieijPj∗−1+BiBiT−1Ai+Qi=Pi∗.
From (15), (17), (18), we get(19)Fik=Pik+∑j=1i−1eijωPjk+1−ωPjk−1+∑j=i+1seijPjk≤Pik+1+∑j=1i−1eijωPjk+1+1−ωPjk+∑j=i+1seijPjk+1=Fik+1=Pik+1+∑j=1i−1eijPjk+1+ω−1Pjk+1−Pjk+∑j=i+1seijPjk+1≤Pik+1+∑j=1i−1eijPjk+1+∑j=i+1seijPjk+1≤Pi∗+∑j≠ieijPj∗.
Thus, the proof of induction is completed. BecausePik and Fik are monotonically increasing and they are bounded, then limk⟶∞Pik and limk⟶∞Fik exist. As k⟶∞, Algorithm 1 gives(20)Pi∞=AiTFi−1∞+BiBiT−1Ai+Qi=AiTPi∞+∑j=1i−1eijωPj∞+1−ωPj∞+∑j=i+1seijPj∞−1+BiBiT−1Ai+Qi=AiTPi∞+∑j≠ieijPj∞−1+BiBiT−1Ai+Qi.
Thus,limk⟶∞Pik=Pi∗.Theorem 2.
LetPi be the positive definite solution of DCARE (5), then(21)Pi≤AiTBiBiT−1Ai+Qi.Proof.
IfG>Pi+∑j≠ieijPj, then by Lemma 1, we get(22)Pi=AiTPi+∑j≠ieijPj−1+BiBiT−1Ai+Qi≤AiTG−1+BiBiT−1Ai+Qi.
Whenλ1G=∞, G−1=null matrix; therefore, (22) changes to (21) in this case.
We can choose (21) as starting value and get the following algorithm.Algorithm 2.
Step 1: setPi0=AiTBiBiT−1Ai+Qi, Fi0=Pi0+∑j≠ieijPj0, 0≤ω, i=1,2,…,s .Step 2: compute(23)Pik+1=AiTFi−1k+BiBiT−1Ai+Qi,Fik+1=Pik+1+∑j=1i−1eijωPjk+1+1−ωPjk+∑j=i+1seijPjk+1,k=0,1,2,….
From Algorithm2, we get a decreasing and bounded iterative sequences, which is convergent to the positive definite solution of DCARE (5).Theorem 3.
LetPi∗ be the positive definite solution of DCARE (5) and Qi>0. The iterative sequences Pik and Fik are generated by iterative (23) with 0≤ω≤1, and then(24)Pi0≥Pi1≥Pi2≥⋯,limk⟶∞Pik=Pi∗,Fi0≥Fi1≥Fi2≥⋯,Fik≥Pi∗+∑j≠ieijPj∗.Proof.
According to (21) and (23), we have(25)Pi1=AiTFi−10+BiBiT−1Ai+Qi=AiTAiTBiBiT−1Ai+Qi+∑j≠ieijAjTBjBjT−1Aj+Qj−1+BiBiT−1Ai+Qi≥AiTPi∗+∑j≠ieijPj∗−1+BiBiT−1Ai+Qi=Pi∗,(26)Pi1=AiTFi−10+BiBiT−1Ai+Qi≤AiTBiBiT−1Ai+Qi=Pi0.
Sinceω−1≤0, with (25) and (26) we get(27)Fi0=Qi+∑j≠ieijQj=Pi0+∑j=1i−1eijωPj0+1−ωPj0+∑j=i+1seijPj0≥Pi1+∑j=1i−1eijωPj1+1−ωPj0+∑j=i+1seijPj1=Fi1=Pi1+∑j=1i−1eijPj1+1−ωPj0−Pj1+∑j=i+1seijPj1≥Pi1+∑j=1i−1eijPj1+∑j=i+1seijPj1≥Pi∗+∑j≠ieijPj∗,
that is,(28)Fi0≥Fi1≥Pi∗+∑j≠ieijPj∗.
Suppose that(29)Pim−1≥Pim≥⋯≥Pi∗,(30)Fim−1≥Fim≥Pi∗+∑j≠ieijPj∗,m≤k,k≥1.
According to (30) and Lemma 2, we get(31)Pik+1=AiTFi−1k+BiBiT−1Ai+Qi≤AiTFi−1k−1+BiBiT−1Ai+Qi=Pik,(32)Pik+1=AiTFi−1k+BiBiT−1Ai+Qi≥AiTPi∗+∑j≠ieijPj∗−1+BiBiT−1Ai+Qi=Pi∗.
From (29), (31), (32), we get(33)Fik=Pik+∑j=1i−1eijωPjk+1−ωPjk−1+∑j=i+1seijPjk≥Pik+1+∑j=1i−1eijωPjk+1+1−ωPjk+∑j=i+1seijPjk+1=Fik+1=Pik+1+∑j=1i−1eijPjk+1+1−ωPjk−Pjk+1+∑j=i+1seijPjk+1≥Pik+1+∑j=1i−1eijPjk+1+∑j=i+1seijPjk+1≥Pi∗+∑j≠ieijPj∗.
Thus, the proof of induction is completed. BecausePik and Fik are monotonically decreasing and they are bounded, then limk⟶∞Pik and limk⟶∞Fik exist. In a similar way as the proof of (20), as k⟶∞, Algorithm 2 gives limk⟶∞Pik=Pi∗.Remark 1.
In Algorithm2, if BiBiT is singular, we can choose a suitable G so that G−1+BiBiT−1 is nonsingular, as in Theorem 2.Remark 2.
In Algorithm1, the sequence Pik in (8) with the initial value Pi0=Qi converges monotonically to a positive definite solution of DCARE (5), and so does the sequence Pik in (23) with the initial value Pi0=AiTBiBiT−1Ai+Qi. But the two positive definite solutions may be different. Whether the positive definite solution of DCARE (5) is unique or not, a problem needs to be discussed further.Remark 3.
Wheneij=0j≠i, DCARE (5) changes to the discrete algebraic Riccati equation. And iterative sequences (8) and (23), respectively, in Algorithm 1 and Algorithm 2, become the iterative (17) and iterative (28) in [22], which means that the algorithms of the DCARE in this paper are generalizations of the discrete algebraic Riccati equation. Moreover, when ω=1, the iterative (8) and (23) are extensions on the discrete coupled algebraic Riccati equation of the work of [22].Remark 4.
In this paper, we only prove Algorithms 1 and 2 are convergent under the condition0≤ω≤1, but we can run the two algorithms with ω>1 in practical computation. And, we have faster convergence speed if appropriate parameters are selected. We will illustrate it in the following examples.


## 3. Numerical Examples

In this section, the following numerical examples are presented to show the effectiveness of our results.Example 1 (see [26]).
Consider DCARE (5) with(34)A1=0.250.150.25−0.1,A2=−0.10.20.1−0.2,B1=01,B2=10,Q1=50−30−3040,Q2=60−20−2070,e˜iji,j∈S=0.60.40.20.8,S=1,2.
Since there are two equations in the DCARE, the superiority of theω in Algorithm 1 is not obvious. So, we choose ω=1 here. After 9 steps of iteration of (8), we obtain the solution Pi of DCARE (5).(35)P19=54.782858819173867−27.163728424128180−27.16372842412818041.743512895466367,P29=60.745519196489681−21.491038392979359−21.49103839297935972.982076785958711,and the residual AiTPi9+∑j≠ieijPj9−1+BiBiT−1Ai+Qi−Pi9 is 8.246736626915663e−009.
However, it needs 47 steps of iteration for the algorithm in [26] to get the iteration solution of DCARE (5).Example 2.
Consider DCARE (5) with(36)A1=0.80.07−0.132.1,A2=1.630.12−0.181.06,A3=0.650.130.14−1.08,Q1=40−2.5−2.51.1,Q2=6−1.5−1.50.4,Q3=0.48−1.4−1.448,B1=01,B2=02,B3=03,e˜iji,j∈S=0.670.170.160.30.470.230.260.10.64,S=1,2,3.
Because the restrictions of the algorithms in [25, 26] are not met for this case, the algorithms in [25, 26] cannot work.
For Algorithm1, the steps of iteration and the residual are presented in Table 1 with different parameter ω. Although we only prove the convergence of Algorithm 1 with 0≤ω≤1, from Table 1, we find the convergence rapid is the fastest when ω is 1.8. After 31 steps of iteration of (8) with ω=1.8, we obtain the solution Pi of DCARE (5).(37)P131=1103.165003916018101.279835324595101.27983532459515.487684241437,P231=9664.052810636161713.129010075344713.12901007534453.563508057380,P331=7325.0564983527281445.9223354037061445.922335403706773.201080130236,and the residual AiTPi31+∑j≠ieijPj31−1+BiBiT−1Ai+Qi−Pi31 is 8.307893040182535e−009.Table 1
Numerical results.
ωIterationsResidualωIterationsResidual0469.0841e − 0091.8318.3079e − 0090.4448.3616e − 0092328.0616e − 0090.8426.2660e − 0094415.6463e − 0091414.7366e − 0096499.3612e − 0091.4378.0066e − 0098586.7581e − 009Example 3 (see [26]).
Consider the DCARE (5) with(38)A1=00.07−0.130.1,A2=0.030.12−0.180.06,A3=0.050.130.14−0.08,Q1,Q2,Q3,B1,B2,B3,e˜iji,j∈S and S are the same as Example 2.
For Algorithm2, since BiBi′ is singular, by choosing G=I, then Algorithm 2 can work now. After 4 steps of iteration of (23) with ω=1, we obtain the solution Pi of DCARE (5):(39)P14=40.015697705014347−2.510023450561822−2.5100234505618221.306818585337136,P24=6.030297717859115−1.387771050220626−1.3877710502206260.850999482654777,P34=6.030297717859115−1.387771050220626−1.3877710502206260.850999482654777,and the residual AiTPi4+∑j≠ieijPj4−1+BiBiT−1Ai+Qi−Pi4 is 9.070366679964081e−011.
However, it needs 18 steps of iteration for the algorithm in [26] to get the iteration solution of DCARE (5).



---

*Source: 1841582-2020-08-31.xml*