15 Linear Matrix Inequality (LMI)

SNU MAE Multivariable Control

15 Linear Matrix Inequality (LMI)

A linear matrix inequality is an expression of the form

F (x) , F₀+ x₁F₁+ · · · + x_mF_m > 0 (1) where

• x = (x₁, · · · , x_m) is a vector of real numbers,

• F₀, · · · , F_m are real symmetric matrices, i.e., F_i = F_i^T ∈ IR^n×n, i = 0, · · · , m for some n ∈ Z₊, and

• the inequality > 0 in (1) means positive definite, i.e., u^TF (x)u > 0 for all u ∈ IRⁿ, u 6= 0. Equivalently, the smallest eigenvalue of F (x) is positive.

Definition 15.1 (Linear matrix inequality(LMI)) A linear matrix in- equality is

F (x) > 0 (2)

where F is an affine function mapping a finite dimensional vector space to the set Sⁿ, {M : M = M^T ∈ IR^n×n}, n > 0, of real matrices.

“Affine matrix inequality” would have been a better name. Note that the constraints F (x) < 0 and A(x) < B(x) are special cases of (2).

Remark. Recall, from definition, that an affine mapping F : V → Sⁿ necessarily takes the form F (x) = F₀+ T (x) where F₀ ∈ Sⁿand T : V → Sⁿ is a linear transformation. Thus if V is finite dimensional, say of dimension m, and {e₁, · · · , e_m} constitutes a basis for V, then we can write

T (x) = Xm j=1

x_jF_j

where the elements {x₁, · · · , x_m} are such that x = P_m

j=1x_je_j and F_j = T (e_j) for j = 1, · · · , m. Hence we obtain (1) as a special case.

Remark. The same remark applies to mappings F : IR^m1×m2 → Sⁿwhere m₁, m₂∈ Z⁺. A simple example where m₁ = m₂is the Lyapunov inequality

F (X) = A^TX + XA + Q > 0 .

Here, A, Q ∈ IR^m1×m2 are assumed to be given and X ∈ IR^m×m is the unknown. The unknown variable is therefore a matrix. Note that this defines an LMI only if Q is symmetric. In this case, the domain V of F in definition 15.1 is equal to S^m. We can view this LMI as a special case of (1) by defining a basis E₁, · · · , E_m of S^m and writing X =P_m

j=1x_jE_j: F (X) = F



X^m

j=1

x_jE_j



 = F₀+ Xm j=1

x_jF (E_j) = F₀+ Xm j=1

x_jF_j

which is of the form (1).

The LMI

F (x) = F₀+ xF₁+ · · · + x_mF_m

defines a convex constraint on x = (x₁, · · · , x_m). i.e., the set F , {x : F (x) > 0}

is convex. Indeed, if x₁, x₂ ∈ F and α ∈ (0, 1) then

F (αx₁+ (1 − α)x₂) = αF (x₁) + (1 − α)F (x₂) > 0

Convexity has an important consequence: even though the LMI has no analytical solution in general, it can be solved numerically with guarantees of fining a solution when one exists. Although 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







