Low-Complexity Polytopic Invariant Sets For Linear Systems Subject To Norm-Bounded Uncertainty

This article has been accepted for publication in a future issue of this journal, but has not been
fully edited. Content may change prior to final publication. Citation information: DOI
10.1109/TAC.2014.2352692, IEEE Transactions on Automatic Control
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
Limited circulation. For review only
Low-complexity Polytopic Invariant Sets for Linear

Systems Subject to Norm-bounded Uncertainty
Furqan Tahir and Imad M. Jaimoukha
AbstractWe propose a novel algorithm to compute lowcomplexity polytopic Robust Control Invariant (RCI) sets, along
with the corresponding state-feedback gain, for linear discretetime systems subject to norm-bounded uncertainty, additive
disturbances and state/input constraints. Using a slack variable
approach, we propose new results to transform the original
nonlinear problem into a convex/LMI problem whilst introducing
only minor conservatism in the formulation. Through numerical
examples, we illustrate that the proposed algorithm can yield
improved maximal/minimal volume RCI set approximations in
comparison with the schemes given in the literature.
Index TermsRobust Control Invariant set, norm-bounded
uncertainty, Slack variables, S-Procedure, Optimization.
I. I NTRODUCTION
Obust Control Invariant (RCI) sets are of great significance in the robustness analysis and synthesis of
controllers for uncertain systems. These sets play an important
role in establishing stability and recursive feasibility of Robust
Model Predictive Control schemes [1], [2] and are also used
as target sets in robust time-optimal control schemes [3].
Invariant set computation has been the subject of extensive research over the past several decades [4]. Important
results have been reported in [5], [6], including necessary
and sufficient conditions for invariance using Farkas Lemma
and derivation of (piecewise) linear control law to achieve
closed-loop invariance. An iterative set-computation approach
to compute suitable approximations of minimal invariant set
for systems subject to additive disturbances was presented in
[7]. Optimization of RCI sets with respect to the control law
has been considered in [8]. Finally, for systems with polytopicuncertainty, an algorithm to compute low-complexity RCI
(LC-RCI) sets along with controller K, is proposed in [9].
All the above schemes deal only with systems involving
disturbance or polytopic uncertainty. An exception to this
is [10] which proposes (hyper-rectangle) invariant sets for
systems with norm-bounded uncertainties. However, the hyperrectangle set structure is generally a conservative choice. In
this technical note, we develop an algorithm to compute LCRCI sets, along with the corresponding gain K, for linear systems subject to both additive disturbances and norm-bounded
uncertainty as well as constraints on the state and input. Here,
note that while a nonlinear control law is the least conservative
(and sometimes the only) choice [11], many schemes use linear
F. Tahir is with Perceptive Engineering Limited, Cheshire WA4 4AB,
U.K. I. M. Jaimoukha is with the Control and Power Group, Department of
Electrical and Electronic Engineering, Imperial College, London SW7-2AZ,
U.K. E-mail: [email protected], [email protected].
Manuscript received ...;
feedback due to computational ease (see e.g. [12], [9] and the
references therein). Similarly, LC-RCI target sets hold significant computational advantages (in comparison to ellipsoidal
or general polyhedral RCI sets) for the associated control
schemes (e.g. MPC) particularly for higher order systems [9].
However, as shown in Section II, the computation of such
sets is a highly nonlinear problem owing to the presence of
uncertainty as well as both the RCI set and feedback gain being
treated as decision variables. Using a slack variable approach
[13], we propose general results to linearize the problem whilst
introducing only minor conservatism in the algorithm. An
initial, constraint admissible RCI set and corresponding K are
computed through a convex/LMI problem. Then, the volume
of this set is iteratively optimized. Through examples from
the literature, we show that both the initial and final RCI
sets computed by the proposed algorithm are larger than those
obtained using the scheme in [9]. Furthermore, the proposed
scheme can also compute, in one-step, hyper-rectangle RCI
sets which have better volume than those obtained using [10].
This technical note is organized as follows. Section II
provides a description of the system, formulates the LCRCI set problem and highlights the associated nonlinearities.
In Section III, we propose general results, based on slack
variables, which allow us to linearize the problem. We give
numerical examples in Section IV and conclude in Section V.
nm
, kAk :=
qThe notation used is fairly standard. For A R
(AAT ), where () denotes the largest eigenvalue. For

