Universit`
a degli Studi di Pisa
DIPARTIMENTO DI MATEMATICA Corso di Laurea Magistrale in Matematica
Tesi di laurea magistrale
Minimizing the optimality residual
for algebraic Riccati equations
Candidato
Alice Cortinovis
Relatore
Prof. Federico Poloni
Contents
Introduction 6
1 From control theory to ARE 7
1.1 Introduction on control theory . . . 7
1.2 Linear quadratic optimal control problem . . . 12
1.3 Obtaining the algebraic Riccati equation . . . 16
2 The optimality residual 21 2.1 Integral expression for the optimality residual . . . 22
2.2 Expression of the optimality residual as the solution of a Lyapunov equation . . . 24
2.3 Approximation of the optimality residual as a quadratic form . . . 25
2.4 Numerical experiments . . . 27
3 Methods for the solution of ARE 29 3.1 Newton’s method . . . 29
3.2 Schur’s method . . . 30
3.2.1 Ordering Schur’s form . . . 31
3.2.2 Exploiting the Hamiltonian structure . . . 32
3.3 Sign methods . . . 34
3.4 Comparison of methods . . . 36
4 Schur’s method 39 4.1 Residual of the Schur form and optimality residual . . . 39
4.2 Scaling . . . 40
4.2.1 Block diagonal change of variables . . . 41
4.2.2 Scalar scaling . . . 42
4.2.3 Diagonal scaling . . . 45
4.2.4 Comparison of scaling strategies . . . 45
4.2.5 Translational change of variables . . . 48
Conclusion 51
A Sylvester and Lyapunov equations 53
Introduction
In this thesis we consider a continuous-time algebraic Riccati equation (ARE) ATX+ XA + Q − XBTS−1
BX = 0 (1)
that comes from an optimal control problem of the form
min J (u, x) subject to (2)
J (u, x) = 1 2 R∞ 0 x(t) TQx(t) + u(t)TSu(t) dt; ˙x = Ax + Bu; x(0) = x0;
limt→∞u(t) = limt→∞x(t) = 0;
(3)
where A, B, Q and S satisfy suitable hypotheses.
There are different types of methods to solve Equation (1), for instance Newton’s method, Schur’s method and sign algorithms. We focus primarily on Schur’s method. The solution X of (1) is related to the stable invariant subspace of the Hamiltonian matrix H = A −B TS−1B −Q −AT .
Schur’s method works on finding this subspace instead of the solution X directly. The usual measures of the accuracy of a computed solution are the “equation residual” obtained by plugging the computed value of X into (1) and taking a norm (or a normalized version of this quantity) and the “subspace residual” obtained by seeing how far is the computed subspace from being invariant. In our case, we want to analyze the residual coming from the original control problem (2), which we call “optimality residual”, defined as
J (computed solution) − J (exact solution). (4) We derive an expression for this residual and a way to compute it from the equation residual and the data of the problem, up to first order corrections.
In general, the accuracy of Schur’s method can be improved by scaling the matrix H before doing the computations, i.e. by substituting H with SHS−1 for a suitable
matrix S. We are interested in studying scaling strategies in order to reduce the optimality residual. In particular, we look for symplectic matrices S of the form
S =B 0
0 B−T
. (5)
The thesis is organized as follows.
In Chapter 1, we introduce some definitions on control theory, state the problem (2) with all the necessary hypotheses and obtain the ARE, proving that the solution we are looking for exists and is unique.
Chapter 2 is devoted to the computation of the optimality residual: as the definition (4) involves an integral depending on the exact solution, we first convert the integral to a Lyapunov equation and then approximate the solution to obtain a computable estimate.
Chapter 3 contains a overview of the three methods mentioned above for solving AREs and a comparison of the performances of these methods with respect to the equation residual and optimality residual.
In Chapter 4 we first analyze the relation between the residual of Schur’s method and the optimality residual, and we see how this quantity changes by scaling with a matrix S of the form (5). Then we propose and compare several scaling strategies for Schur’s method, i.e. different choices of the matrix B in (5).
Chapter 1
From control theory to ARE
We begin our presentation with an introduction to control theory and the au-tonomous linear quadratic control problem. We will state and prove Pontryagin’s maximum principle that allows us to characterize the solution of such problem and we will see how to express the solution of the problem in terms of the solution of a continuous-time algebraic Riccati equation. For this presentation we follow [7; 11; 13; 14].
1.1
Introduction on control theory
Suppose we have a linear system subject to equations ˙x(t) = Ax(t),
where x(t) ∈ Rn is a vector that describes the status of the system at time t and
A ∈ Rn×n is a matrix. Suppose that we can add a control function u(t) : [0, +∞) → Rm
so that the new equations are
˙x(t) = Ax(t) + Bu(t),
for a suitable matrix B ∈ Rn×m. We are interested in finding u in such a way that
the resulting system is stable. Let us consider an example.
Example 1 ([13]). Consider a pendulum close to the unstable equilibrium position, i.e. a rigid stick of length `, where the lower end is fixed and the pendulum is forced to oscillate in the xy plane. The status of the pendulum at time t is given by the angle θ formed with the y axis (θ = 0 when the pendulum is in the unstable equilibrium position) and the angular velocity ˙θ:
x(t) =x1(t) x2(t) =θ(t)˙θ(t) . 7
Its movement is subject to the differential equation (assuming that the pendulum has mass equal to 1):
˙x(t) = ˙x1(t) ˙x2(t) = ˙θ(t) ¨ θ(t) = x2 gsin x1 .
Linearizing around the unstable equilibrium position, we have that ˙x(t) ≈ x2 gx1 , so denoting A =0 1 g 0 we have ˙x ≈ Ax.
The system is unstable because the matrix A has eigenvalues ±√g so it has an eigenvalue with positive real part.
Let us suppose that there is a motor that can apply a torque u(t) to the pendu-lum. Then the equations of motions of the system, linearized around the unstable equilibrium position, are
˙x1 ˙x2 ≈ x2 gx1 +0 u .
In a more compact form, denoting by B = 0 1
, the system’s equations can be written as
˙x = Ax + Bu.
Adding the motor to the system we can enforce stability, in particular we can choose a control function of the form
u(t) = F · x(t),
where F is a fixed matrix. Indeed, let F =f1 f2, so that
˙x = Ax + Bu = (A + BF )x. Stability depends on the eigenvalues of
A+ BF = 0 1 g+ f1 f2 , whose characteristic polynomial is
p(λ) = λ2− λf2− (g + f1).
With an appropriate choice of f1 and f2 we can obtain an arbitrary pair of
1.1. INTRODUCTION ON CONTROL THEORY 9 In this case we can obtained what is called a feedback control, i.e. a control function of the form u(t) = F x(t) where F is a fixed matrix. Thus the control depends only on the current state of the system (and not from previous history or other variables), and the system’s equations are
˙x = (A + BF )x.
Definition 2. A matrix M is stable if all its eigenvalues have negative real part. Equivalently, M is stable if the associated system ˙x = M x is stable.
Therefore, we are looking for matrices F such that A + BF is stable. It is not always possible to stabilize a system with a feedback control.
Example 3 ([7]). Consider matrices A ∈ Rn×n and B ∈ Rn×m and a system ˙x =
Ax+ Bu. Suppose that A and B have the block form A=A11 A12 0 A22 , B =B1 0 .
If we look for a feedback control associated to a matrix F =F1 F2, we need the
matrix
A+ BF = A11+ B1F1 A12+ B1F2
0 A22
to be stable, and this is impossible if A22 has some eigenvalues with positive real
part.
In fact, this “block structure” is the only obstruction to controllability. Lemma 4 ([7]). The following conditions are equivalent.
1. The space K(A, B) generated by the columns of (B, AB, A2B, . . . , AkB, . . .)
is not the whole Rn.
2. There exists a nonsingular matrix K such that A = KA11 A12 0 A22 K−1 and B = KB1 0 .
Proof. 1 ⇒ 2) Assume that K(A, B) 6= Rn. Let M
1 be a matrix whose columns
form a basis of K(A, B), M1 will be of size n × m with m < n. We complete it to
an invertible matrix M =M1 M2. Then
M−1B =B1 0
Moreover, the space K(A, B) is A-invariant, i.e. if v ∈ K(A, B) then also Av ∈ K(A, B), so M−1AM =A11 A12 0 A22 . 2 ⇒ 1) If A = KA11 A12 0 A22 K−1 and B = KB1 0
then AiB takes the following
form: AiB = K∗ ∗ 0 ∗ K−1· K∗ 0 = K∗ 0 , so the subspace K(A, B) is not the whole Rn.
Definition 5. The matrix pair (A, B) is controllable if
K(A, B) := Span(B, AB, A2B, . . . , AkB, . . .) = Rn.
If (A, B) is controllable then there exists a feedback control u = F x for the system ˙x = Ax + Bu. However, controllability is not a necessary condition: recalling the example above, if (A11, B1) is controllable and the matrix A22 is already stable, the
whole system can be stabilized. This motivates the following definition.
Definition 6. The matrix pair (A, B) is stabilizable if there exists a nonsingular matrix K such that
(KAK−1, KB) = A11 A12 0 A22 ,B1 0
where (A11, B1) is controllable and A22 is stable.
Stabilizability is a necessary and sufficient condition for the existence of a feed-back control. We now prove some properties of controllable and stabilizable pairs that will be useful in the derivation of the algebraic Riccati equation.
Theorem 7 (Kalman decomposition, [11]). For every matrix pair (A, B) there exists a nonsingular matrix M such that M−1AM = A11 A12
0 A22 and M−1B = B1 0 , where (A11, B1) is a controllable pair.
Proof. Arguing as in the first implication in the proof of Lemma 4, we find the decomposition M−1AM = A11 A12 0 A22 and M−1B = B1 0 ; it remains to prove that (A11, B1) is controllable. This follows from the fact that if we partition M =
M1 M2 conformably with A and B then M1 is a basis for the subspace
Span(M1B1, M1A11B1, M1A211B1, . . .) = M1Span(B1, A11B1, A211B1, . . .)
so the subspace Span(B1, A11B1, A211B1, . . .) has the same dimension as the rank of
1.1. INTRODUCTION ON CONTROL THEORY 11 Proposition 8 ([11]). Let A ∈ Rn×n and B ∈ Rn×m. The following conditions are
equivalent:
1. (A, B) is controllable; 2. ker(BT) ∩ ker(λI − A)∗
= {0} for all λ ∈ C; 3. RankλI − A, B = n for all λ ∈ C. Proof. Condition (2) is equivalent to (3) because
ker(BT) ∩ ker(λI − A)∗ = ker BT (λI − A)∗
= (Im(B) + Im(λI − A))⊥.
Now we prove that condition (1) implies (2). If there exists y ∈ Cn\{0} such
that y ∈ ker(BT) ∩ ker(λI − A)∗ then in particular y∗B = 0 and y∗Ar = λry∗ for
every r ∈ N. Hence
y∗B AB A2B · · · = 0,
so the matrixB AB A2B · · · must have rank less than n.
Finally, we prove that condition (2) implies condition (1). If RankB AB A2B · · · 6= n,
then there exists z ∈ Cn\{0} such that
z∗ArB = 0 for every r ∈ N.
Let ψ(x) be a polynomial of minimum degree such that z∗ψ(A) = 0. Let λ be a
root of ψ (which exists, because z 6= 0 so ψ cannot be constant) and let us write ψ(x) = ϕ(x) · (x − λ), where ϕ(x) is a polynomial of degree less than ψ(x). Let y∗ = z∗ϕ(A). By minimality of ψ, we have that y 6= 0. We want to prove that
y ∈ker(BT) ∩ ker(λI − A)∗. (1.1)
We have that
y∗(A − λI) = z∗ϕ(A)(A − λI) = z∗ψ(A) = 0; moreover, as z∗ArB = 0 for every r ∈ N we obtain
y∗B = z∗ϕ(A)B = 0. Hence, Equation (1.1) is verified.
Proposition 9 ([11]). The matrix pair (A, B) is stabilizable if and only if the matrix λI − A, B has rank n for every λ ∈ C with nonnegative real part.
Proof. Without loss of generality we can assume that A and B are in the form given by Kalman decomposition (Theorem 7), so
A=A1 A2 0 A3 and B =B1 0 , where (A1, B1) is controllable. By Proposition 8, we have that
RankλI − A1, B1 = p,
where p is the dimension of block A1. Hence,
RankλI − A, B = RankλI − A1 −A2 B1
0 λI − A3 0
,
so the rank is n for every λ ∈ C with nonnegative real part if and only if A3 has
no eigenvalues with nonnegative real part, i.e. if and only if A3 is stable, which is
equivalent to (A, B) stabilizing.
Lemma 10 ([11]). If C is positive definite then (A, B) is controllable if and only if (A, BCBT) is controllable.
Proof. The space K(A, B) is the smallest A-invariant subspace that contains Im(B). Hence, it is sufficient to prove that Im(B) = Im(BCBT), or equivalently that
ker(BT) = ker(BCBT).
The inclusion ker(BT) ⊆ ker(BCBT) is trivial. For the converse inclusion, let
x ∈ ker(BCBT). Then xTBCBTx = 0. Let C1/2 be the positive definite square
root of the positive definite matrix C, then we can rewrite the previous equation as (xTBC1/2)(xTBC1/2)T = 0,
from which we conclude that
C1/2BTx= 0,
so BTx= 0 because C1/2 is nonsingular. Therefore, we have obtained that
ker(BCBT) ⊆ ker(BT).
1.2
Linear quadratic optimal control problem
If the matrix pair (A, B) is stabilizable, there are many choices of F such that the matrix A + BF is stable. Therefore, we introduce a cost functional:
J (u, x) = 1 2
Z ∞
0
x(t)TQx(t) + u(t)TSu(t) dt,
where Q and S are two suitable positive definite matrices of sizes n × n and m × m, respectively. Intuitively, matrix S indicates the cost associated to the control, while matrix Q measures how far is the system from the equilibrium position.
The autonomous linear quadratic optimal control problem can then be stated in this way:
1.2. LINEAR QUADRATIC OPTIMAL CONTROL PROBLEM 13 Problem 11 ([14]). Let A and B be such that the pair (A, B) is stabilizable. Solve
minnJ (u, x) | ˙x = Ax + Bu, x(0) = x0, lim
t→∞u(t) = limt→∞x(t) = 0
o .
The linear part of the problem is the constraint ˙x = Ax + Bu, the quadratic part involves the cost functional.
The main ingredient for solving the problem through the solution of a continuous-time algebraic Riccati equation is the following theorem.
Theorem 12 (Pontryagin’s maximum primciple, [14]). Let u∗ and x∗ be the
solu-tions to Problem 11. Then there exists a function µ: R → Rn such that x
∗(t), u∗(t)
and µ(t) satisfy the boundary value problem A 0 B Q AT 0 0 BT S · x(t) µ(t) u(t) = I 0 0 0 −I 0 0 0 0 · ˙x(t) ˙µ(t) ˙u(t) (1.2)
with boundary conditions x(0) = x0, limt→∞u(t) = limt→∞µ(t) = limt→∞x(t) = 0.
Proof. Consider the Hamiltonian function
H(z, µ, u) = x(t)TQx(t) + u(t)TSu(t) + 2µ(t)T(Ax(t) + Bu(t)).
Then we have that J (u) = 1 2 Z ∞ 0 (H(x, µ, u) − 2µ(t)T ˙x(t)) dt, J (u∗) = 1 2 Z ∞ 0 (H(x∗, µ, u∗) − 2µ(t)T ˙x∗(t)) dt; so J (u) − J (u∗) = 1 2 Z ∞ 0 (H(x, µ, u) − H(x∗, µ, u∗)) dt + Z ∞ 0 µ(t)T( ˙x ∗(t) − ˙x(t)) dt. (1.3) Now consider a perturbation of the control u∗ of the form
u(t) = u∗(t) + εν(t).
Then, the solution x(t) of the system ( ˙x(t) = Ax(t) + Bu(t) x(0) = x0 is x(t) = exp(At)x0+ Z t 0 exp(A(t − s))B(u∗(s) + εν(s)) ds = x∗(t) + ε Z t 0 exp(A(t − s))Bν(s) ds.
Let ϕ(t) =Rt
0exp(A(t − s))Bν(s) ds, then we have that
x(t) = x∗(t) + εϕ(t), ϕ(0) = 0.
Substituting these values of x and u in Equation (1.3) we obtain that H(x, µ, u) − H(x∗, µ, u∗)
= ε ϕ(t)T(Qx(t) + ATµ(t)) + ν(t)T(Su∗(t) + BTµ(t)) + O(ε2).
Moreover, by integration by parts we obtain that Z ∞ 0 µ(t)T( ˙x ∗(t) − ˙x(t)) dt = −ε Z ∞ 0 µ(t)Tϕ(t) dt = ε˙ Z ∞ 0 ˙µ(t)Tϕ(t) dt.
As a consequence, we have that J (u) − J (u∗) = ε Z ∞ 0 (ϕ(t)T(Qx ∗(t) + ATµ(t) + ˙µ) + ν(t)T(Su ∗(t) + BTµ(t))) dt + O(ε2).
We set µ(t) such that (
− ˙µ(t) = Qx∗(t) + ATµ(t)
limt→∞µ(t) = 0,
and this is in fact the second equation of the boundary value problem (1.2). As we must have J (u) − J (u∗) ≥ 0 for every choice of ε, we need to have that
Z ∞
0
ν(t)T(Su
∗(t) + BTµ(t)) dt = 0.
As this must hold for any piecewise continuous function ν(t) such that ν(0) = 0, we need to have
Su∗(t) + BTµ(t) = 0,
which is the third equation of (1.2). The first equation of (1.2) is the constraint ˙x = Ax + Bu.
The converse of Theorem 12 is also true.
Theorem 13 ([14]). Let x, µ, u such that x(0) = x0,limt→∞µ(t) = limt→∞x(t) = 0,
the system ((1.2)) holds and assume that S and Q are positive semidefinite. Then J (˜u,x) ≥ J (u, x) for every ˜˜ u,x such that ˙˜ x(t) = A˜˜ x(t) + B ˜u(t) and ˜x(0) = x0.
Proof. Let
φ(s) = J (sx + (1 − s)˜x, su+ (1 − s)˜u).
The theorem is proved if we show that φ(s) has a minimum in s = 1. As φ is quadratic in s, it is sufficient to prove that
1.2. LINEAR QUADRATIC OPTIMAL CONTROL PROBLEM 15 1. dφ
ds(1) = 1;
2. d2φ
ds2(1) ≥ 0.
We compute the first derivative of φ(s): dφ ds s=1 = d ds Z ∞ 0 ((sx(t)T + (1 − s)˜x(t)T)Q(sx(t) + (1 − s)˜x(t)
+ (su(t)T + (1 − s)˜u(t)T)S(su(t) + (1 − s)˜u(t))) dt s=1 = Z ∞ 0 ((x(t)T − ˜x(t)T)Q(sx(t) + (1 − s)˜x(t)) + (sx(t)T + (1 − s)˜x(t)T)Q(x(t) − ˜x(t)) + (u(t)T − ˜u(t)T)S(su(t) + (1 − s)˜u(t)) + (su(t)T + (1 − s)˜u(t)T)S(u(t) − ˜u(t)) dt
s=1 = Z ∞ 0 ((x(t)T − ˜x(t)T)Qx(t) + x(t)TQ(x(t) − ˜x(t))
+ (u(t)T − ˜u(t)T)Su(t) + u(t)TS(u(t) − ˜u(t))) dt.
Using the equations in the hypothesis we get that x(t)TQx(t) = −x(t)T ˙µ(t) − x(t)TATµ(t) = −x(t)T ˙µ(t) + u(t)TBTµ(t) − ˙x(t)Tµ(t) = −x(t)T ˙µ(t) − u(t)TSu(t) − ˙x(t)Tµ(t), and similarly ˜ x(t)TQx(t) = −˜x(t)T ˙µ(t) − ˜u(t)TSu(t) − ˙˜x(t)Tµ(t). Then we have that
dφ ds s=1 = Z ∞ 0 (−x(t)T ˙µ(t) − ˙x(t)Tµ(t) + ˜x(t)T ˙µ(t) + ˙˜x(t)Tµ(t)) dt = (˜x(t)T − x(t)T)µ(t) ∞ 0 ,
which is 0 because ˜x(0) = x(0) = x0 and limt→∞µ(t) = limt→∞x(t) = 0.˜
The second derivative is d2φ dt2 t=1= Z ∞ 0 x(t) − ˜x(t) u(t) − ˜u(t) T Q 0 0 S x(t) − ˜x(t) u(t) − ˜u(t) dt,
which is nonnegative because the matrix Q 0 0 S
is positive semidefinite, so the function we are integrating is always greater or equal than 0.
1.3
Obtaining the algebraic Riccati equation
In this section we will show that the solution of the autonomous linear quadratic con-trol problem is linked to a solution of the continuous-time algebraic Riccati equation (ARE)
ATX+ XA + Q − XGX = 0. (1.4)
From now on, we will assume that the hypotheses of Theorem 12 are satisfied, i.e. the matrices Q and S are positive definite and the matrix pair (A, B) is stabilizable.
Writing explicitly the three equations given by Theorem 12, we get ˙x(t) = Ax(t) + Bu(t); − ˙µ(t) = Qx(t) + ATµ(t); BTµ(t) + Su(t) = 0. As S is nonsingular, we obtain that
u(t) = −S−1BTµ(t).
Substituting this in the other two equations we get the equivalent system ˙x ˙µ = A −BS −1BT −Q −AT x µ . We denote by G = BS−1BT and H = A −G −Q −AT
so the system becomes ˙x ˙µ = Hx µ . (1.5)
Before proceding, we introduce the definition of Hamiltonian matrix and some basic properties about its eigenvalues.
We will denote J = 0 I −I 0
. We observe that J−1 = JT = −J .
Definition 14. A matrix H is Hamiltonian if J H = (J H)T.
Lemma 15. If H is Hamiltonian and λ is an eigenvalue of H, then −¯λ is also an eigenvalue of H.
Proof. Let v ∈ C2na right eigenvector, such that Hv = λv. Multiplying by J we get
that J Hv = λ(J v). As J H is Hamiltonian, we have that HTJTv = λ(J v), that
is HT(J v) = −λ(J v). Taking the conjugate transpose of the previous equation we
obtain that
(J v)∗H = −¯λ(J v)∗,
1.3. OBTAINING THE ALGEBRAIC RICCATI EQUATION 17
The matrix H = A−Q −A−GT
for which we need to compute the stable invariant subspace in order to solve Equation (1.4) is Hamiltonian.
As H is a real matrix, if λ is an eigenvalue of H then ¯λ is also an eigenvalue of H of the same algebraic and geometric multiplicity as λ. Thanks to the previous lemma, if λ is an eigenvalue, so are −λ, ¯λ and −¯λ. If we prove that there are no pure imaginary eigenvalues, we conclude that there are exactly n eigenvalues with positive real part and n eigenvalues with negative real part. In this case, the stable subspace of H, i.e. the subspace associated to the eigenvalues with negative real part, has dimension n. Moreover, it is H-invariant.
Theorem 16 ([11]). If G and Q are positive semidefinite and the matrix pairs (A, G) and (AT, Q) are stabilizable, then H = A −G
−Q −AT
does not have pure imaginary eigenvalues.
Proof. By contradiction, assume that H has a pure imaginary eigenvalue. Then there exist a vectorx1
x2
∈ C2n\{0} and a real number λ such that
Hx1 x2 = A−Q −A−GT x1 x2 = iλx1 x2 . Writing the equations explicitly we have that
(
Ax1− Gx2 = iλx1;
−Qx1 − ATx2 = iλx2.
Multiplying the first equation of the system by x∗
2 we have that
x∗2Ax1− x∗2Gx2 = iλx∗2x1 ⇔ x∗2Gx2 = x∗2Ax1− iλx∗2x1.
Transposing this equation, we have that x∗2Gx2 = x∗1A
Tx
2+ iλx∗1x2. (1.6)
Multiplying the second equation of the system by x∗
1 we obtain that
x∗1Qx1 = −x∗1A Tx
2− iλx∗1x2. (1.7)
Comparing Equations (1.6) and (1.7) and recalling that both Q and G are positive semidefinite, we conclude that
x∗2Gx2 = −x∗1Qx1 = 0.
Therefore, we have that (
x∗1(AT + iλI) = 0;
As (AT, Q) is stabilizable, the matrix AT + iλI, Q has rank n by Proposition 9,
so x1 = 0.
Similarly, we have that (
x∗2G= 0;
x∗2(iλI − A) = 0.
As (A, G) is stabilizable, the matrix iλI − A, G has rank n by Proposition 9, so x2 = 0 and we reached a contradiction. We conclude that H does not have pure
imaginary eigenvalues.
In our case the hypotheses of Theorem 16 are satisfied, so our matrix H has no pure imaginary eigenvalues. Indeed:
• Q is positive definite by hypothesis;
• G = BS−1BT is positive semidefinite because S is positive definite;
• (A, G) is stabilizable: S is positive definite by hypothesis, hence invertible; thus, the matrix pair (A, S−1) is controllable because Span(S−1
) = Rn; by
Theorem 10 (A, BS−1BT) = (A, G) is controllable, hence stabilizable;
• (AT, Q) is stabilizable because Q is positive definite, thus invertible.
As a consequence, the stable invariant subspace of H has dimension n. If there exists a basis of this subspace of the form I
X
, then there exists a stable matrix M such that
H I X = I X M.
Rewriting the last system of equations explicitly, we obtain that (
M = A − GX;
ATX+ XA + Q − XGX = 0.
The second equation is called continuous-time algebraic Riccati equation (ARE). A solution to Equation (1.4) is called stabilizing if the matrix A − GX is stable.
In this case, the solution of the original problem (1.5) can be expressed as x(t) µ(t) = I X exp(t(A − GX))x0.
We will prove that with our hypotheses there is a basis of the stable invariant subspace of the form I
X
1.3. OBTAINING THE ALGEBRAIC RICCATI EQUATION 19
Remark 17. If Span I X
is the stable (right) invariant subspace of matrix H, then X must be symmetric. Indeed, by the definition of Hamiltonian matrix we have that HTJ = −J H, so if H I X = I X M where M is stable, then
HT J I X = −J H I X = J I X (−M ). We obtain that J I X =−X I
is the anti-stable left invariant subspace of matrix H. As left and right eigenvectors relative to different eigenvalues are orthogonal, we have that −XT I I X = 0, i.e. X = XT so X is symmetric.
We will see in Chapter 3 that there exists a decomposition of H in Hamiltonian Schur form (see theorems 32, 33)
UTHU = U1T U2T −UT 2 U1T A −G −Q −AT U1 −U2 U2 U1 =T V 0 −TT = T , (1.8)
where T is a stable quasi-upper triangular matrix, the matrix U is orthogonal and has the special form U =U1 −U2
U2 U1
. For now, we give this for granted. The stable invariant subspace of H then is SpanU1
U2
. This means that there exists a stable matrix M such that
HU1 U2 =U1 U2 M. (1.9)
If U1 is invertible, we can find the basis
I X =U1 U2
U1−1 and we obtain the solution to our problem.
Theorem 18 ([7]). U1 is invertible.
Proof. By contradiction, assume that U1 is singular. Then there exists a vector
w ∈ Rn\{0} such that U1w = 0. As the matrix U is orthogonal, we have that
UT
2 U1 = U1TU2. Therefore, we have that
−wTUT 2 GU2w=wTU2T 0 A −G −Q −AT 0 U2w = wT UT 2 −U1T U1 U2 M w = 0.
Thus, GU2w= 0. Recalling that G = BS−1BT, we also obtain that
BTU2w= 0.
From Equation (1.8) we get that
AU1w − GU2w= U1T w,
so U1(T w) = 0. Hence, ker(U1) is T -invariant. Every T -invariant subspace is
asso-ciated to at least an eigenvalue and a corresponding eigenvector of T , so there exist λ ∈ σ(T ) (thus λ has negative real part) and z ∈ ker(U1)\{0} such that T z = λz.
From Equation (1.8) we get that
−QU1z − ATU2z = U2T z, so (AT + λI)(U2z) = 0.
We have that U2z is not zero because the matrix
U1
U2
has full rank. Hence, U2z
is an eigenvalue of AT corresponding to the eigenvector −λ, which has positive real
part. As z ∈ ker(U1), we have that BTU2z = 0. Therefore, the rank of the matrix
(−λ)I − A, B
is less than n because z 6= 0 is in the (left) kernel. By Proposition 9, we conclude that (A, B) is not stabilizable, hence we reached a contradiction.
Chapter 2
The optimality residual
When we solve the algebraic Riccati equation (1.4), we need a measure of the error to know how “good” the approximation of the solution is. Usual error estimates involve the equation residual and the subspace residual, which we define below. We are interested in finding a residual measure that is connected to the linear quadratic control problem 11.
Let us recall the setting. Let X be the stabilizing solution of the algebraic Riccati equation ATX+ XA − XGX + Q = 0, denote M = A − GX and recall that
G= BS−1BT. Let F = −S−1BTX, so that the solutions to the associated problem
11 are
(
x(t) = exp(M t)x0,
u(t) = F x(t).
Now assume that we have a computed solution ˜X = X + ∆X, associated to matrices ˜F = −S−1BTX, ˜˜ M = A + B ˜F = A − G ˜X, and to approximate solutions
to 11 ( ˜ x(t) = exp( ˜M t)x0, ˜ u(t) = ˜Fx(t).˜ Definition 19. The equation residual is
R= Q + ATX˜ + ˜XA − ˜XG ˜X. Definition 20. Let ˜Q1 = orth
I ˜ X
. The subspace residual is computed as Ressubspace = kH ˜Q1− ˜Q1( ˜QT1H ˜Q1)k2.
Taking into consideration the linear quadratic optimal control problem from which we derived the algebraic Riccati equation, we would like to measure the resid-ual in the following way.
Definition 21. We will call optimality residual the quantity J (˜u) − J (u).
In this chapter we study the optimality residual, its relation with the equation residual, and we discuss a way to find a first-order approximation.
2.1
Integral expression for the optimality residual
This section is devoted to the proof of the following theorem. Theorem 22. We have this expression for the optimality residual:
J (˜u) − J (u) = 1 2
Z ∞
0
(˜x(t) − x(t))TRx(t) dt.
The proof of this theorem reuses many ideas from the proof of Theorem 12. In particular, we use the Hamiltonian function and we take care of the second-order terms in the integrals. At the end we make a different choice of the function µ(t). For the sake of brevity, in the following we omit the dependency of the functions from t.
Proof. Let us introduce the Hamiltonian function
H(x, µ, u) = xTQx+ uTSu+ 2(Ax + Bu)Tµ.
We have the constraint that ˙x = Ax + Bu so we can write, equivalently, H(x, µ, u) = xTQx+ uTSu+ 2 ˙xTµ.
Then the optimality residual can be written as J (˜u) − J (u) = 1 2 Z ∞ 0 (˜xTQ˜x+ ˜uTSu − x˜ TQx − uTSu) dt = 1 2 Z ∞ 0 H(˜x, µ,u) − H(x, µ, u) − 2 ˙˜˜ xTµ+ 2 ˙xTµ dt = 1 2 Z ∞ 0 (H(˜x, µ,u) − H(x, µ, u)) dt −˜ Z ∞ 0 ˙˜xTµ − ˙xTµ dt.
We now consider the second integral: integrating by parts and recalling that x(0) = ˜
x(0) = x0 and x, ˜x →0 for t → ∞ we get
Z ∞ 0 ˙˜xTµ − ˙xTµ dt = − Z ∞ 0 (˜x − x)T ˙µ dt.
Therefore the optimality residual is J (˜u) − J (u) = 1 2 Z ∞ 0 (H(˜x, µ,u) − H(x, µ, u)) dt +˜ Z ∞ 0 (˜x − x)T ˙µ dt = 1 2 Z ∞ 0 (˜xTQ˜x+ ˜uTSu˜+ 2(A˜x+ B ˜u)Tµ − xTQx − uTSu − 2(Ax + Bu)Tµ+ 2(˜x − x)T ˙µ) dt = 1 2 Z ∞ 0 ((˜xTQ˜x − xTQx) + (˜uTSu − u˜ TSu) + 2(˜x − x)TATµ + 2(˜u − u)TBTµ+ 2(˜x − x)T ˙µ) dt.
2.1. INTEGRAL EXPRESSION FOR THE OPTIMALITY RESIDUAL 23 We denote by ϕ = ˜x − x and ν = ˜u − u. We want to express the optimality residual in two ways, first as a function of ˜u and ˜x plus a correction depending on ϕand ν, then as a function of u and x plus a correction depending on ϕ and ν. To this aim, using the symmetry of Q we observe that
˜
xTQ˜x − xTQx= ϕTQ˜x − ϕTQϕ+ ˜xTQϕ= 2ϕTQ˜x − ϕTQϕ
= ϕTQx+ ϕTQϕ+ xTQϕ = 2ϕTQx+ ϕTQϕ.
Similarly, using the symmetry of S we have that ˜
uTSu − u˜ TSu= νTSu − ν˜ TSν+ uTSν = νTSu − ν˜ TSν
= νTSu+ νTSν+ uTSν = νTSu+ νTSν.
Then we can write J (˜u) − J (u) = Z ∞ 0 ϕT(Q˜x+ ATµ+ ˙µ) dt + Z ∞ 0 νT(S ˜u+ BTµ) dt −1 2 Z ∞ 0 (ϕTQϕ+ νTSν) dt = Z ∞ 0 ϕT(Qx + ATµ+ ˙µ) dt + Z ∞ 0 νT(BTµ+ Su) dt + 1 2 Z ∞ 0 (ϕTQϕ+ νTSν) dt.
Now we will make two appropriate choices of µ(t) in order to obtain two expres-sions for the optimality residual, from which the desired result will follow.
Choosing µ(t) = ˜Xx(t), we get
• S ˜u+ BTµ= (S ˜F + BTX)˜˜ x= (S(−S−1BTX) + B˜ TX)˜˜ x= 0;
• Q˜x+ATµ+ ˙µ = (Q+ATX˜+ ˜X(A+B ˜F))˜x= (Q+ATX˜+ ˜XA− ˜XG ˜X)˜x= R˜x
so we have the first expression: J (˜u) − J (u) = Z ∞ 0 ϕTRx˜dt − 1 2 Z ∞ 0 (ϕTQϕ+ νTSν) dt. (2.1)
On the other hand, choosing µ(t) = Xx(t) we get
• Su + BTµ= (SF + BTX)x = (−SS−1BTX+ BTX)x = 0;
• Qx+ATµ+ ˙µ = (Q+ATX+X(A+BF ))x = (Q+ATX+XA+XB(−S−1BTX))x =
(Q + ATX+ XA − XGX)x = 0 because X is the exact solution of the Riccati
equation.
As a consequence, we get the second expression for the optimality residual: J (˜u) − J (u) = 1
2 Z ∞
0
(ϕTQϕ+ νTRν) dt. (2.2)
Comparing equations (2.1) and (2.2) we get that J (˜u) − J (u) = 1 2 Z ∞ 0 ϕ(t)TRx(t) dt =˜ 1 2 Z ∞ 0 (˜x(t) − x(t))TRx(t) dt.˜
The equation and subspace residuals can be easily computed once we have the computed solution ˜X. On the contrary, the expression for the optimality residual that we obtained in Theorem 22 is not easily computable because the exact solution x(t) is needed, and moreover we have to compute an integral. The plan is now to get rid of the integral sign and of the exact solution. We will see in the next section that the optimality residual can be expressed as the solution of a Lyapunov equation, still involving the exact solution X. In the subsequent section, we will show how to get a first-order approximation of the optimality residual in order to eliminate the necessity of X.
2.2
Expression of the optimality residual as the
solution of a Lyapunov equation
Now the plan is to find a more computable way to express the optimality residual. We will first write it as the solution of a Lyapunov equation. Since the coefficients still depend on the exact solution X, we will then find a first-order approximation by linearizing the previous equation.
Thanks to Lemma 54 we can write J (˜u) − J (u) = 1 2 Z ∞ 0 (˜x(t) − x(t))R˜x(t)dt = 1 2x T 0 Z ∞ 0 exp( ˜MTt)R exp( ˜M t)dt − Z ∞ 0 exp(MTt)R exp( ˜M t)dt x0 = 1 2x T 0(Y2− Y1)x0
where Y1 and Y2 solve the following Sylvester equations:
( ˜MTY
1+ Y1M − R˜ = 0;
MTY
2+ Y2M − R˜ = 0.
(2.3) In principle, we can compute the solution of the first equation because all the coefficients are known. The solution of the second equation is as stated in the following lemma.
Lemma 23. ( ˜X − X) is the unique solution of the Sylvester equation ( ˜X − X) ˜M + MT( ˜X − X) − R = 0.
Proof. We have that
( ˜X − X) ˜M + MT( ˜X − X) − R
= ( ˜X − X)(A − G ˜X) + (A − GX)T( ˜X − X) − Q − ATX − ˜˜ XA+ ˜XG ˜X
= XGX − XA − ATX − Q= 0,
where the last equality holds because X satisfies that Riccati equation. As M and ˜
M are stable, ˜M and −MT do not have common eigenvalues, so thanks to Lemma
2.3. APPROXIMATION OF THE OPTIMALITY RESIDUAL AS A QUADRATIC FORM25 Heuristically, as ˜M is a small perturbation of M , the solution of the first equation
in (2.3) will be close to ˜X − X. We denote by Z = Y2− Y1 = ˜X − X − Y1, so that
J (˜u) − J (u) = 1 2x
T 0Zx0.
Lemma 24. Z is the unique solution of the Lyapunov equation ˜
MTZ + Z ˜M + ( ˜X − X)TG( ˜X − X) = 0. (2.4)
Proof. The uniqueness of the solution follows again from Lemma 53 because ˜M is stable. We have that
0 = R − ˜M Y1 − Y1M˜ = Q + ATX˜ + ˜XA − ˜XG ˜X − ˜MT( ˜X − X − Z) − ( ˜X − X − Z) ˜M
= ˜MTZ+ Z ˜M + Q + ATX˜ + ˜XA − ˜XG ˜X −(A − G ˜X)T( ˜X − X) − ( ˜X − X)(A − G ˜X)
= ˜MTZ+ Z ˜M + Q + ATX+ XA + ˜XTG ˜X − ˜XTGX − XG ˜X
= ˜MTZ+ Z ˜M + XGX + ˜XTG ˜X − ˜XTGX − XG ˜X = ˜MTZ+ Z ˜M + ( ˜X − X)TG( ˜X − X).
To sum up, the optimality residual is J (˜u) − J (u) = 1
2x
T 0Zx0
where Z solves the Lyapunov equation ˜
MTZ + Z ˜M + ( ˜X − X)TG( ˜X − X) = 0. (2.5) Notice that thanks to Lemma 56, as ( ˜X − X)TG( ˜X − X) is positive semidefinite
and ˜M is stable (at least if the computed solution is sufficiently close to the exact one), we have that Z is positive semidefinite, which is what we expect because the optimality residual must be nonnegative by definition.
2.3
Approximation of the optimality residual as
a quadratic form
It will be useful to express the quantity J (˜u) − J (u) as a quadratic form depending on vec(R). Thanks to 50 we can vectorize Equation (2.5) and we obtain:
vec(Z) = −(I ⊗ ˜MT + ˜MT ⊗ I)−1vec(( ˜X − X)TG( ˜X − X)). We define
E = (I ⊗ ˜MT + ˜MT ⊗ I), so
vec(Z) = −E−1vec(( ˜X − X)TG( ˜X − X)).
Our objective is to find an n2× n2 symmetric matrix M such that
We have that J (˜u) − J (u) = 1 2x T 0Zx0 = 1 2vec(x T 0Zx0) = 1 2(x T 0 ⊗ x T 0)vec(Z) = −1 2(x T 0 ⊗ x T 0)E −1 vec(( ˜X − X)TG( ˜X − X)).
Let C be a n × n matrix such that
vec(C)T = −1 2(x T 0 ⊗ x T 0)E −1 . We have that
J (˜u) − J (u) = (vec(C))Tvec(( ˜X − X)TG( ˜X − X))
= (vec(C))T(I ⊗ ( ˜X − X)TG)vec( ˜X − X)
= (((I ⊗ G( ˜X − X))vec(C))Tvec( ˜X − X)
= (vec(G( ˜X − X)C))Tvec( ˜X − X)
= ((CT ⊗ G)vec( ˜X − X))Tvec( ˜X − X)
= vec( ˜X − X)T(C ⊗ G)vec( ˜X − X).
By Lemma 23 we have that
vec( ˜X − X) = (I ⊗ MT + ˜MT ⊗ I)−1 vec(R) = E−1vec(R), so up to first-order corrections vec( ˜X − X) ≈ E−1vec(R). Therefore, J (˜u) − J (u) ≈ vec(R)TE−T (C ⊗ G)E−1vec(R) (2.6) = vec(R)TMvec(R) (2.7) where M = E−T(C ⊗ G)E−1.
Remark 25. The matrix C ⊗ G is positive semidefinite. As G is positive definite, it is sufficient to prove that C is symmetric and positive semidefinite. C is the solution of the Lyapunov equation ˜M C+ C ˜MT = x
0xT0. As M is stable and x0xT0 is positive
2.4. NUMERICAL EXPERIMENTS 27
2.4
Numerical experiments
We want to see graphically the relation between the equation residual and the opti-mality residual. To this scope, we choose an algebraic Riccati equation from [4] for which the solution is known, in particular the coefficients are:
A =1 0 0 −2 , B =λ 0 , S= 1, Q =1 1 1 1
and the solution is
X = "1+√1+λ2 λ2 1 2+√1+λ2 1 2+√1+λ2 1 4 1 − λ2 (2+√1+λ2)2 # .
We choose λ = 0.1 and ε = 10−4. We make 10000 perturbations of the form
˜
X = X + ε · randn(2, 2).
As the optimality residual depends on the initial condition x0 while the equation
residual does not, we prefer to consider the norm of matrix Z in Equation (2.5), i.e. such that J (˜u) − J (u) = 1
2x T
0Zx0. Figure 2.1 shows the relation between the
equation residual and the norm of the matrix Z for each perturbation.
Figure 2.1: Optimality residual versus equation residual.
If we look at Equation (2.6), we can expect that the points in Figure 2.1 should be between two parabolas, associated to the smallest and largest eigenvalues of M. In fact, in this equation we have that M is singular (because G is singular), so the smallest eigenvalue is 0. This means that the optimality residual is bounded in a certain sense by the equation residual, but it can be small even if the equation residual is large.
Chapter 3
Methods for the solution of ARE
There are many methods that can be used to solve continuous-time algebraic Riccati equations. In this chapter we briefly present Newton’s method, Schur’s method and a sign algorithm. We will compare these methods with respect to optimality residual at the end of this chapter.
3.1
Newton’s method
We apply Newton’s method to the function
F(X) = ATX+ XA + Q − XGX,
whose Fr´echet derivative is
LF,X(E) = (AT − XG)E − E(A − GX).
Given an initial X0, at each step k = 1, 2, . . . we solve the Sylvester equation:
(AT − X
kG)Hk+ Hk(A − GXk) = F (Xk)
and we set
Xk+1 = Xk− Hk.
Under suitable hypothesis on X0 Newton’s method converges, as indicated in the
following theorem.
Theorem 26 ([5]). If Q and G are positive semidefinite, (A, G) and (AT, Q) are
stabilizable and A − GX0 is stable then the sequence {Xk} generated by Newton’s
method satisfies the following properties: 1. A − GXk is stable for all k ≥0;
2. Xk+1− Xk is positive semidefinite for al k ≥1;
3. there exists a constant c >0 (independent of X) such that kX − Xk+1k ≤ ckX − Xkk2
for all k ≥0.
In our case, Q and G are positive semidefinite and (A, G) and (AT, Q) are
sta-bilizable. To apply the theorem, it remains to show how to find a good initial point X0. This can be done through the Bass algorithm.
Theorem 27. ([1]) Let (A, G) be a stabilizable pair. Let α > ρ(A) so that the matrix −(A + αIn) is stable. Then X0 = −GTZ† is stabilizing1, where Z is symmetric
positive semidefinite and solves the Lyapunov equation (A + αIn)Z + Z(A + αIn) = 2GGT.
3.2
Schur’s method
We have seen that the solution of the algebraic Riccati equation (1.4) can be obtained from the stable invariant subspace of the Hamiltonian matrix H = A −G
−Q −AT . If U1 U2
is a base of such subspace and U1 is nonsingular, then the stabilizing solution
of the ARE is X = U2U1−1. The method introduced in [12] uses this to find the
solution, and its simplest form is the following.
1. Find a Schur form of H, i.e. find an orthogonal matrix Q and a quasi-upper triangular matrix T such that H = QT QT. We are working with quasi-upper
triangular matrix in order to avoid using complex numbers.
2. Reorder the Schur form in such a way that the eigenvalues of H that have negative real part are in the n × n block (1, 1) of matrix T ([2]); a method to do this will be described in the next section.
3. Partitioning Q and T in blocks of dimension n × n as Q = Q1 Q3 Q2 Q4 and T =T11 T12 0 T22 , we have that HQ1 Q2 =Q1 Q2 T11, so Q1 Q2
is a basis of the stable invariant subspace and we can compute the solution X = Q2Q−11 .
1We denote by Z† the Moore-Penrose inverse of matrix Z, which is defined as follows: take
a singular value decomposition Z = U ΣVT, let S be a diagonal matrix such that S ii =
√ Σii if
3.2. SCHUR’S METHOD 31
3.2.1
Ordering Schur’s form
We will show how to swap two consecutive blocks in a matrix A = A11 A12 0 A22
, where A11 is p × p, A12 is p × q and A22is q × q, with p, q ∈ {1, 2}. Once we can swap
adjacent blocks, we can move the blocks relative to the eigenvalues with negative real part in the upper-left corner of the matrix.
Let X be the solution of the Sylvester equation A11X − XA22= A12.
The solution exists and it is unique because σ(A11)∩σ(A22) = ∅, otherwise we would
not want to exchange the two blocks. Note that X has dimensions p × q and we have that A11 A12 0 A22 =Ip −X 0 Iq A11 0 0 A22 Ip X 0 Iq . Let us take an orthogonal matrix Q such that
QT−X Iq =R 0
(for example by a QR-factorization of the matrix−X Iq
) and let us partition it as Q=Q11 Q12
Q21 Q22
. Then we have that QT −X Ip Iq 0 =Q T 11 QT21 QT 12 QT22 −X Ip Iq 0 =R Q T 11 0 QT 12
and from this we deduce that R and Q12 are invertible. Then we have that
R QT 11 0 QT 12 −1 =R −1 −R−1QT 11Q −T 12 0 Q−T12 , so Q=−X Ip Iq 0 R QT 11 0 QT 12 −1 . Therefore, QT A11 A12 0 A22 Q= QT Ip −X 0 Iq A11 0 0 A22 Ip X 0 Iq Q =R Q T 11 0 QT 12 A11 0 0 A22 Ip X 0 Iq −X Ip Iq 0 R QT 11 0 QT 12 −1 =R Q T 11 0 QT 12 A22 0 0 A11 R−1 −R−1QT 11Q −T 12 0 Q−T12 =RA22R −1 −RA 22R−1QT11Q −1 12 + QT11A11Q−T12 0 QT 12A11Q−T12 = ˜ A22 A˜12 0 A˜11 .
We have that A11 is similar to ˜A11 and A22 is similar to ˜A22, so we swapped the
blocks.
3.2.2
Exploiting the Hamiltonian structure
The matrix H for which we want to compute the stable invariant subspace is Hamil-tonian. We first need some definitions and properties about Hamiltonian and sym-plectic matrices, then we will talk about the Hamiltonian Schur form and how it can be obtained and included in the previous algorithm.
Symplectic matrices
Definition 28. A matrix S is symplectic if STJ S = J .
We are interested in symplectic matrices because they preserve the Hamiltonian structure.
Lemma 29. If H is Hamiltonian and S is symplectic, then S−1HS is Hamiltonian.
Proof. As H is Hamiltonian, we have that HT = J HJ . As S is symplectic, we
have that ST = −J S−1J . Therefore,
(S−1HS)T = STHTS−T = (J S−1J )(J HJ )(J SJ ) = J (S−1HS)J
and this shows that the matrix S−1HS is Hamiltonian.
Remark 30. In general, verifying that a matrix is symplectic is an expensive task (i.e. it requires O(n3) operations). However, there are classes of matrices that are
easily seen to be symplectic:
• B =B 0
0 B−T
for any nonsingular matrix B ∈ Rn×n;
• C = I 0
C I
for any symmetric matrix C = CT ∈ Rn×n.
We can also characterize the orthogonal symplectic matrices, which are involved, for instance, in the construction of the real Hamiltonian Schur form.
Lemma 31. Every orthogonal symplectic matrix U is of the form U =U1 −U2 U2 U1
.
Hamiltonian Schur form
Hamiltonian matrices that do not have imaginary eigenvalues have a Hamiltonian Schur form.
3.2. SCHUR’S METHOD 33 Theorem 32. ([17]) Let H be a Hamiltonian matrix without imaginary eigevalues. Then there exist U ∈ R2n×2n orthogonal symplectic and T ∈ R2n×2n quasi-upper
triangular (i.e. block-upper triangular with diagonal blocks of size 1 × 1 or 2 × 2) such that
H = UT V
0 −TT
UT.
This is called the Hamiltonian Schur form.
A method to compute the Hamiltonian Schur form of a matrix is the following ([12]). The first step is to compute a real Schur form of H. Then we re-order the eigenvalues in such a way that the ones with negative real part are in the upper-left corner of T . More precisely, we obtain H = UT UT where T = T1 T12
0 T2
with T1 and T2 quasi-upper triangular, associated to the eigenvalues with negative and
positive real part, respectively. Now we partition the matrix U as U = U1 U3 U2 U4
and we have the following theorem. Theorem 33. Let V =U1 −U2
U2 U1
. Then V is orthogonal symplectic and transforms H in Hamiltonian Schur’s form, i.e. VHHV = T1 Tˆ12
0 −TT 1
.
Proof. The fact that V is orthogonal symplectic follows directly from the definitions. Writing explicitly the block products VHHV and UHHU we notice that the
(1, 1)-block of both matrices is T11, so by the orthogonality and symplecticity of V
we have that the (2, 2)-block of VHHV must be −TT
1 . Moreover, the (2, 1)-block of
VHHV is
−UT
2 AU1− U1TQU1+ U2TGU2− U1TATU2
and recalling that the solution of the Riccati equation is X = U2U1−1 we get that
(VHHV)
21= −U1T(XA+Q−XGX +ATX)U1 = 0 and this concludes the proof.
We recall that we were interested in a basis of the stable invariant subspace, and one such basis is the span of the columns of U1
U2
from the ordered real Schur decomposition of H. At this point, we can compute the solution X of the ARE as X = U2U1−1.
This method can be implemented in Matlab using functions schur with option ’real’ to compute the Schur decomposition of the matrix H and ordschur with option ’lhp’ to reorder the Schur form to put all the eigenvalues with negative real part in the (1, 1)-block.
However, this method does not preserve the Hamiltonian structure of the prob-lem. Structure-preserving methods for computing the real Hamiltonian Schur form have been developed in [6].
3.3
Sign methods
Let us recall that we need to compute the stable invariant subspace of H = A −Q
−G −AT
. Definition 34 ([9]). The sign of a complex number z is 1 if it has positive real part, −1 if it has negative real part, not defined otherwise.
For a matrix W without pure imaginary eigenvalues, its sign is obtained in the following way. Take a Jordan canonical form
W = V JV−1, J =J>0 0 0 J<0
,
where the p eigenvalues of J>0 have positive real part and the q eigenvalues of J<0
have negative real part. Then
sign(W ) = V Ip 0 0 −Iq
V−1.
Note that sign(H) exists because by Theorem 16 the matrix H has no pure imaginary eigenvalues. The stable invariant subspace of H is then ker(sign(H) + I). We present the algorithm suggested in [15; 19]. First, we need some definitions on matrix pencils.
Definition 35. A matrix pencil is a first-degree matrix polynomial E − λF , that we denote by (E, F ). It is row-reduced if the matrix E F has full row rank. A matrix pencil (E, F ) is regular if there exists λ ∈ C such that det(E − λF ) 6= 0. The vector v is a right eigenvector of (E, F ) associated to the eigenvalue λ ∈ C if (E − λF )v = 0.
Definition 36. We say that two matrix pencils (E, F ) and ( ˜E, ˜F) are equivalent if E = M ˜E and F = M ˜F for a nonsingular matrix M . We denote equivalence by ∼.
When two regular matrix pencils (E, F ) and ( ˜E, ˜F) are equivalent they have the same eigenvalues and right eigenvectors.
Definition 37. A pencil (E, F ) is Hamiltonian if EJ FT + F J ET = 0.
Theorem 38 ([19]). Let (E, F ) be a regular pencil and let ( ¯E, ¯F) be row-reduced and such that ¯EF = ¯F E. Consider the pencil
( ˜E, ˜F) := 1
2( ¯F F + ¯EE), ¯EF
.
If v is an eigenvector of (E, F ) with eigenvalue λ then v is an eigenvector of ( ˜E, ˜F) with eigenvalue f(λ) := 1
2(λ + λ
−1). Moreover, if (E, F ) is Hamiltonian, then
3.3. SIGN METHODS 35 The function f and its iterates f(k) are such that lim
k→∞f(k)(z) = sign(z).
Thus, if we iterate the procedure in Theorem 38, the eigenvalues of the pencil with negative real part tend to −1 and the eigenvalues with positive real part tend to 1. In order to obtain a representation of the pencils in such a way that the entries do not become too big, we can use permuted graph representations.
Definition 39 ([15]). A permuted graph representation for a subspace U is U = Span ΠT I Y , where Π is a permutation matrix.
Theorem 40 ([19]). Let U ∈ R2n×n be a matrix with full column rank. Then there
exist Y ∈ Rn×n and a permutation matrix P ∈ R2n×2n such that U = PIn
Y
and maxi,j|Yij| ≤ 1.
Definition 41 ([15]). Let v ∈ {0, 1}n and let w be the vector such that w
i = 1 − vi.
A symplectic swap matrix is the orthogonal symplectic matrix given by Πv = diag(w)
diag(v) −diag(v) diag(w)
.
We denote by S2n the set of symplectic swap matrices of dimension 2n.
Theorem 42 ([19]). Let (E, F ) be a row-reduced Hamiltonian pencil with E, F ∈ R2n×2n. Then there exist S ∈ S4n and Y = YT ∈ R2n×2n with maxi,j|Yij| ≤
√ 2 such that
(E, F ) ∼ ( ˜E, ˜F), where ( ˜E, ˜F) is the matrix pencil defined by
˜
F J ˜ET = S I Y
.
In fact, the bounds of Theorems 40 and 42 cannot be obtained exactly with a polynomial algorithm, but for our purposes it is sufficient to obtain a representation in which maxi,j|Yij| ≤ T0, where T0 >
√
2 is a fixed threshold. Algorithms to do this can be found in [15].
Using these theorems, we can construct an iterative algorithm that starts with the Hamiltonian pencil
(E0, F0) = (H, I)
and at each step (k = 0, 1, 2, . . .) does the following.
1. Compute a permutation matrix Π ∈ R4n×4n and a matrix Y ∈ R2n×2n such
that ΠI2n Y = Fk Ek
2. Let ¯
E F¯ = −Y I2n ΠT (so the hypothesis in Theorem 38 is satisfied).
3. Compute (Ek+1, Fk+1) as in Theorem 38,
4. Compute S ∈ S4n and Z = ZT ∈ R2n×2nsuch thatF
k+1 J Ek+1
T
= SI2n Z
and maxi,j|Zij| ≤ T0.
This is repeated until Z converges. Theorems 40 and 42 ensure that the entries of the matrices remain bounded. At the end, we get the pencil (E∞, F∞), and
the n-dimensional subspace associated to the eigenvalue −1 is the stable invariant subspace of H, that we can compute as ker(E∞+ F∞).
3.4
Comparison of methods
We now compare the three methods above and the solution produced by Matlab’s solver for algebraic Riccati equations care with respect to the optimality residual and the equation residual. We use examples of AREs coming from [4]. In general, Newton’s method behaves better with respect to both residuals, but it is also slower than the others.
For Newton’s method, we used the implementation in [5]; for Schur’s method we used the functions schur and ordschur in Matlab; for the sign algorithm with permuted graph bases we used the code in [18] with option sign.
To better visualize the behaviour of the methods, we use the performance profiles ([8]). This is a method to compare several solvers on a set of test problems. Let us assume that we have n solvers and m test problems. For each test problem we know the performance of each solver, which we denote by ts(p). In our case, ts(p) will be
the optimality or equation residual produced in the p-th test by the s-th solver. Definition 43. The performance ratio is the performance of solver s on problem p divided by the best performance obtained on that problem:
rp,s=
ts(p)
min{tσ(p) : σ is a solver}
≥ 1.
Definition 44. The performance profile of solver s is the function φs(θ) =
1
m · |{p ∈ P : rp,s≤ θ}|,
i.e. φs(θ) is the probability that the performance of solver s is within a factor θ of
the best performance over all solvers on the given set of problems.
We used the code from [8] and we plotted the performance profile with logarith-mic x-axis.
3.4. COMPARISON OF METHODS 37
Figure 3.1: Comparison of the optimality residuals.
Figure 3.3: Performance profile of the optimality residual.
Chapter 4
Schur’s method
In this chapter we analyze in more detail what happens to the residuals by applying Schur’s method for the solution of algebraic Riccati equations. In the first section we derive an expression for the optimality residual in terms of the residual of the Hamiltonian Schur form. We want to analyze what happens in terms of these residuals if we apply a change of basis before computing the Schur decomposition. Symplectic matrices must be used in order to preserve the structure, in particular we will use matrices of the form B =B 0
0 B−T
. We will find some heuristics to choose B in order to lower the optimality residual and we will compare their performances.
4.1
Residual of the Schur form and optimality
residual
Given a Hamiltonian matrix H, we want to produce an orthogonal symplectic matrix Q =Q1 −Q2 Q2 Q1 and matrix T =T11 T12 0 −TT 11
with T11 quasi-upper triangular such
that QTHQ = T .
In practice, a method to compute the Hamiltonian real Schur form produces Q and T such that
QTHQ =T11+ ∆T11 T12+ ∆T12
W −TT
11+ ∆T22
= T + ∆T . (4.1)
We call W the residual of the Schur form.
If the method is backward stable, we also have that ∆T11 ∆T12 W ∆T22 = O(u)kHk, so in particular kW k = kHk · O(u).
Our goal is to obtain a relationship between the residual of the Schur form and the optimality residual. To do so, we first get a relation between the residual of the Schur form and the equation residual R.
Lemma 45. We have that W = −QT 1RQ1.
Proof. We recall that ˜X = Q2Q−11 . First we prove that ˜X is symmetric. As Q is
orthogonal, we have that
QTQ = QT1 QT2 −QT 2 QT1 Q1 −Q2 Q2 Q1 =I 0 0 I , so in particular QT 1Q2 = QT2Q1, hence ˜ X = Q2Q−11 = Q −T 1 Q T 2 = (Q2Q−11 ) T = ˜XT. Expanding the product in Equation (4.1) we have that
W = −QT 2AQ1− QT1QQ1+ QT2GQ2− QT1A TQ 2 = −QT 1X˜ TAQ 1− QT1QQ1− QT1A TXQ˜ 1+ QT1X˜ TG ˜XQ 1 = −QT 1( ˜X TA − Q − ATX˜ + ˜XTG ˜X)Q 1 = −QT 1RQ1.
The last equation holds because ˜X is symmetric.
Notice that we really needed the Hamiltonian Schur form of H. Indeed, repeating the same computations with the matrix U coming from a real Schur form of H we do not get such a nice formula.
Vectorizing the previous result we have that vec(W ) = −(QT
1 ⊗ QT1)vec(R) so
vec(R) = −(QT
1 ⊗ QT1) −1
vec(W ). Using Equation (2.6) we get that J (˜u) − J (u) = vec(W )T(QT 1 ⊗ Q T 1) −T M(QT 1 ⊗ Q T 1) −1 vec(W ) = vec(W )T(Q−1 1 ⊗ Q −1 1 )M(Q −T 1 ⊗ Q −T 1 )vec(W ).
If the method is backward stable then we have that J (˜u) − J (u) ≈ O(u2) · kHk2· k(Q−1 1 ⊗ Q −1 1 )M(Q −T 1 ⊗ Q −T 1 )k. (4.2)
4.2
Scaling
We want to see what happens if we make a symplectic change of basis in H before applying Schur’s method. As seen in Lemma 29, if we scale with a symplectic matrix we obtain a Hamiltonian matrix again, so we will restrict ourselves to symplectic changes of variables of the two types in Remark 30.
4.2. SCALING 41
4.2.1
Block diagonal change of variables
We now consider a symplectic change of basis of the form
B =B 0
0 B−T
.
We denote with a bar the transformed quantities, so for instance ¯H = BHB−1 is
the transformed Hamiltonian matrix. Lemma 46. Let ¯H =
¯
A − ¯G − ¯Q − ¯AT
and denote by ¯X the computed solution of the associated algebraic Riccati equation ¯X ¯A+ ¯ATX¯+ ¯Q − ¯X ¯G ¯X = 0. Denote by ¯R the equation residual relative to ¯X.
Then we have that X = BTXB and R¯ = BTRB.¯
Proof. By direct computation we find that ¯ H =B 0 0 B−T · A −G −Q −AT ·B −1 0 0 BT = BA −BG −B−TQ −B−TAT ·B −1 0 0 BT = BAB−1 −BGBT −B−TQB−1 −B−TATBT = ¯ A − ¯G − ¯Q − ¯AT .
The algebraic Riccati equation associated with the Hamiltonian matrix ¯H is then 0 = ¯XTBAB−1− ¯XTBGBTX¯ + B−TQB−1+ B−TATBTX¯
which we can rewrite multiplying by BT on the left and B on the right as
0 = BT( ¯XTBAB−1− ¯
XTBGBTX¯ + B−TQB−1+ B−TATBTX)B¯ = (BTX¯TB)A − (BTX¯TB)G(BTXB¯ ) + Q + AT(BTXB)¯
so X = BTXB. From the previous relation it also follows that R = B¯ TRB.¯
Vectorizing the result of the previous lemma we get that vec(R) = (BT ⊗ BT)vec( ¯R).
Lemma 47. The matrix Q1 from the Schur factorization of H is of the following
form:
Q1 = (I + XTX)−1/2U,
where U is an orthogonal matrix.
Proof. Recall that X = Q2Q−11 , so Q2 = XQ1. As Q =
Q1 −Q2 Q2 Q1 is orthogonal, we have that I = QT 1Q1+ QT2Q2 = QT1Q1+ QT1X TXQ 1 = QT1(I + X TX)Q 1,
Consequently, after the change of basis we obtain ¯
Q1 = (I + ¯XTX)¯ −1/2U¯ = (I + B−TXTB−1B−TXB−1)−1/2U .¯ (4.3)
We then have that
J (˜u) − J (u) = vec(R)TMvec(R)
= vec( ¯R)T(BT ⊗ BT)TM(BT ⊗ BT)vec( ¯R) = vec( ¯W)T( ¯Q 1 T ⊗ ¯Q1 T )−T(BT ⊗ BT)TM(BT ⊗ BT)( ¯Q 1 T ⊗ ¯Q1 T )−1vec( ¯W) = vec( ¯W)T(( ¯Q 1 −1 B) ⊗ ( ¯Q1 −1 B))M(( ¯Q1 −1 B) ⊗ ( ¯Q1 −1 B))Tvec( ¯W).
We assume that the Hamiltonian Schur decomposition has been computed by a backward stable method, so that k ¯W k = O(u) · k ¯Hk. Then we can estimate J (˜u) − J (u) with the norm of the involved matrices:
J (˜u) − J (u) ≤ O(u2) · k ¯Hk2 · k(( ¯Q 1 −1 B) ⊗ ( ¯Q1 −1 B))M(( ¯Q1 −1 B) ⊗ ( ¯Q1 −1 B))Tk. (4.4) In the remaining part of this chapter, we try to find B in such a way that the quantity ϕ(B) := k ¯Hk2· k(( ¯Q1 −1 B) ⊗ ( ¯Q1 −1 B))M(( ¯Q1 −1 B) ⊗ ( ¯Q1 −1 B))Tk (4.5) is as small as possible.
4.2.2
Scalar scaling
First, we restrict ourselves to B = λI, so we need to estimate a good value for λ. In this case, the matrix ¯Q1
−1
B can be written more explicitly, we have that ¯ Q−11 B = λU I+ 1 λ4X TX 1/2 = U λ2I+ X TX λ2 1/2 and ¯ H = A −λ2G − 1 λ2Q −A T . Using Lemma 51, we find that
ϕ(B) ≤ k ¯Hk2· k(( ¯Q 1 −1 B) ⊗ ( ¯Q1 −1 B))k · kMk · k(( ¯Q1 −1 B) ⊗ ( ¯Q1 −1 B))Tk = k ¯Hk2· k ¯Q 1 −1 Bk4· kMk.
The matrix M depends (almost1) only on the problem, so we can ignore it for
now.
4.2. SCALING 43
As λ2I+XTX
λ2
1/2
is a positive semidefinite matrix and U is orthogonal, we have that k ¯Q1 −1 Bk= λ2+kXk 2 λ2 1/2 .
Consequently, the norm is minimized for λ =pkXk, so a first possible choice for the parameter is λ = kXk.
It is in fact known that rescaling the equation in this way usually leads to more precise solutions. In the paper [10], the authors obtain this result arguing in a different way, in particular they analyze the stability of the inversion step, i.e. the computation of X = Q2Q−11 .
With this choice of λ, however, we are neglecting the term k ¯Hk. The problem here is that there is not a nice formula to express k ¯Hk after the change of basis. We propose two estimates, the first based on the Frobenius norm of ¯H and the second based on an approximation of the spectral norm of ¯H.
First strategy
We use the fact that k ¯Hk ≤ k ¯HkF and
k ¯Hk2 F = BAB−1 −BGBT −B−TQB−1 −B−TATBT 2 F = kBAB−1k2F + kBGBTk2F + kB−TQB−1k2F + kB−TATBTk2F = 2kAk2 F + λ4kGk2F + 1 λ4kQk 2 F.
Instead of minimizing ϕ(B), we minimize the function ψ(B) = k ¯Q1 −1 Bk4· k ¯Hk2F = λ2+ kXk 2 λ2 2 · 2kAk2F + λ 4kGk2 F + 1 λ4kQk 2 F . Let y = λ2 and denote
¯ ψ(y) = ψ(λ2) = y+ kXk 2 y 2 · 2kAk2 F + kGk 2 Fy 2+kQk2F y2 . To find the minimum over {y > 0} we study the first derivative of ¯ψ:
¯ ψ0(y) = 4 y+kXk 2 y · kAk2 F + y 2kGk2 F − kAk2 FkXk2F y2 − kQk2 FkXk2F y4 . Considering the polynomial of degree 3
p(z) = kGk2 Fz 3+ kAk2 Fz 2− kAk2 FkXk 2 Fz − kQk 2 FkXk 2 F
we have that it has exactly one positive root η (because p(0) < 0, p(z) → +∞ as z →+∞ and p0 has exactly one zero for z > 0), so we use the value λ = η1/4.
Second strategy We have that k ¯Hk ≤ A 0 0 −AT + 0 −λ2G − 1 λ2Q 0 . We know that A 0 0 −AT = kAk and 0 −λ2G −1 λ2Q 0 = max λ2kGk, 1 λ2kQk . Instead of minimizing ϕ(B), we minimize the function
ρ(B) = k ¯Q1 −1 Bk2· A 0 0 −AT + 0 −λ2G −1 λ2Q 0 = λ2+ kXk 2 λ2 · kAk + max λ2kGk, 1 λ2kQk . Let y = λ2 and denote
¯ ρ(y) = ρ(λ2) = y+kXk 2 y · kAk + max ykGk,1 ykQk . We analyze the two cases:
• if y2 ≥ kQk kGk then
¯
ρ(y) = ykAk + y2kGk + kAkkXk2
y + kGkkXk
2;
¯
ρ0(y) = kAk + 2kGky −kAkkXk
2
y2 ;
so we can find the solution as the unique positive root of the polynomial p(z) = 2kGkz3+ kAkz2− kAkkXk2;
• if y2 < kQk kGk then
¯
ρ(y) = ykAk + kQk +kAkkXk
2 y + kQkkXk2 y2 ; ¯ ρ0(y) = kAk −2kQkkXk 2 y3 − kAkkXk2 y2 ;
so we can find the solution as the unique positive root of the polynomial p(z) = kAkz3− kAkkXk2z −2kQkkXk2.
4.2. SCALING 45
4.2.3
Diagonal scaling
Now we want to analyze more general changes of basis. We consider diagonal ma-trices B, of the form B = diag(b1, . . . , bn). We do not have a simple expression for
¯ Q1
−1
B this time, but we can make some estimates. We have that k ¯Q−11 Bk= σmax( ¯Q−11 B) = q λmax(( ¯Q−11 B)T( ¯Q −1 1 B)).
Recalling Equation (4.3) we obtain ( ¯Q−11 B)T( ¯Q−1 1 B) = B · ¯Q −T 1 · ¯Q −1 1 · B = B(I + B −1 XTB−2XB−1)B = B2+ XTB−2 X = B2+ (B−1 X)T(B−1 X).
Partition X by rows in the form X = x1 .. . xn
. Then we can estimate
k ¯Q−11 Bk2 = kB2+ (B−1 X)T(B−1 X)k ≤ kBk2+ kB−1 Xk2 ≤ kBk2 F + kB −1 Xk2F = n X i=1 b2i + n X i=1 kxik2 b2 i .
The last function is minimized for bi = pkxik for i = 1, . . . , n. We are again
neglecting the term k ¯Hk2, but it would be difficult to also include that in the above
computations.
4.2.4
Comparison of scaling strategies
We tried these scaling strategies on several examples of algebraic Riccati equations coming from [4]. As many of these examples do not have a known solution, we computed a precise approximation in Matlab using Newton’s method and vpa to increase the number of significant digits in the solution.
For each test, we plot the relative error in the computed solution (k ˜X−XkkXk ) and the norm of the matrix Z in Equation (2.5), from which the optimality residual is computed as J (˜u) − J (u) = 1
2x T
0Zx0. We prefer not to compute the optimality
residual because it depends on the initial condition x0, while the equation residual
does not.
The results are shown in Figures 4.1 and 4.2. The corresponding performance profiles (see [8]) are plotted in Figures 4.3 and 4.4. As a reference, we also show the results obtained with Matlab’s care function.
Figure 4.1: Optimality residual.
4.2. SCALING 47
Figure 4.3: Performance profile of the optimality residual.
