<<

. 25
( 59 .)



>>

We shall prove this lemma in Exercise IV.2.10.
. 0 for all k : 1, 2, . . . , n and not all the : 0, then
If we assume that
I I
there is difference between n . 3 and n : 2.
For n . 3, if . 0, k : 1, . . . , n, and not all : 0, then A need not be
I I
positive semide¬nite. To see this, consider the matrix

10% 0
00% 0
A: .
$$\ $
0 0 % 91

Then 1x, Ax2 : x 9 x, which is not nonnegative for all x.
 L
112 CONVEX FUNCTIONS


For n : 2, however, if . 0, . 0, and not both and are zero,
   
then the symmetric matrix A is positive semide¬nite. To see this, let

a a

A: .
aa

: 0, then : 9a. Then to have . 0, we must have a : 0. But then
If
  
: 0. Hence we must have a 9 0. Thus 9 0. Since . 0,
   
a a . a. (10)
 
Since a 9 0, it follows that a . 0. For x : (x , x )
  
1x, Ax2 : a x ; 2ax x ; a x.
   

If x : (x , 0) with x " 0, we get
 
1x, Ax2 : a x 9 0.
 
If x : (x , x ) with x " 0, we have x : tx for some 9- : t : - and
   
1x, Ax2 : [a t ; 2at ; a ]x.
 

Denote the term in square brackets by q(t). From (10) we get that the dis-
criminant of q, which equals 4a 9 4a a , is nonpositive. Thus the quadratic
 
q either has a double root or has no real roots. Since a 9 0, it follows that

q(t) . 0 for all t. Hence, 1x, Ax2 . 0 for all x.

Exercise 3.1. Determine whether or not the following functions are convex on
R:

(i) f (x, y, z) : x ; 2xy ; 4xz ; 3y ; yz ; 7z,
(ii) f (x, y, z) : x ; 4xy ; 4y ; 2xz ; 4yz.

Exercise 3.2. Determine the convex set in R on which the function

f (x, y) : x 9 2xy ; y 9 3y

is (i) convex and (ii) strictly convex.

Exercise 3.3. For what values of r is the function f (x) : xP 9 r ln x convex on
(0, -).

Exercise 3.4. Show that f (x) : xP ; % ; xPL, r . 1, is convex on +x : x . 0,.
 LG
ALTERNATIVE THEOREMS FOR CONVEX FUNCTIONS 113


Exercise 3.5. Show that the n-dimensional ellipsoid

L x
G -1
x: 
a
G G
is convex. Hint: There is a very easy solution.

Exercise 3.6. For what values of p is f (x) : #x#N convex on RL. Hint: Use
Lemma 1.4.

Exercise 3.7. Show that if c 9 0, i : 1, . . . , 4, the function
G
f (x) : exp(c x ; c x\ ; c x ; c x\)
   
is convex on S : +(x , x ) : x 9 0, x 9 0,.
  
