<<

. 30
( 59 .)



>>


@
1 , 2: (x) (x) dx.
?
Exercise 2.10. In this exercise we shall establish a series of results, some of
which are of interest in their own right, that lead to a proof of Lemma III.3.2.
(a) Let Q(x) : 1x, Ax2, where A is a symmetric matrix. Show that if Q is
positive de¬nite, then A is nonsingular. Hint: If A were singular, there would
exist an x " 0 such that Ax : 0.
 
(b) Show that if Q is positive semide¬nite and A is nonsingular, then Q is
positive de¬nite. Hint: If A is positive semide¬nite, then there exists an x " 0

that minimizes Q.
(c) If Q is positive de¬nite, then det A 9 0. Hint: Let I denote the identity
matrix and let 0 - - 1. For each 0 - - 1 consider the quadratic form
136 OPTIMIZATION PROBLEMS


P(x, ) : (1 9 )#x# ; Q(x) : 1x, [(1 9 )I ; A]x2.

Let d( ) : det[(1 9 )I ; A]. Show that d is a continuous function, that
d( ) " 0, and that d(0) : 1.
(d) Let the function f with domain RL be de¬ned by

f (x) : 1x, Ax2 ; 21b, x2 ; c,

where A is an n;n positive-de¬nite matrix and b is an n-vector. Show that
x : 9A\b in the unique minimizer of f and that

Ab
det
bR c
f (x ) : 1b, x 2 ; c :
  det A

Hint:

A A Ax ; b
b

: det .
det
c 1b, x 2 ; c
bR bR

Why?
(e) Let

g(x, y) : 1x, Ax2 ; 2y1b, x2 ; cy : (x, y)RB(x, y),

where

A b
B: .
c
bR

Show that the quadratic form g is positive de¬nite if and only if A is positive
de¬nite and det B 9 0. Hints:

(i) Since g(x, 0) : 1x, Ax2, if g is positive de¬nite, then A is positive
de¬nite.
(ii) For y " 0,

x
g(x, y) : yg ,1
y

(iii) If A is positive de¬nite, then

g(x, 1) : f (x) . f (x ).

(f ) Prove Lemma III.3.2. Hint: If A is positive de¬nite, use (e) and
induction. If A is negative de¬nite, then 9A is positive de¬nite.
OPTIMIZATION OF CONVEX FUNCTIONS 137


3. OPTIMIZATION OF CONVEX FUNCTIONS

The points at which a convex function attains a maximum or minimum have
important properties not shared by all functions.

T 3.1. L et f be a convex function de¬ned on a convex set C.

(i) If f attains a local minimum at x , then f attains a minimum at x .
 
(ii) T he set of points at which f attains a minimum is either empty or convex.
(iii) If f is strictly convex and f attains a minimum at x , then x is unique.
* *
(iv) If f is not a constant function and if f attains a maximum at some point
x in C, then x must be a boundary point of C.
Proof. (i) Since f attains a local minimum at x , there exists a 9 0 such

that for all z in B(x , ) 5 C

f (z) 9 f (x ) . 0. (1)

Let y be an arbitrary point in C. Then [x , y] belongs to C. Hence for

0 : t : /#y 9 x # the point z : x ; t(y 9 x ) belongs to B(x , ) 5 C.
   
Hence, from Lemma III.1.7 and (1) we get

f (z) 9 f (x )
 . 0.
f (y) 9 f (x ) .
 t

(ii) If f attains a minimum at a unique point, then there is nothing to prove.
Suppose that f attains a minimum at two distinct points x and x . Let
 
: f (x ) : f (x ) : min+ f (x) : x + C,. Then for any ( , ) in P with 9 0,
  
9 0,

- f ( x ; x ) - f (x ) ; f (x ) : ( ; ) : .
   
Hence f attains a minimum at each point of [x , x ].

(iii) Suppose that f attains a minimum at two distinct points x and x . Let
 
be as in (ii). Then for any ( , ) in P ,

- f ( x ; x ) : f (x ) ; f (x ) : .
   
Thus, we get a contradiction, : , and so x and x cannot be distinct.
 
(iv) Suppose f attains a maximum at x. If x were not a boundary point,
then x would be an interior point. Since f is not a constant function, there
exists a point y in C such that f (y) : f (x). Since C is convex, the line segment
[x, y] belongs to C. Since x is an interior point, there is a line segment [z, y]
such that x is an interior point of [z, y]. Then x : z ; y for some ( , ) in
138 OPTIMIZATION PROBLEMS


