Introduction to Constrained Optimization

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

PRISM Peer Advising

This Thursday and next, from 4:00 - 5:00 PM in South 309, PRISM will be doing informal peer-to-peer advising on (math) course selection for next semester.

Absolute Extreme Values

Yesterday we started finding the absolute minimum and maximum of z = 2x² + 3y² - 4x - 6y + 5 over the triangle in the xy plane with vertices (0,0), (3,0), and (0,3) (including those vertices and the sides of the triangle).

We found a critical point at (1, 1), and possible extremes along two of the sides at (1, 0) and (0, 1). There’s one more side, and all three vertices, left to check.

To check the remaining side, we realized that it has the equation y = 3 - x, between x = 0 and x = 3. So we could substitute 3 - x for y in the definition of z and use single-variable derivatives to find possible locations for possible extremes along the last side.

Finally we had to evaluate z at all the points we had found, plus the vertices of the triangle (possible extremes that none of the things we did would necessarily find). The largest of the resulting numbers is the absolute maximum, and the smallest the absolute minimum.

Here’s the work we did…

Constrained Optimization

Problem: Find the minimum or maximum value of “objective” function f(x, y, …), subject to some “constraint” g(x, y, …) = 0.

For example, find the maximum profit a company can make from raw material quantities x, y, etc., subject to a limit on what the total cost of those materials can be.

Or find the maximum volume of a cylindrical drum subject to a constraint on how much material is available to make it.

You’ve probably seen this sort of problem in calculus 1; now we have some more powerful tools for dealing with them.

Let’s try developing one of those tools, “Lagrange multipliers.”

To start, consider a function f (which I’ll draw and analyze as a 2-variable function, though Lagrange multipliers generalize to more variables), and a curve in the xy plane along which the constraint holds i.e., along which g(x,y) = 0. To solve the constrained optimization problem, we want to find a minimum or maximum value along the line on the surface of f corresponding to this curve:

To make the constraint curve easier to work with, parameterize it. Let t₀ be the value of the parameter at which f reaches the extreme value while also satisfying the constraint:

Now, since f( x(t₀), y(t₀) ) is an extreme value, we know that the derivative of f with respect to t must be 0 there. We can find that derivative using the chain rule, and it turns out to be the dot product of the gradient of f with the tangent to g. Since this dot product is 0, it means the gradient of f must be perpendicular to the curve of g:

Finally, the curve g(x,y) = 0 is a level curve for the constraint function g. And we know that gradients are perpendicular to level curves, so the gradient of g must also be perpendicular to the curve of g, and thus parallel to the gradient of f. Since parallel vectors are scalar multiples of each other, we can state that the two gradients are parallel in the form of an equation that says one of them is a constant (λ, the Greek letter lambda) times the other:

As an example of what this looks like in real life, let’s consider finding the minimum and maximum values of z from our absolute extremes example along the ellipse x² + 2y² = 9:

We’ve now written out the gradient and constraint equations, and would next solve them for x and y. We’ll see how to do that tomorrow, along with more discussion of Lagrange multipliers and examples of them.

Next

More about Lagrange multipliers.

Please read “Lagrange Multipliers” in section 3.8 of the textbook.

Next Lecture