<<

. 28
( 59 .)



>>

K L L K


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.

<<

. 28
( 59 .)



>>