We denote the number in (13) by v and call it the value of the game. We say

that the game has a saddle point (x , y ), that x is an optimal mixed strategy

** *

for Blue, and that y is an optimal mixed strategy for Red if

*

P(x, y ) - P(x , y ) - P(x , y) (14)

**

* *

for all x in P and y in P .

K L

T 5.3. A matrix game has a value and a saddle point in mixed strategies.

This theorem is a corollary of Theorem 5.2. Take X : P , Y : P , and

K L

f : P. The function P is continuous on P ; P . The sets P and P are

K L K L

compact and convex. Since P is bilinear, it is concave in x and convex in y.

Theorem 5.3 follows by applying Theorem 5.2 to P.

Note that the saddle point condition (13) implies that

v : P(x , y ).

**

APPLICATION TO GAME THEORY 127

Exercise 5.1. Verify that in the submarine”convoy game the value in mixed

strategies is and that

x : (, , 0, 0, ), y : ( , , , )

* *

is a saddle point.

Exercise 5.2. Show that if a matrix game has a value in pure strategies, then

(10) and (11) hold. Conversely, show that if a matrix game has a saddle point

in pure strategies, then the game has a value v and (10) holds.

Exercise 5.3. Let X denote the set of optimal mixed strategies for Blue and

*

let Y denote the set of optimal mixed strategies for Red. Show that X and

* *

Y are compact convex sets.

*

Convexity and Optimization in n . Leonard D. Berkovitz

Copyright 2002 John Wiley & Sons, Inc.

ISBN: 0-471-35281-0

IV

OPTIMIZATION

PROBLEMS

1. INTRODUCTION

In Section 9 of Chapter I we stated the basic problem in optimization theory

as follows: Given a set S (not necessarily in RL) and a real-valued function f

de¬ned on S, does there exist an element s in S such that f (s ) - f (s) for all

* *

s in S, and if so ¬nd it. We also showed that the problem of maximizing f over

S is equivalent to the problem of minimizing 9 f over S. Thus, there is no loss

of generality in only considering minimization problems, as we shall do

henceforth.

If S is a set in RL and f is a real-valued function on S, we say that a point

s in S is a local minimizer or that f has a local minimum at s if there exists a

9 0 such that f (s ) - f (s) for all s in B(s , ) 5 S. If the strict inequality

f (s ) : f (s) holds, then s is said to be a strict local minimizer. If S is open,

then B(s , ) 5 S is an open set contained in S. Hence there exists a 9 0 such

that, for all s in B(s , ), f (s ) - f (s). Therefore, if S is open, for s to be a local

minimizer, we need to ¬nd a 9 0 such that f (s ) - f (s) for all s in B(s , )

and can omit the intersection with S. A point s that is a minimizer is also a

*

local minimizer. A point s that is a local minimizer need not be a minimizer.

In this chapter we shall develop necessary conditions and suf¬cient condi-

tions for a point s to be a minimizer or local minimizer for various classes of

*

problems. The determination of the set E of points that satisfy the necessary

conditions does not, of course, solve the optimization problem. All we learn is

that the set of solutions is to be found in this set. The determination of those

points in E that are solutions to the problem requires further analysis.

Suf¬cient conditions, if applicable to the problem at hand, are useful in this

connection.

If S is an open set in RL, the optimization problem is often called an

unconstrained problem.

A programming problem is a problem of the following type. A set X in RL

is given as are functions f and g with domain X and ranges in R and RK

128

DIFFERENTIABLE UNCONSTRAINED PROBLEMS 129

respectively. Let

X : +x : x + X , g(x) - 0,.

Problem P

Minimize f over the set X. That is, ¬nd an x in X such that f (x ) - f (x) for

*

*

all x in X.

The set X is called the feasible set, and elements of X are called feasible

points or feasible vectors.

The problem is sometimes stated as follows: Minimize f (x) subject to

x + X and g(x) - 0.

If X : RL, A is an m;n matrix, and

Ax 9 c

f (x) : 19b, x2, g(x) : (1)

,

9x

the problem is said to be a linear programming problem. We have written 9b

rather than b because in the linear programming literature the problem is

usually stated as follows: Maximize 1b, x2 subject to Ax - c and x . 0.

