Linear Matrix Inequality (LMI)
A linear matrix inequality is an expression of the form
F (x) , F0 + x1F1 + · · · + xmFm > 0 (1) where
• x = (x1, · · · , xm) ∈ <m,
• F0, · · · , Fm are real symmetric matrices, and
• the inequality > 0 in (1) means positive definite, i.e., uTF (x)u > 0 for all u ∈ <n, u 6=
0. Equivalently, the smallest eigenvalue of F (x) is positive.
1
Definition[Linear matrix inequality(LMI)]
A linear matrix inequality is
F (x) > 0 (2)
where F is an affine function mapping a finite dimensional vector space to the set Sn , {M : M = MT ∈ <n×n}, n > 0, of real matrices.
remark Recall, from definition, that an affine mapping F : V → Sn necessarily takes the form F (x) = F0+T (x) where F0 ∈ Sn and T : V → Sn is a linear transformation. Thus if V is of di- mension m, and {e1, · · · , em} constitutes a basis for V, then we can write
T (x) =
Xm
j=1
xjFj
where the elements {x1, · · · , xm} are such that x = Pmj=1 xjej and Fj = T (ej) for j = 1, · · · , m.
Hence we obtain (1) as a special case.
Remark. The same remark applies to map- pings F : <m1×m2 → Sn where m1, m2 ∈ Z+. A simple example where m1 = m2 is the Lya- punov inequality
F (X) = ATX + XA + Q > 0 .
Here, A, Q ∈ <m×m are assumed to be given, Q is symmetric, and X ∈ <m×m is the unknown matrix.
In this case, the domain V of F in definition is equal to Sm. We can view this LMI as a special case of (1) by defining a basis E1, · · · , Em of Sm and writing X = Pmj=1 xjEj:
F (X) = F
Xm j=1
xjEj
= F0 +
Xm
j=1
xjF (Ej)
= F0 +
Xm
j=1
xjFj which is of the form (1).
3
Remark. The LMI
F (x) = F0 + xF1 + · · · + xmFm
defines a convex constraint on x = (x1, · · · , xm).
i.e., the set
F , {x : F (x) > 0}
is convex. Indeed, if x1, x2 ∈ F and α ∈ (0, 1) then
F (αx1+(1−α)x2) = αF (x1)+(1−α)F (x2) > 0
Convexity has an important consequence: even though the LMI has no analytical solution in general, it can be solved numerically with guar- antees of fining a solution when one exists. Al- though the LMI may seem special, it turns out that many convex sets can be represented in this way.
1. Note that a system of LMIs (i.e. a finite set of LMIs) can be written as a single LMI since
F1(x) < 0 ...
FK(x) < 0
is equivalent to F (x) , diag[F1(x), · · · , FK(x)] < 0
2. Combined constraints (in the unknown x) of the form
( F (x) > 0
Ax = b or
( F (x) > 0
x = Ay + b for some y where the affine function F : <m → Sn and matrices A ∈ <n×m and b ∈ <n are given can be lumped into one LMI. More gener- ally, the combined equations
( F (x) > 0
x ∈ M (3)
5
where M is an affine subset of <n, i.e.
M = x0 + M0 = {x0 + m | m ∈ M0} with x0 ∈ <n and M0 a linear subspace of
<n, can be written in the form of one single LMI. In order to see this, let e1, · · · , ek ∈ <n be a basis of M0 and let F (x) = F0 + T (x) be decomposed as in remark. Then (3) can be rewritten as
0 < F (x) = F0 + T (x0 +
Xk
j=1
xjej)
= F| 0 + T (x{z 0)} constant part
+
Xk
j=1
xjT (ej)
| {z }
linear part
= ¯F0 + x1F¯1 + ... + xkF¯k , F (¯¯ x)
where ¯F0 = F0 + T (x0), ¯Fj = T (ej) and x = (x1, · · · , xk). This implies that x ∈ <n satisfies (3) if and only if F (x) > 0. Note
that the dimension of ¯x is smaller than the dimension of x.
3. (Schur Complement) Let F : V → Sn be an affine function partitioned to
F (x) =
"
F11(x) F12(x) F21(x) F22(x)
#
where F11(x) is square. Then
F (x) > 0 iff
( F11(x) > 0
F22(x) − F21(x)F11−1(x)F12(x) > 0 (4) Note that the second inequality in (4) is a nonlinear matrix inequality in x. It fol- lows that nonlinear matrix inequalities of the form (4) can be converted to LMIs, and nonlinear inequalities (4) define a con- vex constraint on x.
Types of LMI problems
Suppose that F, G : V → Sn1 and H : V → Sn2 are affine functions.
Feasibility: The test whether or not there ex- ist solutions x of F (x) > 0 is called a fea- sibility problem. The LMI is called non- feasible if no solutions exist.
Optimization: Let f : S → < and suppose that S = {x|F (x) > 0}. The problem to de- termine Vopt = infx∈S f (x) is called an op- timization problem with an LMI constraint.
Generalized eigenvalue problem: Minimize a scalar λ ∈ < subject to
λF (x) − G(x) > 0 F (x) > 0
H(x) > 0
What are LMIs good for?
Many optimization problems in control design, identification, and signal processing can be for- mulated using LMIs.
Example. Asymptotic stability of the LTI sys- tem
˙x = Ax , A ∈ <n×n (5) Lyapunov said, asymptotically stable iff there exists X ∈ Sn such that
X > 0, ATX + XA < 0
i.e. equivalent to feasibility of the LMI
"
X 0
0 −ATX − XA
#
> 0
7
Example. Determine a diagonal matrix D such that ||DM D−1|| < 1 where M is some given matrix. Since
||DM D−1|| < 1 ⇐⇒ D−TMTDTDM D−1 < I
⇐⇒ MTDTDM < DTD
⇐⇒ X − MTXM > 0
where X := DTD > 0 we see that the existence of such a matrix means the feasibility of LMI.
Example. Let F be an affine function and consider the problem of minimizing
f (x) , σmax(F (x)) over x.
λmax(FT(x)F (x)) < γ
⇐⇒ γI − FT(x)F (x) > 0
⇐⇒
"
γI FT(x) F (x) I
#
> 0 if we define
¯ x ,
"
x γ
#
, F (¯¯ x) ,
"
γI FT(x) F (x) I
#
, f (¯¯ x) , γ , then ¯F is an affine function of ¯x and the prob- lem to minimize the maximum eigenvalue of F (x) is equivalent to determining inf ¯f (¯x) sub- ject to the LMI ¯F (¯x) > 0. Hence, this is an optimization problem with a linear objective function ¯f and an LMI constraint.
9
Example(Simultaneous stabilization)
Consider k LTI systems with n-dim state space and m-dim input space:
˙x = Aix + Biu
where Ai ∈ <n×n and Bi ∈ <n×m, i ∈ 1, · · · , k.
We’d like to find a state feedback law u = F x, F ∈ <m×n such that the eigenvalues λ(Ai+ BiF ) lie on the LHP for i ∈ 1, · · · , k. From the example above, this is solved when we find matrices F and Xi, i ∈ 1, · · · , k such that for i ∈ 1, · · · , k,
( Xi > 0
(Ai + BiF )TXi + Xi(Ai + BiF ) < 0 (6) Note that this is not a system of LMIs in Xi and F . If we introduce Yi = Xi−1 and K = F Yi, then (6) becomes
( Yi > 0
AiYi + YiATi + BiK + KiTBi < 0 ,
which can be further simplified by assuming
the existence of a joint Lyapunov function, i.e.
Xi = · · · = Xk = X. The joint stabilization problem has a solution if this system of LMIs is feasible.
H∞ nominal performance Consider
x = Ax + Bu (7)
y = Cx + Du (8)
with state space X = <n, input space U = <m and output space Y = <p.
proposition If the system (7) is asymptotically stable then ||G||∞ < γ whenever there exists a solution K = KT > 0 to the LMI
"
ATK + KA + CTC KB + CTD BTK + DTC DTD − γ2I
#
< 0. (9)
Can compute the H∞ norm of the transfer function by minimizing γ > 0 over all variables γ and K > 0 that satisfy the LMI.
H2 nominal performance
We take impulsive inputs of the form u(t) = δ(t)ei with ei the ith basis vector in the standard basis of the input space <m. (i = 1 · · · m).
With zero initial conditions, the corresponding output yi ∈ L2 and is given by
yi(t) =
C exp(At)Bei for t > 0 Deiδ(t) for t = 0 0 for t < 0.
.
Only if D = 0, the sum of the squared norms of all such impulse responses Pmi=1 ||yi||22 is well defined and given by
Xm
i=1
||yi||22 = trace
Z ∞
0 BT exp(At)CTC exp(At)B dt
= trace
Z ∞
0 C exp(At)BBT exp(ATt)CT dt
= trace
Z ∞
−∞ G(jω)G∗(jω) dω
where G is the transfer function of the system.
12
proposition Suppose that the system (7) is asymptotically stable (and D = 0), then the following statements are equivalent.
(a) ||G||2 < γ
(b) there exists K = KT > 0 and Z such that
"
ATK + KA KB BTK −I
#
< 0;
"
K CT
C Z
#
> 0; (10) trace(Z) < γ2 (11)
(c) there exists K = KT > 0 and Z such that
"
AK + KAT KCT
CK −I
#
< 0;
"
K B
BT Z
#
> 0; (12) trace(Z) < γ2 (13)
pf. note that ||G||2 < γ is equivalent to re- quiring that the controllability gramian Wc :=
R∞
0 exp(At)BBTexp(ATt) dt satisfies trace(CW CT) < γ2.
Since the controllability gramian is the unique positive definite solution to the Lyapunov equa- tion
AW + W AT + BBT = 0
this is equivalent to saying that there exists X > 0 such that
AX + XAT + BBT < 0; trace(CXCT) < γ2. With a change of variables K := X−1, this is equivalent to the existence of K > 0 and Z such that
ATK + KA + KBBTK < 0; CK−1CT < Z;
and
trace(Z) < γ2.
14
Now, using Schur complements for the first two inequalities yields that ||G||2 < γ is equiv- alent to the existence of K > 0 and Z such that"
ATK + KA KB
BTK I
#
< 0;
"
K CT
C Z
#
> 0;
and
trace(Z) < γ2 .
The equivalence with (12) is obtained by the observation that ||G||2 = ||GT||2.
Therefore, the smallest possible upper bound of the H2-norm of the transfer function can be calculated by minimizing the criterion trace(Z) over the variables K > 0 and Z that satisfy the LMIs defined by the first two inequalities in (10) or (12).
Controller Synthesis Let
˙x = Ax + B1w + B2u
z∞ = C∞x + D∞1w + D∞2u z2 = C2x + D21w + D22u
y = Cyx + Dy1w and
˙xK = AKxK + BKy u = CKxK + DKy
be state-space realizations of the plant P (s) and the controller K(s) respectively.
15
Denoting by T∞(s) and T2(s) the CL TF from w to z∞ and z2, respectively, we consider the following multi-objective synthesis problem:
Design an output feedback controller u = K(s)y such that
• H∞ performance: maintains the H∞ norm of T∞ below γ0.
• H2 performance: maintains the H2 norm of T2 below ν0.
• Multi-objective H2/H∞ controller design:
minimizes the trade-off criterion of the form α||T∞||2∞ + β||T2||22 with some α, β ≥ 0.
• Pole placement: places the CL poles in some prescribed LMI region D.
Let the following denote the corresponding CL state-space eqns,
˙
xcl = Aclxcl + Bclw z∞ = Ccl1xcl + Dcl1w
z2 = Ccl2xcl + Dcl2w
then our design objectives can be expressed as follows:
• H∞ performance: the CL RMS gain from w to z∞ does not exceed γ iff there exists a symmetric matrix X∞ such that
AclX∞ + X∞ATcl Bcl X∞Ccl1T BclT −I DTcl1 Ccl1X∞ Dcl1 −γ2I
< 0 X∞ > 0
• H2 performance: the LQG cost from w to z2 does not exceed ν iff Dcl2 = 0 and there
17
exists a symmetric matrices X2 and Q such that "
AclX2 + X2ATcl Bcl BclT −I
#
< 0
"
Q Ccl2T X2 X2Ccl2T X2
#
> 0 trace(Q) < ν2
• Pole placement: the CL poles lie in the LMI region D := {z ∈ C : L + M z + MTz <¯ 0} with L = LT = [λij]1≤i,j≤m and M = [µij]1≤i,j≤m iff there exists a symmetric ma- trix Xpol such that
[λijXpol + µijAclXpol + µjiXpolATcl]1≤i,j≤m < 0 Xpol > 0 .
For tractability, we seek a single Lyapunov ma- trix X := X∞ = X2 = Xpol that enforces all three sets of constraints. Factorizing X as
X =
"
R I
MT 0
# "
0 S I NT
#−1
and introducing the transformed controller vari- ables:
BK := N BK + SB2DK CK := CKMT + DKCyR
AK := N AKMT + N BKCyR + SB2CKMT +S(A + B2DKCy)R ,
the inequality constraints on X are turned into LMI constraints in the variables R, S, Q, AK, BK, CK and DK. And we have the following subop- timal LMI formulation of our multi-objective synthesis problem:
18
Minimize αγ2+βtrace(Q) over R, S, Q, AK, BK, CK, DK and γ2 satisfying:
AR + RAT + B2CK + CKT B2T AK + A + B2DKCy B1 + B2DKDy1 F F ATS + SA + BKCy + CyTBKT SB1 + BKDy1 F
F F −I F
C∞R + D∞2CK C∞ + D∞2DKCy D∞1 + D∞2DKDy1 −γ2I
< 0
Q C2R + D22CK C2D22DKCy
F R I
F I S
> 0
"
λij
"
R I I S
#
+ µij
"
AR + B2CK A + B2DKCy AK SA + BKCy
#
+ µji
"
(AR + B2CK)T ATK
(A + B2DKCy)T (SA + BKCy)T
##
1≤i,j≤m
< 0 trace(Q) < ν02
γ2 < γ02 D21 + D22DKDy1 = 0 .
Given optimal solutions γ∗, Q∗ of this LMI prob- lem, the closed loop performances are bounded by
||T ||∞ ≤ γ∗, ||T ||2 ≤
q
trace(Q∗) .
This has been implemented by the matlab com- mand “hinfmix”.
20
Reference
• Boyd S, El Ghaoui L, Feron E, Balakrish- nan V. Linear matrix inequalities in system and control theory, vol. 15 ed.
• Scherer C, Weiland S. Linear matrix in- equalities in control. Lecture notes of DISC Course
• LMI Control Toolbox, Gahinet, Nemirovski, Laub, Chilali, Mathworks
Affine combinations of linear systems
Often models uncertainty about specific pa- rameters is reflected as uncertainty in specific entries of the state space matrices A, B, C, D.
Let p = (p1, ..., pn) denote the parameter vec- tor which expresses the uncertain quantities in the system and suppose that this parameter vector belongs to some subset P ⊂ <n. Then the uncertain model can be thought of as be- ing parameterized by p ∈ P through its state space representation
˙x = A(p)x + B(p)u (14) y = C(p)x + D(p)u . (15) One way to think of equations of this sort is to view them as a set of linear time-invariant systems as parameterized by p ∈ P. However, if p is time, then (14) defines a linear time varying dynamical system and it can therefore also be viewed as such. If components of p are
22
time varying and coincide with state compo- nents then (14) is better viewed as a nonlinear system.
Of particular interest will be those systems in which the system matrices affinely depend on p. This means that
A(p) = A0 + p1A1 + · · · + pnAn (16) B(p) = B0 + p1B1 + · · · + pnBn (17) C(p) = C0 + p1C1 + · · · + pnCn (18) D(p) = D0 + p1D1 + · · · + pnDn . (19) Or, written in a more compact form
S(p) = S0 + p1S1 + ... + pnSn where
S(p) =
"
A(p) B(p) C(p) D(p)
#
is the system matrix associated with (14). We call these models affine parameter dependent
models. In MATLAB such a system is repre- sented with the routines psys and pvec. For n = 2 and a parameter box
P , {(p1, p2)| p1 ∈ [pmin1 , pmax1 ], p2 ∈ [pmin2 , pmax2 ]}
the syntax is
affsys = psys( p, [s0, s1, s2] );
p = pvec( ‘box’, [p1min p1max ; p2min p2max])
where p is the parameter vector whose i-th component ranges between pimin and pimax.
Bounds on the rate of variations, ˙pi(t) can be specified by adding a third argument “rate”
when calling “pvec”.
See also the following routines:
• pdsimul for time simulations of affine pa- rameter models
• aff2pol to convert an affine model to an equivalent polytopic model
• pvinfo to inquire about the parameter vec- tor