Sets of transfer matrices
satis es 1
1
H
D
H
2
H
1 is stronger than 2
1
2
D
D
H
H
1 is weaker than 2
1
2
D
D
H
H
1
2
1
2
D
^
D
H
\
H
1 is infeasible
1 =
D
H
1 is feasible
1 =
D
H
6
1 is strictly stronger than 2
1
2, 1 = 2
D
D
H
H
H
6
H
Properties of design specications and the corresponding sets of
T
able
6.1
transfer matrices.
6.2
Affine and Convex Sets and Functionals
In this section we introduce several important de nitions.
We remind the reader that is a vector space: roughly speaking, we have a
H
way of adding two of its elements (i.e.,
transfer matrices) and multiplying
n
n
z
w
one by a real scalar. In a vector space, we have the important concepts of a line
and a line segment.
If
~
and
, we will refer to
+(1 ) ~ as an ane combination
H
H
2
H
2
R
H
;
H
of and ~. We may think of an a ne combination as lying on the line passing
H
H
through and ~, provided = ~. If 0
1, we will refer to the a ne
H
H
H
6
H
combination
+(1 ) ~ as a convex combination of and ~. We may think of
H
;
H
H
H
a convex combination as lying on the line segment between and ~. The number
H
H
measures the fraction of the line segment that we move from ~ towards to
H
H
yield
+ (1 ) ~. This can be seen in gure 6.1.
H
;
H
1
is a ne if for any , ~
1, and any
,
+
De
nition
6.1:
H
H
H
H
2
H
2
R
H
(1 ) ~
1.
;
H
2
H
Thus a set of transfer matrices is a ne if, whenever two distinct transfer matrices
are in the set, so is the entire line passing through them.
1
is convex if for any , ~
1, and any
0 1],
De
nition
6.2:
H
H
H
H
2
H
2
+ (1 ) ~
1.
H
;
H
2
H
Thus a set of transfer matrices is convex if, whenever two transfer matrices are
in the set, so is the entire line segment between them.
These notions are extended to functionals as follows:
A functional on
is a ne if for any
~
, and any
De
nition
6.3:
H
H
H
2
H
, ( + (1
) ~) = ( ) + (1 ) ( ~).
2
R
H
;
H
H
;
H
6.2 AFFINE AND CONVEX SETS AND FUNCTIONALS
129
= 0 4
;
:
@
o
= 0
@
R
@
o
@
R
6
= 0 7
~H
:
o
= 1
@
@
R
@
o
@
R
6
o
H
@
I
@
= 1 4:
The line passing through and ~ consists of all ane combi-
Figure
6.1
H
H
nations of and ~, i.e.,
+(1 ) ~,
. The line segment between
H
H
H
;
H
2
R
and ~ consists of all convex combinations of and ~, i.e., +(1 ) ~
H
H
H
H
H
;
H
for 0
1.
A functional is a ne if the graph of its values along any line in is a line in
H
2 an example is shown in gure 6.2.
R
A functional on is convex if for any
~
, and any
De
nition
6.4:
H
H
H
2
H
0 1], ( + (1 ) ~)
( ) + (1 ) ( ~).
2
H
;
H
H
;
H
A functional is convex if the graph of its values along any line segment in lies
H
below the line segment joining its values at the ends of the line segment. This is
shown in gure 6.3.
Under very mild conditions we can test convexity of a set or functional by just
checking the case = 1 2. Speci cally, a set 1 is convex if and only if whenever
=
H
1 and ~
1, the average ( + ~ ) 2 is also in 1. Similarly, a functional
H
2
H
H
2
H
H
H
=
H
is convex if and only if, for every and ~ we have
H
H
(( + ~) 2) ( ( ) + ( ~)) 2
H
H
=
H
H
=
:
Since ( + ~) 2 can be interpreted as the midpoint of the line segment between
H
H
=
H
and ~, this simple test is called the midpoint rule.
H
6.2.1
Some Important Properties
We collect here some useful facts about a ne and convex sets and functionals.
130