@

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