c 2005, 2007, 2009, 2011 Anders Helmersson, ISY, May 18, 2011

1 LMIs
A linear matrix inequality (LMI) is an affine matrix-valued function,
m
X
F (x) = F0 + xi Fi  0 (1)
i=1

where x ∈ Rm are called the decision variables and Fi = FiT ∈ Rn×n are
symmetric matrices.
A very important aspect of the LMI is that it defines a convex set. To see
this, let x1 and x2 be two solutions to an LMI problem, i.e. F (x1 )  0 and
F (x2 )  0. Then also any convex combination x = (1 − λ)x1 + λx2 , with
λ ∈ [0, 1] solves the LMI:

F (x) = F ((1 − λ)x1 + λx2 ) = (1 − λ)F (x1 ) + λF (x2 )  0. (2)

Efficient numerical methods have been developed to solve these kind of problems.
Some of thesemost efficient algorithms for solving LMI problems are based on
interior point methods. These methods are iterative and each iteration includes
a least squares minimization problem.

Example 1.1 Most LMIs are not formulated in the standard form (1) but
they can be rewritten as is shown in this example. Let us consider the following
Lyapunov problem: (
P = PT  0
AT P + P A ≺ 0.
Note that P enters linearly in both inequalities. To show how to rewrite this
into the standard LMI form, we assume that P ∈ R2×2 . Parametrize P as a
linear function in x:
     
1 0 0 1 0 0
P (x) = x1 + x2 + x3 = x 1 P1 + x 2 P 2 + x 3 P3 .
0 0 1 0 0 1
 
Then F (x) = diag P (x), −AT P (x) − P (x)A , or
   
P1 0 P2 0
F (x) = x1 + x 2
0 −AT P1 − P1 A 0 −AT P2 − P2 A
 
P3 0
+ x3 ,
0 −AT P3 − P3 A

which is in the form (1) with F0 = 0. In this case three decision variables are
needed. In general we need n(n + 1)/2 decision variables for symmetric matrices
and n2 for full square matrices of size n × n. 2

1.1 Some Standard LMI Problems

Some standard LMI problems are listed in [2]. The most important ones are

1
LMIP: The LMI problem is to find a feasible x such that F (x)  0 or to
determine if the LMI is infeasible.
As an example of an LMIP we take the problem in example 1.1 of finding
a Lyapunov matrix P = P T  0 such that

AT P + P A ≺ 0. (3)

EVP/PDP: The eigenvalue problem (EVP) is to minimize the maximum eigen-

value of a matrix A(x) that depends affinely on a variable subject to an
LMI constraint. That is

min{λ : λI − A(x)  0, B(x)  0}. (4)

λ,x

This is equivalent to minimizing a linear function of x subject to an LMI

constraint:
min{cT x : F (x)  0}. (5)
x

The latter formulation is called positive definite programming (PDP) or,

if the inequality is nonstrict, semidefinite programming (SDP) [12].
As an example of an PDP we consider the bounded real lemma (lemma 2),
which determines the H∞ norm of a system G(s) = D + C(sI − A)−1 B
by minimizing γ with respect to P  0 subject to

P A + AT P P B C T
 
 BT P −γI DT  ≺ 0.
C D −γI

Note that the LMI problem, F (x)  0 can be formulated as an EVP by

min{λ : F (x) + λI  0} ≤ 0, (6)

λ,x

for which a feasible point, (λ, x), can be easily found for any initial x by
choosing λ sufficiently large.
GEVP: The generalized eigenvalue problem is to minimize the maximum gen-
eralized eigenvalue of a pair of matrices that depend affinely on a variable,
subject to an LMI constraint. The general form of a GEVP is

min{λ : λB(x) − A(x)  0, B(x)  0, C(x)  0} (7)

λ,x

where A(x), B(x) and C(x) are symmetric matrices that depend affinely
(linearly) on x ∈ Rm .
As an example of a GEVP we take the problem of finding the upper
bound ν of the complex µ value of a matrix M . This problem is solved by
minimizing ν > 0 (or equivalently ν 2 ) with respect to P  0 subject to

M ∗ P M ≺ ν 2 P.

The GEVP problem is not convex but quasi-convex.

2
1.2 Interior Point Methods
1.2.1 Analytic Center of an Affine Matrix Inequality
We will here consider a general affine matrix inequality F (x)  0, where
m
X
F (x) = F0 + x i Fi
i=1

and Fi = FiT ∈ Rn×n . Without loss of generality, assume that the matrices
F1 , . . . , Fm are linearly independent. Denote the feasible set by X :
X = {x ∈ Rm : F (x)  0} (8)
The function
log det F −1 (x) x ∈ X

φ(x) =
∞ x∈6 X
is finite if and only if x ∈ X , and becomes infinite as x approaches the boundary
of X ; φ is called a barrier function for X . There are other barrier functions, but
this one enjoys many special properties including that it is analytic and strictly
convex when x ∈ X .
Suppose now that X is nonempty and bounded. Denote the unique mini-
mizer with
x? = arg min φ(x). (9)
x
?
We refer to x as the analytic center of the affine matrix inequality F (x) 
0. Equivalently, F (x? ) has maximum determinant among all positive definite
matrices of the form F (x). Note that the analytic center x? is a property of
F (x) and not of X . Two F s may define the same X but may have different x? .
Newton’s method, with appropriate step length selection, can be used effi-
ciently to compute x? , given an initial point in X . Note that a feasible point
can be found by first solving an auxiliary problem defined by λI + F (x)  0,
where λ is chosen sufficiently large. Then λ is minimized until it becomes less
than zero.
We consider the algorithm:
x(k+1) = x(k) − α(k) H(x(k) )−1 g(x(k) )
where α(k) is the damping factor of the kth iteration, g(x) and H(x) are the
gradient and the Hessian respectively:
gi (x) = − tr F (x)−1 Fi
= − tr F (x)−1/2 Fi F (x)−1/2

Hij (x) = tr F (x)−1 Fi F (x)−1 Fj

  
= tr F (x)−1/2 Fi F (x)−1/2 F (x)−1/2 Fj F (x)−1/2 .

Nesterov and Nemirovsky [10] give a simple step length rule appropriate for a
general class of so called self-concordant barrier functions. Their damping factor
depends on a quantity that they call the Newton decrement of φ at x:

δ(x) = H(x)−1/2 g(x) .

3
The Nesterov-Nemirovsky damping factor is

δ(x(k) ) ≤ 1/4

(k) 1
α =
1/(1 + δ(x )) δ(x(k) ) > 1/4.
(k)

Nesterov and Nemirovsky show that this step length always results in x(k+1) ∈
X . Moreover, for δ(x(k) ) < 1/4, we have δ(x(k+1) ) ≤ 2δ(x(k) )2 . Thus, the
algorithm converges quadratically once we start taking undamped Newton steps.
A better step length can be obtained by exact line-search, i.e.

α(k) = arg min φ(x(k) + αv (k) ),

α

(k) (k) −1 (k)

where v = −H(x ) g(x ).
The undamped Newton step −H(x)−1 g(x) can be interpreted as the solution
of the weighted least squares problem:

H(x)−1 g(x) = arg min F (x)−1/2 F (x − v)F (x)−1/2

v F
m

X
−1/2 −1/2
= arg min I − vi F (x) Fi F (x) .

v
i=1 F

where k.kF denotes the Frobenius norm of a matrix. The Frobenius norm is the
square root of the sum of squares of all elements of the matrix, or equivalently
kF k2F = tr F T F .

1.2.2 The Path of Centers

Consider the standard EVP/PDP:

λopt = min{cT x : F (x)  0}.

x

For each λ > λopt the LMI

F (x)  0, cT x < λ (10)

is feasible. Assuming that (10) has a bounded feasible set the analytic center
exists, which is denoted by x? (λ). The curve defined by x? (λ) for λ > λopt is
called the path of centers for the EVP/PDP. It is analytic and has a limit as
λ → λopt , which is the optimal solution.

1.2.3 Methods of Centers

Perhaps the simplest optimization algorithm based on the notion of analytic
center is the method of centers [8]. Consider the GEVP:

min{λ : λB(x) − A(x)  0, B(x)  0, C(x)  0}.

λ,x

The algorithm is initialized with λ(0) and x(0) with λ(0) B(x(0) ) − A(x(0) )  0
and C(x(0) )  0, and proceeds as follows:

λ(k+1) = (1 − θ) λmax (A(x(k) ), B(x(k) )) + θ λ(k)

x(k+1) = x? (λ(k+1) )

4
where 0 < θ < 1, λmax is the maximum generalized eigenvalue and x? (λ) de-
notes the analytic center of diag[λB(x) − A(x), C(x)]. Simple proofs of the
convergence of this algorithm are given in [1, 2]. Among interior-point meth-
ods, the method of centers is not the most efficient. The most efficient methods
today appear to be primal-dual methods and projective methods [10].

1.2.4 Primal and Dual Methods

Primal-dual methods have been developed for positive definite programming
(PDP) and semidefinite programming (SDP) [12].

1.2.5 Duality
Consider the EVP/PDP
( m
)
X
∗ T
p = inf c x : F (x) = F0 + xi Fi  0 . (11)
x
i

Associated with this, the so called primal problem, there is a dual problem
defined by
d∗ = sup {− tr F0 Z : tr Fi Z = ci } . (12)
Z=Z T ≥0

The dual problem itself can be reformulated as an LMI. It is easy to show

p∗ ≥ d∗ . If there exists a strict solution to either of the problems then it can
also be shown that p∗ = d∗ . The primal-dual formulation offers a number of nice
properties. One of them is that the interval of the optimal solution is given, since
both an upper bound, cT x, and a lower bound, tr F0 Z, are provided. Specif-
ically, nonfeasibility can be shown using the primal-dual formulation. Also,
computational advantages can be made in the solution of the LMI problem [12].

Example 1.2 We want to determine if

 
x−4 x−3
F (x) =  0, (13)
x−3 2

is feasible or not. Introduce the auxiliary EVP/PDP as defined in (6) with

x2 = λ:
         
∗
  x1 −4 −3 1 1 1 0
p = inf 0 1 : F̃ (x) = + x1 + x2 0 .
x x2 −3 2 1 0 0 1

Then (13) is feasible if p∗ < 0. The dual problem is given by (12). We first
solve Z with respect to tr F̃1 Z = 0 and tr F̃2 Z = 1. Then
 
n o −2ζ ζ
d∗ = sup − tr F̃0 Z(ζ) = −2 − 6ζ , with Z(ζ) = ≥ 0.
Z(ζ)≥0 ζ 1 + 2ζ

Since any ζ ∈ [−0.4, 0] satisfies Z ≥ 0, we obtain d∗ = 0.4 and infer that (13) is
not feasible (p∗ ≥ 0.4). Note that only one Z is needed to show the infeasibility
of (13). 2

5
1.3 Complexity
The best methods available for solving LMIs are efficient, even if they are more
complex than most matrix manipulations, such as matrix inversions and solving
Riccati equations. The LMI solvers based on interior point methods are iterative
and solve a least squares problem in each iteration. Rather surprisingly, the
number of iterations is practically almost independent of the size of the LMI
problem. Typically, 5 to 50 iterations are needed. An upper bound on the
number of iterations needed can be found but the typical performance is better
than that bound. To improve efficiency further, the structure of the LMI can
be exploited for reducing the computational effort to solve the least squares
problem.
The primal-dual interior point method presented in [12] has a proved the
worst-case complexity in terms of arithmetic operations of O(m2.75 L1.5 ), where
m is the number of decision variables and L is the number of constraints. This
result applies to a set of L Lyapunov inequalities. Typical performance is much
better, for which a complexity of O(m2.1 L1.2 ) is reported.

1.4 Software Packages

A number of toolboxes are available for solving LMIs. One such toolbox is the
LMI Control Toolbox [6] to be used within Matlab. Other toolboxes are the
LMItool [7, 4] and sdpsol [3].
A few years ago, a Matlab interface called Yalmip [9] became available.
Yalmip works as an high-level interface to some of the most popular LMI solvers.
See http://control.ee.ethz.ch/~joloef/yalmip.php for more information.

1.5 Some Matrix Problems

1.5.1 Minimizing Matrix Norms
A simple problem that can be formulated as an LMI is to minimize the maximum
singular value of a matrix that is an affine function of some parameters. Assume
that F ∈ Rm → Rn×n is an affine matrix function. Then the problem of
minimizing σ̄(F (x)) is equivalent to minimizing
r
minm {β : F T (x)F (x) ≤ βI}, (14)
x∈R
β>0

or
−γI F T (x)
   
min γ: ≤0 , (15)
x∈Rm F (x) −γI
γ>0

which are LMIs in (x, β) and (x, γ) respectively. The equivalences follow by
observing that the eigenvalues of F (x)T F (x) are equal to the square of the
singular values of F (x). Specifically, σ̄(F (x)) ≤ γ is equivalent to F (x)T F (x) ≤
γ 2 I. We then use the Schur complement formula followed by a diagonal pre and
post scalings by diag[γ −1/2 I, γ 1/2 I], to obtain (15).
If F (x) is a vector then the maximum singular value is equal to the Euclidian
norm, that is the square root of the sum of squares. Thus, least squares problems
can be combined LMI constraints.

6
1.5.2 Minimizing Condition Number
When solving LMIs it is important to consider the numerical aspects of the
problem in order to get a reliable solution. The problem we are focusing on
here is generally of the type F (P )  0 where F is a function of a matrix P .
In order to find a reliable solution we can try to keep the condition number of
P as low as possible [2]. The condition number is defined as the ratio of the
largest and the smallest singular value. If we assume that P is a symmetric and
positive definite matrix the singular values and the eigenvalues coincide. Thus
the condition number of P is less than γ if and only if there exists a µ, such
that
µI ≺ P ≺ γµI.
Suppose that
m
X m
X
F (x) = F0 + xi Fi , P (x) = P0 + x i Pi .
i=1 i=1

Defining new variables x̄ = x/µ and ν = 1/µ, we obtain an EVP. Minimize γ

subject to
Xm Xm
νF0 + x̄i Fi  0, I ≺ νP0 + x̄i Pi ≺ γI.
i=1 i=1
Another similar problem is to find a nonsingular scaling matrix T of a given
structure, such that the condition number of T T P T is minimized. This problem
is equivalent to minimizing γ subject to
µI ≺ T T P T ≺ γµI or µT −T T −1 ≺ P ≺ γµT −T T −1
with respect to T , µ > 0 and γ. Introducing W = γµT −T T −1 yields
W ≺ P, and γ −1 P ≺ W,
which is an EVP with respect to γ −1 .

1.5.3 Treating Complex-Valued LMIs

When using an LMI solver it usually only accepts real-valued problems. In
order to handle complex-valued LMIs, we need to turn these into real-valued
ones. This can be done by using the following observation. The field of complex
numbers, a + jb ∈ C, is isomorphic to the field of 2 × 2 matrices with the
a b
structure −b a ∈ R2×2 . Thus, the product P = X + jY of two complex
matrices M = A + jB and N = C + jD can be computed using a real-valued
matrix multiplication
    
X Y A B C D
= . (16)
−Y X −B A −D C
Also, a Hermitian matrix P = P ∗ = X + jY is positive definite if and only if
 
X Y
 0. (17)
−Y X
Since the dimensions of the matrices double, the complexity of a complex-valued
LMI is significantly higher than a real-valued LMI of the same dimension. Thus
we should always try to use as much of the structure of the problem as possible
and, for instance, avoid to treat a real-valued LMI as a complex one.

7
2 Performance Bounds
Consider a dynamic system described by a differential equation
ẋ = f (x, w) (18)
and a performance criterion, Jw ∈ Rn → R:
Z T
Jw (x(t)) = g(x(τ ), w(τ ))dτ (19)
t

where x ∈ R → Rn is the state vector as a function of time, w ∈ R → Rm is the

input (or disturbance) vector and g ∈ Rn × Rm → R is the cost function.
The time variable t can be included in the state-space vector x by having a
state xi such that ẋi = 1 and xi (t) = t.
Theorem 1. A strict upper bound V for the performance criterion Jw , such
that Jw (x) < V (x) for all w, can be established if there exists a continuously
differentiable, positive definite Lyapunov or storage function (see [13]), V , that
makes the Hamiltonian, H, negative for all x and w:
H = g(x, w) + Vx (x)f (x, w) < 0, ∀x, w, (20)
∂
where Vx = ∂x V denotes the partial derivative of V with respect to x.
Proof.
Z T
Jw (x(t)) = g(x, w)dτ
t
Z T
= g(x, w)dτ + V (x(T )) − V (x(t)) + V (x(t)) − V (x(T ))
t
Z T  
≤ g(x, w) + V̇ (x) dτ + V (x(t))
t
Z T
= (g(x, w) + Vx (x)f (x, w)) dτ + V (x(t)) < V (x(t)).
t

This theorem can be modified to a nonstrict version by replacing < with ≤.

Here we will use this inequality to provide conditions for stability and per-
formance bounds on linear systems subject to nonlinear disturbances. We will
use the L2 [t, T ] norm as a performance criterion. We assume that x(t) = 0 and
that t = 0 and T = ∞ if nothing otherwise is stated. However, the analysis is
general and the L2 norm can easily be extended to any interval [t, T ].

3 Matrix Inequalities
3.1 Continuous Time
We will here study linear, stable systems subject to nonlinear uncertainties:
ẋ = Ax + Bw
(21)
z = Cx + Dw,

8
where w is the disturbance input and z is the performance output.
The aim of this section is to give criteria for assuring upper bounds of the
H∞ or L2 -induced norm from w to z for LTI system, i.e. to show that

kzk2 < γkwk2 ,

or equivalently
Z
kzk2 − γ 2 kwk2 = z T (t)z(t) − γ 2 wT (t)w(t)dt < 0.

For this problem the following cost function can be used

g(x, w) = kzk2 − γ 2 kwk2 = z T z − γ 2 wT w, (22)

and a quadratic Lyapunov function is chosen

V (x) = xT P x. (23)

To assure internal stability, it is assumed that the Lyapunov matrix P is sym-

metric and positive definite (P  0), that is xT P x > 0, ∀x 6= 0. If x(0) = 0 the
L2 -induced norm from w to z is less than one if the Hamiltonian for (21) and
(22) is negative for all x:

H = V̇ + g(x, w)
= ẋT P x + xT P ẋ + z T z − wT w
= xT P (Ax + Bw) + (Ax + Bw)T P x + (Cx + Dw)T (Cx + Dw) − γ 2 wT w.
(24)

In order to assure that kzk2 < γkwk2 then H < 0 must hold for all x and w.

3.2 The Riccati Inequality

One way of arriving at the related Riccati inequality is by completing the squares
in (24). First observe that by letting x = 0 it can be inferred that DT D < I
and thus R = γ 2 I − DT D is invertible. Then

H = xT AT P + P A + (B T P + DT C)T R−1 (B T P + DT C) + C T C x



T
− w − R−1 (B T P + DT C)x R w − R−1 (B T P + DT C)x

≤ xT AT P + P A + (B T P + DT C)T R−1 (B T P + DT C) + C T C x.

Equality is obtained for

w = R−1 (B T P + DT C)x, (25)

which can be interpreted as the worst-case disturbance.

3.3 Linear Matrix Inequalities (LMIs)

Instead of completing the squares, the Hamiltonian (24) can be rewritten into
 T 
P A + AT P + C T C P B + C T D
 
x x
H= < 0, (26)
w B T P + DT C DT D − γ 2 I w

9
which shall hold for all nonzero x, w. This implies that
P A + AT P + C T C P B + C T D
 
≺0 (27)
B T P + DT C DT D − γ 2 I
which is a linear matrix inequality (LMI) in P , for given (A, B, C, D). This
implies that the set of P satisfying the LMI is convex, which substantially
simplifies the search for P .

3.3.1 Schur Complements

The equivalence between the Riccati inequality and the LMI can be seen by the
following well-known fact:
Lemma 1 (Schur Complement). Suppose R and S are Hermitian, i.e. R = R∗
and S = S ∗ . Then, the following conditions are equivalent:
R ≺ 0, S − GT R−1 G ≺ 0; (28)
and
S GT
 
≺ 0. (29)
G R
h i
Proof. Post-multiply (29) by the nonsingular −RI−1 G I0 and pre-multiply by
its transpose:
I −GT R−1 S GT S − GT R−1 G 0
     
I 0
= ≺ 0,
0 I G R −R−1 G I 0 R
which is equivalent to the conditions in (28).
The Schur complement result can be generalized to nonstrict inequalities.
Using Schur complements we can infer that if a matrix is positive definite then
an arbitrary diagonal square sub-block is also positive definite. For instance, if
any diagonal element pii of a matrix P is negative or zero the matrix P is not
positive definite.

3.3.2 Congruence Transformations

When proving the Schur complements a so called congruence transformation is
employed. Let U be a nonsingular matrix, then
F 0 and U T F U  0, (30)
are equivalent statements. The inequality can be replaced by equality (=) or
nonstrict inequality (≥).
Applying the Schur complement on (27), which can be written as
P A + AT P P B
   T 
C  
T 2 + T I C D ≺ 0, (31)
B P −γ I D
yields
P A + AT P P B C T
 
 BT P −γ 2 I DT  ≺ 0. (32)
C D −I

10
By scaling P we can rewrite this into

P A + AT P P B C T
 
 BT P −γI DT  ≺ 0. (33)
C D −γI

3.3.3 Equivalent Matrix Inequalities

We have shown the equivalence between the Riccati inequality and the corre-
sponding LMI. They have different virtues, which will be employed when con-
venient. One of the objectives for choosing the LMI is that it in many cases
provides a simple tool for showing that the set of solutions is convex.
By repeating the Schur complement we arrive at the following equivalent
conditions:

σ̄(D) < γ,
(i)
AT P + P A + (B T P + DT C)T (γ 2 I − DT D)−1 (B T P + DT C) + C T C ≺ 0;

P A + AT P + C T C P B + C T D
 
(ii) ≺ 0;
B T P + DT C DT D − γ 2 I

P A + AT P P B C T
 

(iii)  BT P −γI DT  ≺ 0.
C D −γI

All but the first one of these inequalities are linear in P if (A, B, C, D) are kept
fixed. The last one of these inequalities (iii) is linear in (A, B, C, D) for a given
P , from which we conclude that the set of system matrices satisfying the Riccati
inequality or equivalently the LMI is convex. The bounded real lemma states
an extension of these results.
Lemma 2 (Bounded Real Lemma [11, 5]). The following statements are equiv-
alent
(i) kGk∞ < γ and A stable with G(s) = D + C(sI − A)−1 B;

(ii) there exists a solution P  0 to the LMI

P A + AT P P B C T
 
 BT P −γI DT  ≺ 0. (34)
C D −γI

Proof. We have already shown that (ii) ⇒ (i). By using the Kalman-Yakubovich-
Popov lemma, the opposite direction can proved.

4 The Elimination Lemma

Let U ⊥ denote any matrix of maximum rank that satisfies U ⊥ U = 0. To be
more precise: range U ⊥T = null U T .

11
Lemma 3. Let Q, U and V be given matrices. Then

Q + U KV T + V K T U T ≺ 0, (35)

has a solution K if and only if

(i) V ⊥ QV ⊥T ≺ 0,
(ii) U ⊥ QU ⊥T ≺ 0,

If V ⊥ or U ⊥ does not exist the corresponding condition is assumed to be satisfied.

Proof. We show the lemma by construction.
 Make a congruence transformation
of (35) using a nonsingular T = T1 T2 T3 T4 where the transformed rows
(and columns) correspond to the following disjunct spaces
(1) range T1 = null U T ∩ null V T

(2) range T2 = range U ∩ null V T

(3) range T3 = null U T ∩ range V
(4) range T4 = range U ∩ range V

Then, (35), is equivalent to

 
Q̃11 Q̃12 Q̃13 Q̃14
 Q̃T Q̃ Q̃ + K̃ Q̃ + K̃24 
 12 22 23 23 24
T T (Q + . . .)T =  T  ≺ 0 (36)

T T T
Q̃
 13 23Q̃ + K̃ 23 Q̃33 Q̃34 + K̃43 
Q̃T T T T T
14 Q̃24 + K̃24 Q̃34 + K̃43 Q̃44 + K̃44 + K̃44

where  
K̃23 K̃24 T
U KV T T3 T4
  
= T2 T3 (37)
K̃43 K̃44
can be chosen freely.
We first consider the the sub-matrix of Q̃ that comprises the first three rows
and columns. Eliminating the first row and column by Schur complement yields
Q̃11 ≺ 0 and
−1 −1
Q̃22 − Q̃T Q̃23 − Q̃T
 
12 Q̃11 Q̃12 12 Q̃11 Q̃13 + K̃23
−1 −1 ≺0 (38)
Q̃T T T
23 − Q̃13 Q̃11 Q̃12 + K̃23 Q̃33 − Q̃T13 Q̃11 Q̃13

−1 −1
We can choose K̃23 = −Q̃23 + Q̃T T
12 Q̃11 Q̃13 , which yields Q̃22 − Q̃12 Q̃11 Q̃12 ≺ 0
T −1
and Q̃33 − Q̃13 Q̃11 Q̃13 ≺ 0 as remaining conditions together with Q̃11 ≺ 0.
These are equivalent to
   
Q̃11 Q̃12 Q̃11 Q̃13
≺ 0 and ≺0 (39)
Q̃T
12 Q̃22 Q̃T
13 Q̃33

which in turn is equivalent to condition (i) and (ii), respectively. Finally, includ-
ing the fourth row and column of (36), we can always find a constant K̃44 = −σI
provided conditions (i) and (ii) hold, by choosing σ large enough.

12
5 H∞ Synthesis using LMIs
The problem addressed here is the following. Suppose we are given a linear
time-invariant (LTI) plant, G, with state-space realization

ẋ = Ax + B1 w + B2 u
z = C1 x + D11 w + D12 u (40)
y = C2 x + D21 w + D22 u

where A ∈ Rn×n , D11 ∈ Rp1 ×m1 and D22 ∈ Rp2 ×m2 define the problem dimen-
sion.
From now on we assume that D22 is zero. If this is not the case we can find a
controller, K̄, for a modified G in which D22 is set to zero. Then the controller
for D22 6= 0 is K = K̄(I + D22 K̄)−1 . Hence there is now loss of generality in
assuming D22 = 0. See also [14, Section 17.2, page 454].
The output-feedback control problem consists of finding a dynamic controller
with state-space equations

ẋK = KA x + KB y (41)
u = KC x + KD y

where KA ∈ Rr×r that ensures internal stability and a guaranteed performance

bound, γ. The performance bound is defined as the H∞ norm of the closed loop
system from disturbance input signal, w, to the performance output, z.
We use the index K to denote the state-space matrices of the closed loop
system. If we assume that D22 = 0, we can write the closed loop system as
   
  A 0 B1 B2 0   
AK B K KD KC C2 0 D21
= 0 0 0 + 0 I  (42)
CK DK KB KA 0 I 0
C1 0 D11 D12 0

where AK ∈ R(n+r)×(n+r) . The closed loop system is internally stable and has
an H∞ norm of γ if there exists a symmetric P = P T  0 such that Lemma 2
holds or, equivalently,

P AK + AT T
 
K P P BK CK
T T 
 BK P −γI DK
CK DK −γI
     T
0 0 0 P 0   
A K B K I 0 0
=  0 −γI 0  +  0 0  +  ≺0 (43)
CK DK 0 I 0
0 0 −γI 0 I

Inserting this in (43) together with

   −1
X N Y M
P = =  0. (44)
NT L MT ∗

13
where N, M ∈ Rn×r yields

XA + AT X AT N XB1 C1T
 

 N TA 0 N T B1 0 

T T T
 B1 X B1 N −γI D11 
C1 0 D11 −γI
 
XB2 N   T
 N T B2 L  KD KC
 
C2 0 D21 0
+ 0
 +  ≺0 (45)
0  KB KA 0 I 0 0
D12 0
 
KD KC
Using Lemma 3, the existence of K = is equivalent to
KB KA

XA + AT X XB1 C1T 
 
 T 
NX 0 T  NX 0
 B1T X −γI D11 ≺0 (46)
0 I 0 I
C1 D11 −γI

and
AY + Y AT Y C1T B1
 
 T  
NY 0 Y C1 −γI D11  NY 0 ≺ 0
 (47)
0 I T T
0 I
B1 D11 −γI
 
where NX and NY designate any bases of the null spaces of C2 D21 and
B2T D12T
, respectively.
For showing (47) we have used
 ⊥  ⊥
XB2 N B2 0  −1  

T Y M 0 0

 N T B2 L  NY 0
 = 0 I P 0
 
 =  0 0 0 I
 0 0   0 0 0 I 0 I
0 0 I 0
D12 0 D12 0

A third LMI is required to link X and Y according to Lemma 4 below

 
X I
≥ 0. (48)
I Y

Note that (48) is equivalent to X − Y −1 ≥ 0.

Lemma 4. Suppose X = X T ∈ Rn×n and Y = Y T ∈ Rn×n . Let r be a positive
integer. The following statements are equivalent:
(i)  
X I
≥0 and rank (X − Y −1 ) ≤ r (49)
I Y

(ii) There exists P = P ∈ R(n+r)×(n+r) such that

   −1
X N Y M
P = = 0 (50)
NT L MT ∗

14
Proof. (i) ⇒ (ii): Factor X −Y −1 = N N T , where N ∈ Rn×r and let M = −Y N
and L = I. Then
   −1
X N Y −Y N
P = = 0 (51)
NT I −N T Y I + N T Y N

(ii) ⇒ (i): Using the Schur formulas for matrix inversion gives that Y −1 =
X −N L−1 N T . Hence, X −Y −1 = N L−1 N T ≥ 0, and indeed, rank (X −Y −1 ) =
rank (N L−1 N T ) ≤ r.
We conclude by stating the following theorem:
Theorem 2. The following statements are equivalent.

(i) There exists an controller of the system (40) or order r that achieves
closed-loop stability with H∞ norm of γ.
(ii) There exists X = X T , Y = Y T ∈ Rn×n , such that (46), (47) and (49)
hold.

In order to reduce rank (X − Y −1 ) we can instead minimize

 
X I
rank = n + rank (X − Y −1 ). (52)
I Y

One way to try to reduce the rank is to minimize tr X + tr Y , even if this does
not guarantee to find the minimum order controller for a given γ.

References
[1] S. Boyd and L. El Ghaoui. Method of centers for minimizing generalized
eigenvalues. Linear Algebra and Applications, special issue on Numerical
Linear Algebra Methods in Control, Signals and Systems, 188-189:63–111,
July 1993.
[2] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix In-
equalities in System and Control Theory. SIAM Studies in Applied Math-
ematics. SIAM, 1994.

[3] S. Boyd and S. Wu. sdpsol – A Parser/Solver Semidefinite Programs with

Matrix Structure – User’s Guide, Version Alpha. Stanford University, 1995.
[4] F. Delebecque, R. Nikoukhah, and L. El Ghaoui. LMITOOL: A Package
for LMI Optimization in Scilab – User’s Guide, 1995.
[5] P. Gahinet and P. Apkarian. An LMI-based parametrization of all H∞
controllers with applications. In IEEE Proceedings of the 32nd Conference
on Decision and Control, volume 1, pages 656–661, San Antonio, Texas,
December 1993.
[6] P. Gahinet, A. Nemirovski, A. J. Laub, and M. Chilali. The LMI control
toolbox. In Proceedings of the 3rd European Control Conference, volume 4,
part 1, pages 3206–3211, Rome, Italy, September 1995.

15
 [7] L. El Ghaoui, F. Delebecque, and R. Nikoukhah. LMITOOL: A User-
Friendly Interface for LMI Optimization – User’s Guide, Beta version,
1995.

[8] B. Lieu and P. Huard. La méthode des centres dans un espace topologique.
Numerische Mathematik, 8:56–67, 1965.
[9] J. Löfberg. YALMIP : A toolbox for modeling and optimization in MAT-
LAB. In Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
Available from http://control.ee.ethz.ch/~joloef/yalmip.php.
[10] Yu. Nesterov and A. Nemirovsky. Interior point polynomial methods in
convex programming: Theory and application. SIAM, 1993.
[11] C. Scherer. The Riccati Inequality and State-Space H∞ -Optimal Control.
PhD thesis, Universitat Wurtzburg, Wurtzburg, Germany, 1990.

[12] L. Vandenberghe and S. Boyd. Positive-definite programming. 1994. sub-

mitted to SIAM review.
[13] J. C. Willems. The generation of Lyapunov functions for input-output
stable systems. SIAM Journal of Control, 9:105–133, 1971.

[14] K. Zhou, J. C. Doyle, and K. Glover. Robust and Optimal Control. Prentice
Hall, 1995.

16