Exercise 3.8. Show that the function f (x) : (1 ; #x#)N, p . 1, is convex on
RL.

Exercise 3.9. Show that the function f (x) : 9(x ; x ; % ; x )L, n . 1, is
  L
convex on S : +x : x . 0,.

Exercise 3.10. A function f that is positive on a convex set C in RL is said to
be logarithmically convex if the function g(x) : ln f (x) is convex on C:

(i) Show that if f is logarithmically convex, then f is convex.
(ii) Is it true that every positive convex function is logarithmically convex?

Exercise 3.11. Let f be differentiable on an open convex set X. Show that if f
is strictly convex, then
f (x) "
f (y) for all distinct pairs of points x, y in X.

Exercise 3.12. Let C be an open convex set and let f be real valued and
differentiable on C. Prove that f is convex on C if and only if for each pair of
points x and x in C
 
1
f (x ) 9
f (x ), x 9 x 2 . 0.
  
Show that f is strictly convex if and only if strict inequality holds.


4. ALTERNATIVE THEOREMS FOR CONVEX FUNCTIONS

The theorems of this section are alternative theorems for systems of inequalities
involving convex and af¬ne functions. They ¬nd application in optimization
problems involving such functions.
114 CONVEX FUNCTIONS


De¬nition 4.1. A vector-valued function f : ( f , . . . , f ) with domain a convex
 K
set C in RL and range in RK is said to be convex if each of the real-valued
component functions f , i : 1, . . . , m, is convex.
G
Af¬ne functions or af¬ne transformations were de¬ned in De¬nition II.6.6.
It was shown there that an af¬ne function h with domain RL and range RK has
the form

h(x) : Ax ; b,

where A is an m ; n matrix and b is a vector in RK.
Note that h : (h , . . . , h ), where h : 1a , x2 ; b , and a is the ith row of A.
 K G G G G
T 4.1. L et C be a convex set in RL and let f : ( f , . . . , f ) be de¬ned and
 K
convex on C. L et h : (h , . . . , h ) be an af¬ne mapping from RL to RI. If
 I
f(x) : 0, h(x) : 0 (1)

has no solution x in C, then there exist a vector p in RK and a vector q in RI such
that p . 0, (p, q) " 0, and

1p, f(x)2 ; 1q, h(x)2 . 0 (2)

for all x in C.
Proof. For each x in C de¬ne the set

S(x) : +(y, z) : y + RK, z + RI, y 9 f(x), z : h(x),.

For each x in C, the set S(x) is the set of solutions (y, z) in RK>I of the system

y 9 f(x), z : h(x). (3)

Thus for each x, the origin in RK>I is not in S(x). Let

S : 8 S(x).
x+C

Since the origin in RK>I belongs to none of the sets S(x), it does not belong to
S. It is readily veri¬ed that S is convex. Hence by Theorem II.3.2 there is a
hyperplane that separates S and 0 in RK>I. That is, there exist vectors p in RK
and q in RI such that (p, q) " 0 and

1p, y2 ; 1q, z2 . 0 (4)

for all (y, z) in S.
ALTERNATIVE THEOREMS FOR CONVEX FUNCTIONS 115


If (y, z) belongs to S, then y 9 f(x) for some x in C. Hence if some
component of p, say p , were negative, we could take y to be arbitrarily large
G G
and obtain a contradiction to (4). Hence p . 0.
Now let 9 0 and let e denote the vector in RK all of whose components
are equal to 1. Then for x + C the vector (f(x) ; e, h(x)) belongs to S, and so

1p, f(x)2 ; 1q, h(x)2 . 9 (1p, e2).

We obtain (2) by letting ; 0.

Remark 4.1. From the proof it is clear that if the af¬ne function h is absent,
then the conclusion is that there exists a p " 0, p . 0 such that 1p, f(x)2 . 0
for all x in C.

Remark 4.2. This theorem is not a true alternative theorem, as it does not
assert that either the inequality (1) has a solution or the inequality (2) has a
solution, but never both. If we strengthen the hypotheses of the theorem by
assuming C : RL and the rows of A to be linearly independent, then we do get
a true alternative theorem. This is taken up in Exercise 4.2.

The next two theorems are corollaries of Theorem 4.1.

T 4.2. L et f be a vector-valued convex function de¬ned on a convex set
C in RL and with range in RK. T hen either

I: f(x) : 0

has a solution x in C or there exists a p in RK, p " 0, p . 0, such that

II: 1p, f(x)2 . 0

for all x in C, but never both.
Proof. Suppose I has a solution x . Then for all p " 0, p . 0, we have

1p, f(x )2 : 0, so II cannot hold.

Suppose now that I has no solution. Then by Theorem 4.1 and Remark 4.1
following the theorem, there exists a p " 0, p . 0 such that II holds for all x.
Theorem 4.2 is a true generalization of Gordan™s theorem, Theorem II.5.2.
To see that this is so, let C : RL and let f(x) : Ax. Then Ax : 0 has no
solution x if and only if there exists a vector p in RK, p " 0, p . 0, such that

1p, Ax2 . 0 for all x. If we take x : ARp, we get 1ARp, ARp2 . 0. If we take
x : 9ARp, we get 1ARp, ARp2 - 0. Hence ARp : 0. In other words we have
shown that Ax : 0 has no solution if and only if there exists a p " 0, p . 0
such that ARp : 0, which is Gordan™s theorem.
116 CONVEX FUNCTIONS


T 4.3. L et C be a compact convex set in RL and let + f , be a possibly
? ?Z
in¬nite family of real-valued convex functions that are continuous on C. If the
system
f (x) - 0, + A, (5)
?
has no solution in C, then there exists a ¬nite subfamily f , . . . , f and a vector
? ?K
p : (p , . . . , p ) such that p " 0, p . 0 and such that the real-valued function F
 K
de¬ned by

K
F(x) :  p f (x) (6)
G ?G
G
satis¬es
min F(x) 9 0. (7)
x+C


The proof will be carried out by translating the statement of the nonexist-
ence of solutions to the system (5) to a statement about the empty intersection
of a collection of closed subsets of a compact set. The ¬nite-intersection
property will then be used to obtain a statement about the empty intersection
of a ¬nite collection of sets. The last statement will then be translated to a
statement about the nonexistence of a solution to the system (1). An applica-
tion of Theorem 4.1 will then yield (7).
Proof. Since for each + A the function f is continuous, it follows that for
?
each + A and 9 0 the set

C : +x : x + C, f (x) - ,
? C ?
is closed and is contained in C. If the intersection of the closed sets +C ,,
? C
where + A and 9 0, were not empty, there would exist an x in C such that


<<

. 25
( 59 .)



>>