340 CHAPTER 18. OPTIMIZATION

two lines x + y = 2 and x + y = −2. In fact there is no minimum. For example, takex = 100,y = −98. Then xy− x2 = x(y− x) = 100(−98−100) which is a large negativenumber much less than 0, the answer for the point (0,0).

There are no magic bullets here. It was still required to solve a system of nonlinearequations to get the answer. However, it does often help to do it this way.

A nice observation in the case that the function f , which you are trying to maximize,and the function g, which defines the constraint, are functions of two or three variables isthe following.

At points of interest,∇ f ×∇g = 0

This follows from the above because at these points,

∇ f = λ∇g

so the angle between the two vectors ∇ f and ∇g is either 0 or π . Therefore, the sine of thisangle equals 0. By the geometric description of the cross product, this implies the crossproduct equals 0. Here is an example.

Example 18.5.4 Minimize f (x,y) = xy− x2 on the set{(x,y) : x2 +2xy+ y2 = 4

}Using the observation about the cross product, and letting f (x,y,z) = f (x,y) with a

similar convention for g, ∇ f = (y−2x,x,0) ,∇g = (2x+2y,2x+2y,0) and so

(y−2x,x,0)× (2x+2y,2x+2y,0)= (0,0,(y−2x)(2x+2y)− x(2x+2y)) = 0

Thus there are two equations, x2+2xy+y2 = 4 and 4xy−2y2+6x2 = 0. Solving these twoyields the points of interest

(− 1

2 ,−32

),( 1

2 ,32

). Both give the same value for f a maximum.

The above generalizes to a general procedure which is described in the following majorTheorem. All correct proofs of this theorem will involve some appeal to the implicit func-tion theorem or to fundamental existence theorems from differential equations. A completeproof is very fascinating but it will not come cheap. Good advanced calculus books willusually give a correct proof. If you are interested, there is a complete proof later. First hereis a simple definition explaining one of the terms in the statement of this theorem.

Definition 18.5.5 Let A be an m× n matrix. A submatrix is any matrix which can beobtained from A by deleting some rows and some columns.

Theorem 18.5.6 Let U be an open subset of Rn and let f : U → R be a C1 function. Thenif x0 ∈U, has the property that

gi (x0) = 0, i = 1, · · · ,m, gi a C1 function, (18.2)

and x0 is either a local maximum or local minimum of f on the intersection of the levelsets just described, and if some m×m submatrix of

Dg (x0)≡

g1x1 (x0) g1x2 (x0) · · · g1xn (x0)

......

...gmx1 (x0) gmx2 (x0) · · · gmxn (x0)

