<<

. 15
( 59 .)



>>

every i : 1, 2, . . . , n, x 9 0.
G
L 5.1. L et A be an m ; n matrix and let

C : +w : w : Ax, w + RK, x + RL, x . 0,.

T hen C is a closed convex cone.
Proof. A straightforward calculation veri¬es that C is a convex cone.

To show that C is closed, we ¬rst consider the case in which the columns of
A are linearly independent. Let w be a limit point of C, and let +w , be a
 I
sequence of points in C converging to w . Then there exists a sequence of

points +x , in RL with x . 0 such that Ax ; w .
I I I 
We show that +x , is bounded. If +x , were unbounded, there would exist a
I I
subsequence, again denoted by +x ,, such that #x # ; -. All points in the
I I
sequence +x /#x #, have norm 1, so there exists a subsequence and a point x
I I *
of norm 1 such that x /#x # ; x . From
I I *
#x #A(x /#x #) ; w , #x # ; -,
I I I  I
we see that we must have A(x /#x #) ; 0. On the other hand, x /#x #; x
I I I I *
implies that A(x /#x #) ; Ax . Hence Ax : 0. Recall that #x # : 1, so that
I I * * *
x " 0. Therefore the relation Ax : 0 contradicts the linear independence of
* *
the columns of A.
Since +x , is bounded, +x , has a convergent subsequence, which we denote
I I
again by +x ,. Let x :lim x . Then x .0. Also, Ax ; Ax , so that Ax :w .
I  I  I   
Thus w + C, and C is closed.

If the columns of A are not linearly independent, we ¬rst show that any
point z in C can be expressed as a nonnegative linear combination of p : n
linearly independent columns of A. Let A , j : 1, . . . , n, denote the jth column
H
of A. Then there exists an x . 0 such that

L
z:  x A , x . 0.
HH H
H
Since the columns of A are linearly dependent, there exists a :( , . . . , ) "0
 L
such that

A ; A ; % ; A : 0.
  LL
+ R,
Therefore, for any

L
z :  (x 9 )A :  (x 9 )A ;  x A .
H H H H H H HH
H IH$ IH
SYSTEMS OF LINEAR INEQUALITIES: THEOREMS OF THE ALTERNATIVE 63


Since " 0, the ¬rst sum on the right exists. If : 0, then x 9 .0
H H H
whenever . x / . In particular, since x . 0, we have x 9 . 0 whenever
HH H H H
. 0. If 9 0, then x / . 0 and x 9 . 0 if and only if - x / . If
H HH H H HH
there exist indices j such that 9 0, set
H
x
H: 90 .
 : min
H
H
: 0 for all indices j for which " 0, set
If
H H
x
H: "0 .
 : max
H
H
Then x 9  . 0 for all j : 1, . . . , n and x 9  : 0 for at least one value of
H H H H
j. We have now expressed z as a nonnegative linear combination of q : n
columns of A. We continue the process until we express z as a nonnegative
linear combination of p : n linearly independent columns of A.
Let denote a choice of p : n linearly independent columns of A and let
A( ) denote the corresponding m ; p matrix. There are a ¬nite number of such
choices. Let

C( ) : +w : w : A( )y, w + RK, y + RN, y . 0,.

We have shown that each set C( ) is closed and that

C 3 8 C( ).
N
We now show the opposite inclusion. Let w + C( ) for some . By relabeling
columns of A, we can assume without loss of generality that selects the ¬rst
p columns of A. Then there exists a y + RN, y . 0 such that

N N L
w :  y A :  y A ;  (0)A , y . 0, j : 1, . . . , p.
HH HH H H
H H HN>
Let x : (y , . . . , y , 0, . . . , 0). Then w : Ax, and so w + C.
 N
We have expressed C as the union of a ¬nite number of closed sets. Hence
C is closed and Lemma 5.1 is proved.

T 5.1 (F«™ L). L et A be an m ; n matrix and let b be a vector
in RL. T hen one and only one of the systems

Ax - 0, 1b, x2 9 0, x + RL,
I:
II: ARy : b, y . 0, y + RK,

has a solution.
CONVEX SETS IN RL
64




Figure 2.7.



The conclusion of the theorem is sometimes stated in the logically equival-
ent form: Either I has a solution or II has a solution but never both. It can
also be stated in the following form: System I has a solution if and only if
system II has no solution.
Figure 2.7 illustrates Farkas™s lemma when A is a 2 ; 2 matrix with rows
a and a . Any vector x in the cross-hatched region satis¬es Ax - 0. Thus, if b
 
does not lie in the acute angle determined by a and a , then I has a solution.
 
(Draw the hyperplane 1b, x2 : 0 for such a b.) If we write II in the equivalent
form yRA : bR, yR . 0, we see that for II to have a solution b must lie in the
angle determined by a , a . The vector b is given, so its position is ¬xed. It

either lies in the angle or does not. Thus, precisely one of the systems I and II
has a solution.
We now prove the theorem. The reader will get an appreciation of the
ef¬ciency and esthetic appeal of convexity arguments by looking up the
original proof [Farkas, 1901].
We ¬rst suppose that II has a solution y . We shall show that I has no

solution. If Ax 9 0 for all x in RL, then I has no solution. Suppose there exists
an x in RL such that Ax - 0. Then
 

1b, x 2 : bRx : (ARy )R x : yR Ax : 1y , Ax 2.

    
SYSTEMS OF LINEAR INEQUALITIES: THEOREMS OF THE ALTERNATIVE 65


Since y . 0 and Ax - 0, it follows that 1b, x 2 - 0. Hence I has no solution.
  
We now suppose that II has no solution. Let

C : +z : z : ARy, y + RK, y . 0, z + RL,.

The statement that II has no solution is equivalent to the statement that b , C.
By Lemma 5.1, C is closed and convex. Therefore, by Theorem 3.1 there exists
?
a hyperplane Hx that strongly separates b and C. Thus x " 0 and



1x , b2 9 9 1x , z2
 
for all z in C. Since 0 + C, we get that 9 0. Thus

1x , b2 9 0. (1)

For all z in C we have

1x , z2 : 1x , ARy2 : yRAx : ,
  
the last inequality now holding for all y in RK satisfying y . 0.
We claim that the last inequality implies that

Ax - 0. (2)

If (2) were false, there would exist at least one component of Ax , say the jth

denote this component. Let y : e :
component, that is positive. Let
H H H
(0, . . . , 0, 1, 0, . . . , 0), where 9 0. Then 1y , Ax 2 : : . Since 9 0, if
H  H H
we take to be suf¬ciently large, we get a contradiction. Thus (2) is true. But
(1) and (2) say that x is a solution of I.

T 5.2 [G¤® 1873]. L et A be an m ; n matrix. T hen one and only
one of the following systems has a solution:

I: Ax : 0, x + RL,
II: ARy : 0, y + RK, y " 0, y . 0.

The reader should draw a ¬gure which illustrates this theorem when A is a
3 ; 2 matrix with rows a , a , a .

Proof. We shall show that the system I has a solution if and only if the
system

I: Ax - e, : 0,

has a solution, where e in the vector in RK all of whose entries equal 1. Let
CONVEX SETS IN RL
66


(x , ) be a solution of I. Then

Ax - e : 0,
 
so I has a solution. Now let x be a solution of I and let : Ax . If :
 
( , . . . , ), then : 0 for i : 1, . . . , m. Let : max+ , . . . , ,. Then (x , )
 K G   K 
is a solution of I.
The system I has a solution if and only if the system

x
I: (A, 9e) - 0, 1(0 ,91), (x, )2 9 0,
L

where 0 is the zero vector in RL, has a solution. By Farkas™s lemma, either I
L
(and hence I) has a solution or

AR 0
y: y . 0, y + RK,
II: ,
9eR 91

has a solution but never both. System II can be written as

II: ARy : 0, 1e, y2 : 1, y . 0.

From 1e, y2 : 1 it follows that y " 0. Hence if II has a solution, so does

II: ARy : 0, y . 0, y " 0.

If II has a solution, then 1e, y2 " 0. If we set y : y/1e, y2, then II will have a
solution. Hence either I has a solution or II has a solution but never both.

T 5.3 [M«©® 1936]. L et A, B, C be given matrices with n columns
and let A " O. T hen one and only one of the following systems has a solution:

I: Ax 9 0, Bx . 0, Cx : 0, x + RL,
II: ARy ; BRy ; CRy : 0, y . 0, y " 0, y . 0.
     
Proof. Let e : (1, 1, 1, . . . , 1) be a vector all of whose entries equal 1 and
whose dimension is the row dimension of A. We assert that the system I has a
solution if and only if the system I has a solution, where

I: Ax . e, Bx . 0, Cx : 0, 9 0.

Here is a real scalar. It is clear that if I has a solution, then I has a solution.
If I has a solution x , let : ( , . . . , )R : Ax . Let : min+ , . . . , ,. Then
  K   K
9 0 and Ax . e, and so I has a solution.

<<

. 15
( 59 .)



>>