Prototyping with tools

Next: Matrix Calculus Up: Solving Constrained Optimization Problems Previous: Solving Constrained Optimization Problems   Index

Click for printer friendely version of this HowTo

## General Overview

It is often the case that you have some function, for example , and you want to find its extreme values (maximum and or minimum). If is a function of a single variable, , then all that's needed is to take its derivative and check where it equals zero. If we then went a little further and wanted the maximum and minimum values of when also falls on a specific line (or is otherwise constrained by some other function ), then all we would need to do is find out where (and if) the two lines intersected and check to see which values for give us the largest and smallest values from .

When functions of multiple variables are involved and we are still trying to find constrained maximums and minimums, we do a similar thing. In this case, instead of picturing lines intersecting, we can imagine surfaces intersecting (see Figure 3.11.1). Regardless of how we visualize the problem, there are two primary strategies for solving this sort of problem. The first one, algebraic substitution, works well when there are only two variables involved (otherwise you run into the problem of having more variables to solve for than you have equations). In this case you simply use the constraint equation to solve for one variable in terms of another, substitute this solution into the equation you wish to find the maximum/minimum of and then take the derivative to solve for the extreme points. The second method, Lagrange multipliers, (the one we'll be covering here), is a little more fancy, but works well when there are more than two variables involved.3.63.7

To find the extreme values of subject to the constraint :

1. Find all values of and such that

 (3.11.1)

and
2. Evaluate at all points, , that result from the previous step.

no_titleno_title

Example 3.11.1.2 (no_title)

In this example we will use equations with only two variables and demonstrate how both algebraic substitution and Lagrange multipliers result in identical solutions.

Let's find the extreme values of

 (3.11.2)

that are also on the circle

 (3.11.3)

(thus, in this case, ).

Using Algebraic Substitution: Using the constraint equation, , we'll solve for by moving to the other side. Thus, . We can then substitute for into (Equation 3.11.2), giving us

We can now take the derivative of Equation 3.11.4 and solve for the extreme points. That is,

Combining Equation 3.11.5 with Equation 3.11.3, we can determine that when , .

Now we must do the same thing only this time, we must use Equation 3.11.3 to solve for . That is, from Equation 3.11.3, . Substituting this into Equation 3.11.2, we then follow the same steps as before to determine that when , . We can then plug these points into Equation 3.11.2 to find that Thus are both maximums and are both minimums.

Using Lagrange Multipliers: To use the Lagrange multiplier method, we'll first set up the system of equations defined by :

 (3.11.6) (3.11.7)

From Equation 3.11.6 we can determine that either or . If , the constraint equation, (Equation 3.11.3), forces . If , then we can use Equation 3.11.7 to determine that and thus, from Equation 3.11.3, . The points of intersection are therefore and , the same solutions derived using algebraic substitution.

no_titleno_title

Example 3.11.1.4 (no_title)

We want to find the maximum value of

 (3.11.8)

subject to the constraint

 (3.11.9)

(thus, ). In this example, the equations involve more than two variables so algebraic substitution is not an option. Thus, it makes sense to use the Lagrange multiplier method here. We will first set up the system of equations defined by :

 (3.11.10) (3.11.11) (3.11.12)

If we multiply Equation 3.11.10 by , Equation 3.11.11 by and Equation 3.11.12 by , we have,

 (3.11.13) (3.11.14) (3.11.15)

We can now use these equations to solve for and in terms of . Using Equations 3.11.13 and 3.11.14 we get,

Using Equations 3.11.14 and 3.11.15 we get in terms of , that is,

We can now substitute for both and into Equation 3.11.9 to solve for :

Using Equations 3.11.16, 3.11.17 and 3.11.18, we can determine that the only place where both functions intersect is when , and . Thus is both the maximum and minimum from this function subject to the constraint, Equation 3.11.9.

Next: Matrix Calculus Up: Solving Constrained Optimization Problems Previous: Solving Constrained Optimization Problems   Index

Click for printer friendely version of this HowTo

Frank Starmer 2004-05-19
>