F₁(x) < 0 ... F_K(x) < 0





 is equivalent to F (x) , diag[F₁(x), · · · , F_K(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 : IR^m → Sⁿ and matrices A ∈ IR^n×m and b ∈ IRⁿ are given can be lumped into one LMI. More generally, the combined equations

½ F (x) > 0

x ∈ M (3)

where M is an affine subset of IRⁿ, i.e.

M = x₀+ M₀ = {x₀+ m | m ∈ M₀}

with x₀ ∈ IRⁿ and M₀ a linear subspace of IRⁿ, can be written in the form of one single LMI. In order to see this, let e₁, · · · , e_k ∈ IRⁿ be a basis of M₀ and let F (x) = F₀ + T (x) be decomposed as in remark.

Then (3) can be rewritten as

0 < F (x) = F₀+ T (x₀+ Xk j=1

x_je_j) = F₀+ T (x₀)

| {z }

constant part +

Xk j=1

x_jT (e_j)

| {z }

linear part

= F¯₀+ x₁F¯₁+ ... + x_kF¯_k , F (¯¯ x)

where ¯F₀ = F₀ + T (x₀), ¯F_j = T (e_j) and x = (x₁, · · · , x_k). This implies that x ∈ IRⁿ 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 → Sⁿbe an affine function partitioned to

F (x) =

· F₁₁(x) F₁₂(x) F₂₁(x) F₂₂(x)

¸

where F₁₁(x) is square. Then F (x) > 0 iff

½ F₁₁(x) > 0

F₂₂(x) − F₂₁(x)F₁₁⁻¹(x)F₁₂(x) > 0 (4) Note that the second inequality in (4) is a nonlinear matrix inequality in x. It follows that nonlinear matrix inequalities of the form (4) can be converted to LMIs, and nonlinear inequalities (4) define a convex constraint on x.

15.1 Types of LMI problems

Suppose that F, G : V → Sⁿ¹ and H : V → Sⁿ² are affine functions. There are three generic problems related to the study of linear matrix inequalities:

Feasibility: The test whether or not there exist solutions x of F (x) > 0 is called a feasibility problem. The LMI is called non-feasible if no solutions exist.

Optimization: Let f : S → IR and suppose that S = {x|F (x) > 0}. The problem to determine Vopt = inf^x∈Sf (x) is called an optimization problem with an LMI constraint.

Generalized eigenvalue problem: Minimize a scalar λ ∈ IR subject to





λF (x) − G(x) > 0 F (x) > 0

H(x) > 0 15.2 What are LMIs good for?

Many optimization problems in control design, identification, and signal processing can be formulated using LMIs.

Example. Asymptotic stability of the LTI system

˙x = Ax , A ∈ IR^n×n (5)

Lyapunov said, asymptotically stable iff there exists X ∈ Sⁿsuch that X > 0 and A^TX + XA < 0. i.e. equivalent to feasibility of the LMI

· X 0

0 −A^TX − XA

¸

> 0

Example. Determine a diagonal matrix D such that ||DM D⁻¹|| < 1 where M is some given matrix. Since

||DM D⁻¹|| < 1 ⇐⇒ D^−TM^TD^TDM D⁻¹ < I

⇐⇒ M^TD^TDM < D^TD

⇐⇒ X − M^TXM > 0

where X := D^TD > 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 mini- mizing f (x) , λ_max(F (x)) over x.

λ_max(F^T(x)F (x)) < γ ⇐⇒ γI − F^T(x)F (x) > 0

⇐⇒

· γI F^T(x) F (x) I

¸

> 0

if we define

¯ x ,

· x γ

¸

, F (¯¯ x) ,

· γI F^T(x) F (x) I

¸

, f (¯¯x) , γ ,

then ¯F is an affine function of ¯x and the problem to minimize the max- imum eigenvalue of F (x) is equivalent to determining inf ¯f (¯x) subject to the LMI ¯F (¯x) > 0. Hence, this is an optimization problem with a linear objective function ¯f and an LMI constraint.

Example (Simultaneous stabilization)

Consider k LTI systems with n-dim state space and m-dim input space:

˙x = A_ix + B_iu

where A_i ∈ IR^n×n and B_i ∈ IR^n×m, i ∈ 1, · · · , k. We’d like to find a state feedback law u = F x, F ∈ IR^m×n such that the eigenvalues λ(A_i+ B_iF ) lie on the LHP for i ∈ 1, · · · , k. From the example above, this is solved when we find matrices F and X_i, i ∈ 1, · · · , k such that for i ∈ 1, · · · , k,

½ X_i > 0

(A_i+ B_iF )^TX_i+ X_i(A_i+ B_iF ) < 0 (6) Note that this is not a system of LMIs in X_i and F . If we introduce Y_i = X_i⁻¹ and K = F Y_i, then (6) becomes

½ Y_i > 0

A_iY_i+ Y_iA^T_i + B_iK + K_i^TB_i < 0 ,

which can be further simplified by assuming the existence of a joint Lyapunov function, i.e. X_i = · · · = X_k = X. The joint stabilization problem has a solution if this system of LMIs is feasible.

15.3 Nominal Performance Consider

x = Ax + Bu (7)

y = Cx + Du (8)

with state space X = IRⁿ, input space U = IR^m and output space Y = IR^p. 15.3.1 H_∞ nominal performance

Proposition 15.2 If the system (7) is asymptotically stable then ||G||_∞<

γ whenever there exists a solution K = K^T > 0 to the LMI

· A^TK + KA + C^TC KB + C^TD B^TK + D^TC D^TD − γ²I

¸

< 0. (9)

Proof requires discussion on linear dissipative systems. See Scherer, if interested.

Therefore, we can compute the smallest possible upper bound of the L2- induced gain of the system (which is the H_∞ norm of the transfer function) by minimizing γ > 0 over all variables γ and K > 0 that satisfy the LMI (9).

15.3.2 H₂ nominal performance

Suppose that we are interested only in the impulse responses of this system.

This means, that we take impulsive inputs of the form u(t) = δ(t)e_i with e_i the i_th basis vector in the standard basis of the input space IR^m. (i runs from 1 till m). With zero initial conditions, the corresponding output yⁱ belongs to L₂ and is given by

yⁱ(t) =





C exp(At)Be_i for t > 0 De_iδ(t) for t = 0

0 for t < 0.

.

Only if D = 0, the sum of the squared norms of all such impulse responses P_m

i=1||y_i||²₂ is well defined and given by Xm

i=1

||y_i||²₂ = trace Z _∞

0

B^T exp(A^t)C^TC exp(At)B dt

= trace Z _∞

0

C exp(At)BB^Texp(A^Tt)C^T dt

= trace Z _∞

−∞

G(jω)G^∗(jω) dω

where G is the transfer function of the system.

Proposition 15.3 Suppose that the system (7) is asymptotically stable (and D = 0), then the following statements are equivalent.

(a) ||G||₂< γ

(b) there exists K = K^T > 0 and Z such that

· A^TK + KA KB

B^TK −I

¸

< 0;

· K C^T

C Z

¸

> 0; trace(Z) < γ² (10)

(c) there exists K = K^T > 0 and Z such that

· AK + KA^T KC^T

CK −I

¸

< 0;

· K B

B^T Z

¸

> 0; trace(Z) < γ² (11)

Proof. . note that ||G||₂ < γ is equivalent to requiring that the controlla- bility gramian W_c:=R_∞

0 exp(At)BB^Texp(A^Tt) dt satisfies trace(CW C^T) <

γ². Since the controllability gramian is the unique positive definite solution to the Lyapunov equation AW + W A^T + BB^T = 0 this is equivalent to saying that there exists X > 0 such that

AX + XA^T + BB^T < 0; trace(CXC^T) < γ².

With a change of variables K := X⁻¹, this is equivalent to the existence of K > 0 and Z such that

A^TK + KA + KBB^TK < 0; CK⁻¹C^T < Z; trace(Z) < γ². Now, using Schur complements for the first two inequalities yields that

||G||₂< γ is equivalent to the existence of K > 0 and Z such that

· A^TK + KA KB

B^TK I

¸

< 0;

· K C^T

C Z

¸

> 0; trace(Z) < γ². The equivalence with (11) is obtained by a direct dualization and the obser- vation that ||G||₂= ||G^T||₂.

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 (11).

15.4 Controller Synthesis Let

˙x = Ax + B₁w + B₂u z_∞ = C_∞x + D_∞1w + D_∞2u

z₂ = C₂x + D₂₁w + D₂₂u y = C_yx + D_y1w

and

˙x_K = A_Kx_K+ B_Ky u = C_Kx_K+ D_Ky

be state-space realizations of the plant P (s) and the controller K(s) respec- tively.

Denoting by T_∞(s) and T₂(s) the CL TF from w to z_∞ and z₂, respec- tively, 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 γ₀.

• H₂ performance: maintains the H₂ norm of T₂ below ν₀.

• Multi-objective H₂/H_∞ controller design: minimizes the trade-off cri- terion of the form α||T_∞||²_∞+ β||T₂||²₂ 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,

˙

x_cl = A_clx_cl+ B_clw z_∞ = C_cl1x_cl+ D_cl1w

z₂ = C_cl2x_cl+ D_cl2w 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



 A_clX_∞+ X_∞A^T_cl B_cl X_∞C_cl1^T B_cl^T −I D_cl1^T C_cl1X_∞ D_cl1 −γ²I



 < 0 X_∞> 0

• H₂ performance: the LQG cost from w to z₂ does not exceed ν iff D_cl2= 0 and there exists a symmetric matrices X₂ and Q such that

· A_clX₂+ X₂A^T_cl B_cl B_cl^T −I

¸

< 0

· Q C_cl2^T X₂ X₂C_cl2^T X₂

¸

> 0 trace(Q) < ν²

• Pole placement: the CL poles lie in the LMI region D := {z ∈ C : L+M z +M^Tz < 0} with L = L¯ ^T = [λ_ij]_1≤i,j≤mand M = [µ_ij]_1≤i,j≤m iff there exists a symmetric matrix X_pol such that

[λ_ijX_pol+ µ_ijA_clX_pol+ µ_jiX_polA^T_cl]_1≤i,j≤m < 0 X_pol > 0 .

For tractability, we seek a single Lyapunov matrix X := X_∞ = X₂ = X_pol that enforces all three sets of constraints. Factorizing X as

X =

· R I

M^T 0

¸ · 0 S I N^T

¸₋₁

and introducing the transformed controller variables:

B_K := N B_K+ SB₂D_K C_K := C_KM^T + D_KC_yR

A_K := N A_KM^T + N B_KC_yR + SB₂C_KM^T + S(A + B₂D_KC_y)R , the inequality constraints on X are turned into LMI constraints in the vari- ables R, S, Q, A_K, B_K, C_K and D_K. And we have the following suboptimal LMI formulation of our multi-objective synthesis problem:

Minimize αγ²+ βtrace(Q) over R, S, Q, A_K, B_K, C_K, D_K and γ² satisfy-

ing:







AR + RA^T + B₂C_K+ C_K^TB₂^T A_K+ A + B₂D_KC_y B₁+ B₂D_KD_y1 F F A^TS + SA + B_KC_y+ C_y^TB_K^T SB₁+ B_KD_y1 F

F F −I F

C_∞R + D_∞2C_K C_∞+ D_∞2D_KC_y D_∞1+ D_∞2D_KD_y1 −γ²I





 < 0



 Q C₂R + D₂₂C_K C₂D₂₂D_KC_y

F R I

F I S



 > 0

· λ_ij

· R I I S

¸ + µ_ij

· AR + B₂C_K A + B₂D_KC_y A_K SA + B_KC_y

¸ + µ_ji

· (AR + B₂C_K)^T A^T_K (A + B₂D_KC_y)^T (SA + B_KC_y)^T

¸¸

1≤i,j≤m

< 0 trace(Q) < ν₀²

γ² < γ₀² D₂₁+ D₂₂D_KD_y1 = 0 . Given optimal solutions γ^∗, Q^∗ of this LMI problem, the closed loop

performances are bounded by

||T ||_∞≤ γ^∗, ||T ||₂ ≤p

trace(Q^∗) .

This has been implemented by the matlab command “hinfmix”.

15.5 Affine combinations of linear systems

Often models uncertainty about specific parameters is reflected as uncer- tainty in specific entries of the state space matrices A, B, C, D. Let p = (p₁, ..., p_n) denote the parameter vector which expresses the uncertain quan- tities in the system and suppose that this parameter vector belongs to some subset P ⊂ IRⁿ. Then the uncertain model can be thought of as being parameterized by p ∈ P through its state space representation

˙x = A(p)x + B(p)u (12)

y = C(p)x + D(p)u . (13)

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 (12) defines a linear time varying dynamical system and it can therefore

also be viewed as such. If components of p are time varying and coincide with state components then (12) 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) = A₀+ p₁A₁+ · · · + p_nA_n (14) B(p) = B₀+ p₁B₁+ · · · + p_nB_n (15) C(p) = C₀+ p₁C₁+ · · · + p_nC_n (16) D(p) = D₀+ p₁D₁+ · · · + p_nD_n. (17) Or, written in a more compact form

S(p) = S₀+ p₁S₁+ ... + p_nS_n where

S(p) =

· A(p) B(p) C(p) D(p)

¸

is the system matrix associated with (12). We call these models affine parameter dependent models. In MATLAB such a system is represented with the routines psys and pvec. For n = 2 and a parameter box

P , {(p₁, p₂)| p₁ ∈ [p^min₁ , p^max₁ ], p₂∈ [p^min₂ , p^max₂ ]}

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, ˙p_i(t) can be specified by adding a third argument “rate” when calling “pvec”. See also the following routines:

• pdsimul for time simulations of affine parameter models

• aff2pol to convert an affine model to an equivalent polytopic model

• pvinfo to inquire about the parameter vector References

[1 ] C. Scherer and S. Welland, Lecture Notes on Linear Matrix Inequality in Control

[2 ] Gahinet et al., LMI-lab Matlab Toolbox for Control Analysis and De- sign.

[3 ] S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, SIAM studies in Applied Mathematics, Philadelphia, 1994.