A = AT , A 0 ( 0) indicates that A is positive (semi)definite.
The matrix diag(A1 , . . . , Am ) is the block diagonal matrix
whose ith diagonal block is Ai . For x, y Rn , x y is
interpreted element-wise. The symbols Iq and 0p,q denote the
q q identity and the p q null matrices with the subscripts
omitted when they can be inferred from the context. The
symbol ei denotes the ith column of a suitable identity matrix.
Applying a congruence T , where T has full column rank, on
A 0 ( 0) corresponds to pre and postmultiplying by T T
and T , respectively, to deduce that T T AT 0 ( 0). A Schur
T
complement argument
refers

to the result that if A = A and
A B
C = C T 0 then
0 if and only if ABC 1 B T 0
? C
where ? refers to terms readily inferred from symmetry.
To deal with uncertainty, we use the following lemma [14].
Lemma I.1. Let R = RT , F, E, H be real matrices of
appropriate dimensions and define
:= {diag(1 Iq1 , , l Iql , l+1 , , l+r ) :
i R, |i | 1 , i Rqi qi , kk 1}
Preprint submitted to IEEE Transactions on Automatic Control. Received: August 25, 2014 08:44:37 PST
0018-9286 (c) 2013 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See
http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
(1)
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI
b = {(S, G) : S = S T 0, S = S, G+GTT = 0, }
B. RCI set formulation
Then, we have det(I H) 6= 0 and the inequality
In this subsection, we will first derive conditions for the

existence of an admissible invariant set of the form given in
(5). Subsequently, we analyse these conditions and discuss the
associated nonlinearities.
R + F (I H)1 E + E T (I T H T )1 T F T 0
b such that
is satisfied for all if there exist (S, G)
R
E T + F GT
FS
?
S + HGT + GH T
HS 0.
?
?
S
We also refer to the S-procedure. This is a family of procedures used to derive necessary and/or sufficient conditions,
typically in the form of LMI conditions, for the non-negativity
or non-positivity of a quadratic function on a set described by
quadratic inequality constraints [15].
II. LC-RCI S ET P ROBLEM
In this section, we first give a description of the system
and constraints. Subsequently, we derive the conditions for
invariance and highlight the inherent problem-nonlinearities.
Theorem II.1. There exist admissible Z and K if, for all

m Nx := {1, , nx }, j Nu := {1, , nc } and
b and diagonal,
i Nn := {1, , n}, there exist (Si , Gi ) ,
m
j
i
positive semidefinite D , Du and Dx as solutions to the
matrix inequalities:

T m

T j
C Du C 12 K TN T ej
C D C 12 T T em
0,
0 (9)
?
eTj udTDuj d
? eTm xdTDm d
T i
C Dx C
?
?
? ?
i
Dw
?
? ?
1 T0
1
T
i
ei CAK ei CBw eTiddTDxi dv TDw
v
? ?
2
0 (10)
2
CqK
0
12 Gi BpT C Tei Si ?
0
0
12 Si BpT C Tei
0 Si
Proof. Since Z and W are symmetric, the invariance constraint (6) can be written as
eTi C[(AK + Bp CqK )x + Bw w] eTi d 0
A. System Description and Constraints

In this work, we consider a constrained, linear, discrete-time
uncertain system [2]
xk+1 =(A+Bp Cq )xk +(Bu +Bp Dqu )uk +Bw wk (2)

xk X = x Rn : T x x , uk U = u Rnu : N u u (3)
where xk Rn , uk Rnu and wk Rnw are the state, input,
and bounded disturbance vectors (respectively) at step k; A is
the state matrix and Bu , Bw and Bp , Cq and Dqu are the input,
disturbance and uncertainty distribution matrices, respectively,
and where T Rnx n , 0 < x Rnx , N Rnc nu , 0 < u Rnc
are given and define the state and input constraints in (3). We
consider polytopic disturbances of the form:

wk W := w Rnw : v w v
(4)
(11)
i Nn , x Z, w W, . It can be verified that for