If X is convex and the functions f and g are convex, the problem is said

to be a convex programming problem.

2. DIFFERENTIABLE UNCONSTRAINED PROBLEMS

We will now denote the set on which the function f is de¬ned by X rather than

S. We ¬rst assume that X is an open interval in R and that f is differentiable

on X. We will derive necessary conditions and suf¬cient conditions for a point

x in X to be a local minimizer. Although the reader surely knows these

conditions from elementary calculus, it is instructive to review them.

Let x in X be a local minimizer of f and let f be differentiable at x . Then

there exists a 9 0 such that f (x) . f (x ) for x in (x 9 , x ; ). Therefore,

for x : x : x ;

f (x) 9 f (x )

. 0, (1)

x9x

and for x 9 : x : x

f (x) 9 f (x )

- 0. (2)

x9x

Since f is differentiable at x ,

f (x) 9 f (x ) f (x) 9 f (x )

: lim : f (x ).

lim

x9x x9x

VV VV

> >

130 OPTIMIZATION PROBLEMS

From this and from (1) we get f (x ) . 0, while from (2) we get f (x ) - 0.

Hence f (x ) : 0.

Let us now assume further that f is of class C on (x 9 , x ; ). By

Taylor™s theorem, for each x " x in (x 9 , x ; ) there exists a point x that

lies between x and x such that

f (x) : f (x ) ; f (x )(x 9 x ) ; f (x )(x 9 x ).

(3)

Since x is a local minimizer, f (x ) : 0 and therefore

f (x )(x 9 x ) : f (x) 9 f (x ) . 0.

Thus

f (x) 9 f (x )

. 0.

f (x ) : 2

(x 9 x )

If we now let x ; x , then x ; x and f (x ) ; f (x ). Hence f (x ) . 0.

We have proved the following theorem.

T 2.1. L et X be an open interval in R, let f be a real-valued function

de¬ned on R, and let x in X be a local minimizer for f. If f is differentiable at

x , then f (x ) : 0. If f is of class C on some interval about x , then

f (x ) . 0.

A point c in X such that f (c) : 0 is called a critical point of f . We have

shown that for a differentiable function a local minimizer is a critical point.

If we replace the necessary condition f (x ) . 0 by the stronger condition

f (x ) 9 0, we obtain a suf¬cient condition for a critical point to be a local

minimizer.

T 2.2. L et X be an interval in R and let f be real-valued and of class

C on some interval about a point x in X. If f (x ) : 0 and f (x ) 9 0, then

x is a strict local minimizer for f .

Proof. Since f is continuous on some interval about x and since

f (x ) 9 0, there exists a 9 0 such that f (x) 9 0 for all x in (x 9 , x ; )

(See Exercise I.5.4.) By Taylor™s Theorem, for each x " x in (x 9 , x ; )

there exists an x lying between x and x such that (3) holds. Since f (x ) : 0,

we get that for each x " x in (x 9 , x ; )

f (x) 9 f (x ) : f (x )(x 9 x ) 9 0.

(4)

Thus x is a strict local minimizer.

DIFFERENTIABLE UNCONSTRAINED PROBLEMS 131

In elementary calculus texts Theorem 2.2 is often called the second derivative

test.

We must have f (x ) 9 0 rather than f (x ) . 0 for the conclusion of

Theorem 2.2 to hold. To see this, take X : R and take f (x) : x. Then

f (0) : 0, f (0) : 0, but zero is not a local minimizer. If, however, we assume

that f (x) . 0 for all x in X, then all the statements in the proof of Theorem

2.2 hold for each x in X, except that (4) now reads

f (x) 9 f (x ) : f (x )(x 9 x ) . 0.

Thus x is a minimizer. If we assume that f (x) . 0 on some interval about

x , then x is a local minimizer. Also, if we assume that f (x) 9 0 on all of X,

then x is a strict minimizer.

We summarize this discussion in the following corollary to Theorem 2.2

C¬¬ 1. L et f (x ) : 0. If f (x) . 0 on X, then x is a minimizer. If

f (x) 9 0 on X, then x is a strict minimizer. If f (x) . 0 on some interval about

x , then x is a local minimizer.