P with 9 0, 9 0, and

f (x) - f (z) ; f (y) : f (x) ; f (x) : f (x).

Thus we have the contradiction f (x) : f (x).

The next theorem and its corollary characterize points x at which a
*
function attains a minimum.

T 3.2. L et f be a real-valued function de¬ned on a set C. T hen f attains
a minimum at x in C if and only if 0 + * f (x ).
* *
Proof. If f attains a minimum at x , then for all x in C,
*
f (x) . f (x ) : f (x ) ; 10, x 9 x 2. (2)
* * *
Hence 0 + * f (x ). Conversely, if 0 + * f (x ), then (2) holds and f attains a
* *
minimum at x .
*
Note that the theorem does not require f or C to be convex. If, however, f
is not convex, it can fail to have a subgradient at all points of its domain. Such
a function therefore cannot attain a minimum. The logarithm function ln x, or
any other logarithm function, is an example. The next corollary does require f
and C to be convex.

C¬¬ 1. L et f be convex and differentiable on an open convex set C. T hen
f attains a minimum at x in C if and only if
f (x ) : 0.
* *
Proof. Let f attain a minimum at x . That
f (x ) : 0 follows from
* *
Theorem 2.3, whether or not f and C are convex. If f is convex and
differentiable on an open convex set C and
f (x ) : 0, then by Theorem
*
III.3.1

+0, : +
f (x ), : * f (x ).
* *
Thus, by the theorem, f attains a minimum at x .
*
Remark 3.1. In geometric terms, Theorem 3.2 states that for a convex function
f de¬ned on a convex set C, a point x in C furnishes a minimum if and only
*
if the epigraph of f has a horizontal supporting hyperplane at (x , f (x )). The
* *
corollary states that for a differentiable convex function de¬ned on an open
convex set C, a point x furnishes a minimum if and only if the tangent plane
*
to the graph of f at x is horizontal.
*
The corollary also points out the true content of Theorem 2.4. By Theorem
III.3.3, the positive de¬niteness or semide¬niteness of H(x) on X implies that
LINEAR PROGRAMMING PROBLEMS 139


f is convex. It is the convexity of f that is the important element in Theorem
2.4. The alert reader may have observed that much of the proof of Theorem
2.4 was a repetition of the proof of Theorem III.3.3.

Exercise 3.1. Show that f (x) : x ; x 9 3x 9 7x attains a minimum on R
   
at a unique point and ¬nd the minimum.

Exercise 3.2. Maximize f (x) : x ; x x ; x subject to
 

93x 9 2x ; 6 - 0, 9x ; x 9 3 - 0, x 9 2 - 0.
    
(a) Sketch the feasible set.
(b) Show that a solution exists.
(c) Find the solution.


4. LINEAR PROGRAMMING PROBLEMS

Linear programming is used extensively in resource allocation problems. To
illustrate, we formulate a simple job-scheduling problem.
An of¬ce furniture manufacturer makes n different types of desks. His pro¬t
per desk of type j is b . Thus, if each week he produces x desks of type j, then
H H
his pro¬t for the week is

b x ;%;b x .
 LL
The manufacturer™s objective is to maximize his pro¬t. The number of desks
that he can produce per week is not unlimited but is constrained by the
capacity of his plant. Suppose that the manufacture of a type 1 desk requires
a hours per week on machine 1, that the manufacture of a type 2 desk

requires a hours of time on machine 1, and the manufacture of a type j desk

requires a hours per week of time on machine 1. If x , j : 1, . . . , n, denotes
H H
the number of desks of type j manufactured per week, then the number of hours
that machine 1 is used per week is

a x ;a x ;%;a x .
    L L
Because of maintenance requirements, readjustments, and the number of shifts
employed, the total time that machine 1 is in operation cannot exceed some
¬xed preassigned number c . Thus we have a constraint

a x ;%;a x -c .
  L L 
Similarly, if the manufacture of one desk of type j requires a hours per week
GH
140 OPTIMIZATION PROBLEMS


on machine i and the total number of hours per week that machine i can
operate is c , then
G

a x ;%;a x -c , i : 2, 3, . . . , n.
G  GL L G

Also the number of disks of type j made is nonnegative, so x 9 0.
H
The problem for the desk manufacturer is to manufacture x desks of type
H
j so as to maximize

L
 bx
HH
H

subject to

<<

. 30
( 59 .)



>>