i
any Dxi and Dw
, the lefthand side of (11) can be written as
i
i
(dCx)TDxi (Cx+d)(vw)TDw
(w+v)y TLi (Dxi , Dw
, )y
i
where y T := [xT wT 1], and Li (Dxi , Dw
, ) :=
T i
C Dx C
0 12 (AK + Bp CqK )T C T ei
i
T T
21 Bw
C ei
?
Dw
T
T i
T i
?
?
ei d d Dx d v Dw v
Using the S-procedure (Farkas Theorem) [15], it follows that

the existence of diagonal, positive semidefinite matrices Dxi
i
i
, ) 0, i Nn , is
such that Li (Dxi , Dw
and Dw
necessary and sufficient for invariance. It is easy to verify that
this condition can be re-written in the form
where d Rn is a vector of ones and C Rnn is a square

matrix with det(C) 6= 0. An RCI set is defined as follows [3]:
Ri + Fi (I H)1E + E T (I TH T )1TFiT 0, (12)

Ri Fi
where
:=
E
H
T i
C Dx C
0
21 ATK C T ei
0
i
T T
Dw
12Bw
C ei
0
1 T0
1 T
i
ei CAK 1 eTi CBw eTid dTDxi dv TDw
v 2 ei CBp
2
2
CqK
0
0
0
Definition II.1. The set Z Rn is an RCI set under linear

state-feedback for the system in (2) subject to the constraints
in (3) if there exists a control law u = Kx such that
Finally, an application of Lemma I.1 on (12) yields the

invariance condition in (10).
Next, we write the input constraints in (8) as
(AK + Bp CqK )Z Bw W Z
eTj N Kx eTj u 0, x Z, j Nu
nw
for given 0 < v R . The system is also subject to normbounded model uncertainty , with defined in (1).
We consider LC-RCI sets of the form [9]:

Z := x Rn : d Cx d
(5)
(6)
Z X
(7)
KZ U
(8)
where denotes the Minkowski sum, AK := A + Bu K and

CqK := Cq +Dqu K. An RCI set Z of the form (5) and a statefeedback matrix K satisfying (6)(8) are called admissible.
It can be verified that, for any Duj ,

eTj N Kx eTj u = (d Cx)T Duj (Cx + d) y TLju (Duj )y
where y T := [xT 1] and Lju (Duj ) is defined in the first
inequality of (9). Using the S-procedure, it follows that the
existence of diagonal, positive semidefinite matrices Duj such
that Lju (Duj ) 0, j Nu , is necessary and sufficient for

the satisfaction of input constraints and this is given by the
first inequality in (9). Analogously, using the S-procedure, it
can be verified that the second inequality in (9) is a necessary
and sufficient condition for (7).
Note that the problem of computing an admissible RCI set
and control law is nonlinear in the variables C and K - it is
in fact not even bilinear. From Theorem II.1, we see that the
main source of nonlinearity is due to terms of the form C TDi C
and eTi CBz X where z stands for p or u and X stands for K,
Gi or Si . The problem is further complicated by the fact that
decision variable matrix C is not exposed from either side
in the eTi CBz X terms which prevents the use of congruence
transformation techniques for linearization. In the following
we propose an LMI optimization to compute C and K.
Remark II.1. Note that the conditions in Theorem II.1 become
linear when the RCI set (5) is considered to be a hyperrectangle, i.e. C = := diag(1 , , n ) 0. To see
this, apply congruence transformation diag(C T , I, I, I, I)
on (10), followed by multiplication with 1
i . Then, noting
that eTi C = i eTi , applying the congruence transformation
diag(I, I, I, i I, i I) and subsequently introducing the re1 i
i
i
i
:= KC 1 , Dw
:= 1
definitions K
i Dw , Dx := i Dx ,
Gi := i Gi , and Si := i Si renders (10) linear in variables
and C 1 (= 1 ). Constraint conditions in (9) can simK
ilarly be linearized by respectively applying the congruence
diag(C T , I) and using the above re-definitions.
Remark II.2. Note that the Farkas theorem (S-procedure)
used in Theorem II.1 is lossless. Furthermore, there is no
gap in Lemma I.1 for the case of unstructured uncertainties
[14]. Therefore, conditions (9)-(10) become both necessary
and sufficient for the existence of (constraint admissible) LCRCI sets for systems subject to additive disturbances and
unstructured uncertainties. Note also that for such systems,
(9)-(10) become necessary and sufficient LMI conditions to
compute a K that renders a given set C invariant (which is
also a problem treated in literature). Finally, for the nominal
case (i.e. no uncertainty or disturbances), the variables Si , Gi
i
and Dw
disappear, together with the corresponding rows and
columns in all the above matrix inequalities.
III. T HE PROPOSED ALGORITHM
In this section, we first propose general theorems - based on
slack variables - which allow us to remove the aforementioned
nonlinearities in the RCI set problem. A cost function is then
incorporated in the formulation to optimize the set volume.
A. Linearization procedure for the RCI set problem
As part of our main result, we now propose the following
two theorems. Theorem III.1 enables us to expose C and
separate it from the other variables K, Si and Gi (in the
matrix inequalities of Theorem II.1) without introducing any
conservatism/approximations. Theorem III.2 uses slack variables to give necessary and sufficient conditions for separating
bilinear terms of the form XY + Y TX T . These results allow
to linearize the RCI set problem in Theorem III.3.
Theorem III.1. Let R = RT , Z = Z T , A and B denote matrices of appropriate dimensions. Then the following statements
are equivalent:

R AB
(i) L :=
0.
?
Z
1 T T
(ii) Z 0, L0 := R
ABZ B A 0.

R
A
X B
T
(iii) X = X : L1 :=
0, L2 :=
0.
? X 1
? Z
Proof. Note first that (i)(ii) follows from a Schur complement argument. Therefore we only prove (ii)(iii).
(ii)(iii): Suppose (ii) is satisfied. Then, there exist
scalars > 0 and > 0 such that L0 I and
I AAT 0. Let X = BZ 1 B T +I. Then
X BZ 1B T = I 0
L2 0.
Furthermore, for this choice of X, and , we have

RAXAT = RABZ 1 B TAT AAT I AAT 0
and therefore L1 0.
(iii)(ii): Assume (iii) is satisfied for some X. Then,
using Schur complement argument
R AXAT 0,
X BZ 1 B T 0.
Therefore L0 = (RAXAT )+A(X BZ 1 B T )AT 0

and (ii) is satisfied.
Theorem III.2. The Bilinear Matrix Inequality (BMI)
L := Z + XY + Y TX T 0
(13)
is satisfied if and only if there exist matrix variables, of

appropriate dimensions, Q = QT 0, P = P T 0, G1 ,
P Y
G2 , F , and H such that M :=
0, and
? Q
Z +Q+XP X T F XG1 H XG2
?
G1 +GT1 P F T +G2 Y 0
(14)
?
?
H T +H Q
Proof. A manipulation shows that
XY + Y TX T = Q + XP X T V TM V
where V T := [X I]. Replacing the above expression in
(13), taking a Schur complement and performing
a congruence

G1 G2
T
transformation with diag(I, Mo ), Mo :=
, yields:
F
H

Z + Q + XP X T
V TMo
0.
(15)
?
MoTM 1Mo
To deal with MoTM 1Mo , we use the slack variable identity
MoTM 1Mo = Mo+MoTM+(MoM )TM 1(MoM ). (16)
Replacing, without loss of generality, the (2,2) block of (15)
by the first three terms on the right of (16) gives (14).
Remark III.1. Theorem III.1 allows us to separate the variables A and B, in the (1, 2) entry, without any approximation.
Similarly, Theorem III.2 provides a new result to separate the
variables X and Y in the (1, 1) entry without any conservatism. Both these results are general in nature and hence
also have potential applications in other control problems,
e.g. Lyapunov stability. Note that results to separate X and
Y have also been proposed in [13]. However, these require
Z (in (13)) to be multiplied by a variable which we need to
avoid so as to obtain linearity in RCI set problem.
We now propose the following result to compute an admissible RCI set Z and statefeedback gain K through LMIs.
Theorem III.3. There exist admissible Z and K if, for a
given positive R, and for all i Nn , m Nx and j Nu ,
b Xi = X T , Pi = P T , =
there exist matrices (Si , Gi ) ,
i
i
T
diag(1 , , n ) 0, Qi = Qi , Hi , Fi and Zi of appropriate
dimensions and diagonal, positive semidefinite Dm , Duj and
Dxi as solutions to the LMIs:
Qi Xi1 Fi C 1 Hi C 1 ZiTei

Pi Z i
?
2Pi +FiT Zi 0
0 (17)
0,
? Qi
?
?
HiT+Hi Qi 0
?
?
?
li
i
T (Cq C 1+Dqu K)
T
Dx 0 (AC 1+Bu K)
T
? Di
0
Bw
w
0 (18)
1
T
? ? X Bp Si B T
B
G
p i
p
i
? ?
?
Si

m

j
TN T ej
D
12 C TT T em
Du 21 K

0,
0 (19)
?
eTm x dT Dm d
? eTj u dT Duj d
i
where li := 4(i eTidv TDw

vdTDxi d), and K := KC.
Proof. Applying a congruence transformation and taking a

Schur complement, the (nonlinear) invariance condition (10)
can be written as
Ri Ai C T ei ri1 eTi CATi 0, i Nn
i
v) and
where ri := 4(eTid dTDxi dv TDw
Si
0
CqK
0

0
S
0
0
i
Ri Ai :=
T
CqK
0 C T Dxi C
0
i
0
0
0
Dw
(20)
Gi BpT
Si BpT
ATK
T
Bw
Applying Theorem III.1 on (20) verifies that (10) is satisfied

if and only if, i Nn , there exist Xi = XiT such that
Si 0
CqK
0 Gi BpT
? Si

0
0 Si BpT
Xi C T ei
T
? ? C TDxi C 0
AK 0,
0. (21)
?
ri
i
T
? ?
?
Dw
Bw
? ?
?
?
Xi1
Similarly, using the congruence transformation diag(C T , I)

on the second inequality in (21) yields, i Nn :

T
C Xi C 1
ei
0
(23)
i
v)
?
4(eTi d dT Dxi d v T Dw
It follows that sufficient conditions (necessary and sufficient
in the case of unstructured uncertainty) for the invariance
constraint (6) can now be given by the conditions (22)-(23)
i Nn . Note that (22)-(23) (10).
Multiplying (23) by i 1 , for a given (see section IV-A)
and where i = eTi ei , followed by a congruence transformation with diag(I, I) yields, i Nn :
1 T

i C Xi C 1
i ei
0
i
?
4i (eTi ddT Dxi dv T Dw
v)
1
i
i
Using the redefinitions Xi1 := 1
i Xi , Dw := i Dw and
i
i
Dx := i Dx , recognizing that i ei = ei and applying the
congruence transformation diag(ZiT 1 , I) yields
T 1 T

Zi C Xi C 1 1 Zi ZiT ei
0
?
li
Now using slack variable identity (16) on the (1,1) entry gives
the following condition which is equivalent to (23):
1 1

C Zi + ZiT 1 C T Xi1 ZiT ei
0.
?
li
Applying Theorem
III.2 on (1,1) entry with matrix

Mo :=
, subsequently ignoring the positive term
Fi Hi
1 1
1 T
C Pi C
yields the LMIs in (17).
Similarly, multiplying (22) by 1
i , followed by a congruence transformation with diag(i I, i I, I, I), i Nn , and
1
using the redefinitions Si := 1
i Si , Gi := i Gi along
i
i
with those for Xi , Dw and Dx above yields the LMI (18).
Finally, for the input and state constraints, the LMIs in
(19) are obtained by applying the congruence transformation
diag(C T , I) on the corresponding LMIs in (9).
B. Cost function incorporation
We now introduce a cost function in order to compute the
largest/smallest volume constraint-admissible RCI set (herein
known as maximal/minimal volume RCI set approximations).
The volume of Z is proportional to | det(C 1 )| [12] and we
derive upper/lower bounds on the determinant as given below.
Theorem III.4. Consider matrix variables W = W T 0
T
and W = W 0 such that (without loss of generality):
W C 1 C T W .
(24)

Applying a Schur complement argument on the first in- Then
W C 1
1 T
C C
W
0
(25)
equality in (21), followed by the congruence transformation
?
I
diag(I, C T , I, I) and a subsequent rearrangement yields,
:= KC 1 ):
> 0 such that:
i Nn , the LMI (with K
Furthermore, W C 1 C T if there exists a
i
T
TBuT C TCqT + K
TDqu
Dx 0 C TAT + K
I
I
0
T
? Di
Bw
0
T
1
w
(26)
+C
W 2 0
? C
0 (22)
1
T
T
?
?
Xi Bp Si Bp
Bp Gi
?
?
I
?
?
?
Si
Proof. Note first that (25) follows from a Schur complement

argument. Consider next the other inequality in (24), namely:
1
i
i
i
i
redefinitions Xi1 := 1
i Xi , Dw := i Dw , and Dx := i Dx
yields (31). Similarly, in Theorem III.4, using the identity
C 1 C T W 0
1 C T W 1 W W 1 C 1
1 W
T W 1 C 1 = W
i
iT W
C
o
o
o
o
1 1
1
T
C
C
+C T W 1
+C
W
o
o
o
o
(27)
Applying a congruence C T , followed by a Schur complement

argument and a subsequent multiplication of the matrix by the
> 0 yields:
scalar

I
I
(28)
T W 1 C 1 0
? C
Using the slack variable identity (16) on the (2,2) entry of
1W and Mo = C 1 , neglecting a positive
(28), with M :=
semidefinite term, followed by a Schur complement argument
yields (26) as a sufficient condition for (27).
Remark III.2. Note that unlike the scheme in [9], we do
not require det(C 1 ) to be positive since (24) implies that
det(W ) det(C 1 )2 det(W ).
It follows that the computation of initial (inner) approximation of the maximal volume RCI set Z and corresponding gain
K can now be given by the convex optimization problem:
1
= max{ log(det(W 2 ) : (17 19), (26) are satisfied for

all variables defined in Theorems III.3 and III.4}.
(29)
Note that the function Sm = log(det(W )) is concave. Therefore, to compute an initial outer approximation of the minimal
volume RCI set and K, we minimize an upper-bound on Sm
by choosing trace(W ) as the cost (see e.g. arithmetic meangeometric mean inequality). The LMI problem then becomes
= min{trace(W ) : (17 19), (25) are satisfied for all
variables defined in Theorems III.3 and III.4}.
(30)
We now propose a theorem to update the initial solution to

the RCI set as well as controller K.
Theorem III.5. Let Co , W o , W o and Xio be solutions to
the optimization problem in (29) or (30). Then these solutions
(along with K) can be updated iteratively by solving (29) or
(30), with = 1 and (17) replaced by

L11
ei i
0
(31)
i
?
4(i eTi dv T Dw
vdT Dxi d)
where L11 = C TXio Co1 +CoTXio C 1CoTXio Xi1Xio Co1
and the (2,2) and (2,3) blocks of (26) respectively replaced by
1 1
1
T
,
C TW 1
o Co +Co W o C
2
CoT W 1
o W
(32)
Proof. In the proof of Theorem III.3, (17) are used to ensure

(23). Once the initial/previous solutions Co and Xio are available, we proceed as follows. Consider the following identity
based on a slack variable approach (see Remark III.3):
T
o 1 o 1
C T Xi C 1 = YiT Xi Yi 2
i Co Xi Xi Xi Co
T
T
o 1
+1
Xio Co1 +1
(33)
i C
i Co Xi C
1 o 1
where Yi := C 1 1
i Xi Xi Co . Replacing the (1,1) entry
in (23) by the last three terms on the righthand side of
(33), multiplying the resulting matrix by i , followed by the
1 W W 1 C 1 instead of (16) gives (26)

i = C 1
with W
o
o
with the (2,2), (2,3) blocks respectively replaced by (32).
The overall algorithm can now be summarized as follows.
Algorithm III.1: Computation of maximal/minimal volume
RCI set approximations
(1) Initial solution: Compute initial approximations C, K,
W , W and Xi i, to the maximal/minimal volume RCI
set by solving (29) or (30).
(2) Update solution: Set Co = C, W o = W , W o = W and
Xio = Xi , i, and compute C, K, W , W , Xi by solving
modified versions of (29)/(30) as given in Theorem III.5.
(3) Iterate: Loop back to step (2) until there is no further
improvement in the RCI set volume.
Remark III.3. The identity (33) ensures recursive feasibility
since setting Xi and C equal to Xio , and Co shows that
the solutions from the previous iteration are feasible for the
current one. Therefore, the volume of the RCI set defined by C
would be greater than or equal (less than or equal, for minimal
RCI set computation) to that of the previous set defined by Co .
Remark III.4. Set inclusion between solutions of successive
iterations of the algorithm can also be ensured in the proposed
formulation. Let Zk (defined by Ck ) denote the RCI set
computed at iteration k. Then, LMI conditions for Zk+1 Zk
(for minimal-) and Zk Zk+1 for maximal volume RCI sets,
can easily be derived using the S-procedure (see Theorem II.1).
However, we do not include it here due to space limitations.
Remark III.5. Remark II.2 gave a brief analysis of the
relaxation gap in Theorem II.1. A corresponding analysis for
Algorithm III.1 would require an investigation of the relaxation
gaps introduced in Theorems III.3 and III.4. Our numerical
experience, part of which is reported below, indicates that
they are sufficiently tight for practical systems. It may be
possible to use the results in [16] to investigate this issue
in detail, however, such an analysis falls outside the scope of
this technical note.
IV. N UMERICAL EXAMPLES
A. Example 1
We deal with the constrained, uncertain DC electric motor
system (with independent excitation) considered in [17], [9].
In particular, the linear continuous-time system is given by:

0.07
0.86(1 + q1 )
1
A=
, B=
0.06(1 + q1 )
q2
0
where the uncertainty in parameters q1 and q2 belong to the
sets: 0.2 q1 0.2 and 0.0085 q2 0.5. As in [9], the
system is discretized, using a sampling time of Ts = 0.1s and
then put into the form (2). The input and state
constraints
T are
respectively given by: 10 uk 10 and 10 10

T
xk 10 10 . In order to compute the RCI set, we solve
V. C ONCLUSION
Fig. 1. Maximal volume RCI set for Example 1
problem (29) with the proposed Algorithm III.1. Figure. 1

shows the simulation results. The computed initial RCI set
(with = 1), shown in purple,
and the controller are given by:

0.9359 0.0632
Co =
and Ko = 9.3586 0.6315 .
0.0013
0.2054
Following the iterative procedure specified in Algorithm
III.1, the final RCI set, shown in pink, and the
computed
0.1000 0.0000
controller are given by: C =
and K =
0.0032 0.1032

0.9898 0.0109 . For comparison, Figure. 1 also shows
the initial RCI set (in black/dark blue) as well as the final
RCI set (in green) computed using the iterative scheme in [9].
Note that our proposed algorithm is able to yield substantially
larger-volumes for both initial as well as the final (constraintadmissible) RCI sets. The figure also shows the state-trajectory
of the system (black curved line) converging around the
origin, despite persistent uncertainty, through the application
of computed control law K.
To highlight the effect of , Figure. 1 also shows, in yellow,
the initial RCI set computed using = 0.08. Note that even
with this initial condition, the algorithm still converges to the
same final RCI set above (pink) - though in fewer iterations.
B. Example 2
We now consider uncertain version of the double-integrator
system (see e.g. [7]) which is known to naturally have a hyperrectangle RCI set structure. The dynamics are as follows [10]:

1 1
1
1 0
0.2 0
A=
, Bu =
, Bw =
, Bp =
0 1
1
0 1
0 0.2
with Cq = A and Dqu = Bu . The disturbance set (4)
is: v T = [0.5 0.5]and . We also consider input
constraints uk U := u R : 3 u 3 . Using Remark II.1
and Theorem III.4, the minimal volume RCI set approximation
is computed (in one step) as C 1 = diag(0.5, 1.1) with
K = [1 1]. Similarly the maximal volume RCI set is
given by C 1 = diag(4.32, 1.87) with K = [0.26 1].
The corresponding sets computed using algorithm in [10]
are respectively given by C 1 = diag(0.5, 1.3) and C 1 =
diag(3.27, 2.03). Hence, our algorithm yields better volume
approximations to the minimal/maximal RCI sets.
We have proposed a novel algorithm - based on convex/LMI

optimizations - for the computation of low-complexity polytopic RCI sets, along with the corresponding controller for
constrained linear systems with norm-bounded uncertainties.
The main contribution of this technical note is that
the proposed formulation removes the inherent problemnonlinearities, including BMIs and triple product terms of the
form C TXi C, at the expense of only minor conservatism. To
this end, new results have been proposed in Theorems III.1 and
III.2 which, being general in nature, also have applications in
other problem areas [13], e.g. Lyapunov stability of systems.
Examples have shown that the algorithm can yield improved
volume RCI sets in comparison to the schemes in [9] and [10].
Finally, note that the invariance conditions in Theorem II.1
are also valid for general polyhedral sets, though a convex reformulation for non-square C forms part of our future work.
R EFERENCES
[1] F. Tahir and I.M. Jaimoukha, Robust feedback model predictive control
of constrained uncertain systems, Journal of Process Control, vol. 23,
pp. 189200, 2013.
[2] F. Tahir and I.M. Jaimoukha, Causal state-feedback parameterizations
in robust model predictive control, Automatica, vol. 49, no. 9, pp. 2675
2682, 2013.
[3] F. Blanchini, Set Invariance in Control, Automatica, vol. 35, no. 11,
pp. 17471767, 1999.
[4] F. Blanchini and S. Miani, Set-theoretic methods in control, Springer,
2008.
[5] M. Vassilaki, J.C. Hennet and G. Bitsoris, Feedback control of linear
discrete-time systems under state and control constraints, International
Journal of Control, vol. 47, no. 6, pp. 1727-1735, 1988.
[6] C.E.T. Dorea and J.C. Hennet, (A, B)-Invariant Polyhedral sets of linear
discrete-time systems, Journal of Optimization Theory and Applications, vol. 103, no. 3, pp. 521-542, 1999.
[7] S.V. Rakovic, E.C. Kerrigan, K.I. Kouramas and D.Q. Mayne, Invariant
approximations of the minimal robust positively invariant set, IEEE
Trans. Autom. Control, vol. 50, no. 3, pp. 406410, 2005.
[8] S.V. Rakovic, E.C. Kerrigan, D.Q. Mayne and K.I. Kouramas, Optimized robust control invariance for linear discrete-time systems: Theoretical foundations, Automatica, vol. 43, no. 5, pp. 831841, 2007.
[9] T.B. Blanco, M. Cannon and B. De Moor, On efficient computation of
low-complexity controlled invariant sets for uncertain linear systems,
International journal of Control, vol. 83, no. 7, pp. 1339-1346, 2010.
[10] F. Tahir and I.M. Jaimoukha, Robust Positively Invariant sets for linear
systems subject to model-uncertainty and disturbances, in Proc. 4th
IFAC Nonlinear Model Predictive Control Conf., 2012.
[11] P. dAlessandro and E. De Santis, Controlled invariance and feedback
laws, IEEE Trans. Autom. Control, vol. 46, no. 7, pp. 1141-1146, 2001.
[12] M. Cannon, V. Deshmukh and B. Kouvaritakis, Nonlinear model
predictive control with polytopic invariant sets, Automatica, vol. 39,
no. 8, pp. 14871494, 2003.
[13] P. Apkarian, H.D. Tuan and J. Bernussou, Continuous-time analysis,
eigenstructure assignment, and H2 synthesis with enhanced linear matrix
inequalities (LMI) characterizations, IEEE Trans. Autom. Control, vol.
46, no. 12, pp. 19411946, 2001.
[14] L. El Ghaoui, F. Oustry and H. Lebret, Robust solutions to uncertain
semidefinite programs, SIAM Journal on Optimization, vol. 9, no. 1,
pp. 3352, 1998.
[15] I. Polik and T. Terlaky, A Survey of the S-Lemma, SIAM Review, vol.
49, no. 3, pp. 371418, 2007.
[16] U. Malik, I.M. Jaimoukha, G.D. Halikias and S.K. Gungah, On the gap
between the quadratic integer programming problem and its semidefinite
relaxation, Mathematical Programming, vol. 107, no. 3, pp. 505-515,
2006.
[17] F. Blanchini, Constrained Control of Uncertain Linear Systems, Journal of Optimization Theory and Applications, vol. 71, no. 3, pp. 465483,
1991.

Low-Complexity Polytopic Invariant Sets For Linear Systems Subject To Norm-Bounded Uncertainty

Uploaded by

Copyright:

Available Formats

Low-Complexity Polytopic Invariant Sets For Linear Systems Subject To Norm-Bounded Uncertainty

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Low-Complexity Polytopic Invariant Sets For Linear Systems Subject To Norm-Bounded Uncertainty

Uploaded by

Copyright:

Available Formats

This article has been accepted for publication in a future issue of this journal, but has not been

Limited circulation. For review only