. 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