Solving Multivariable Max-Min Problems

Using Maple and the vec_calc Package

This worksheet gives examples of how to solve multivariable max-min problems using Maple and the vec_calc package.

There are two main classes of such problems:

* The Unconstrained Problem:

Find all critical points of a function and classify each as a local maximum, a local minimum or a saddle point.

* The Constrained Problem:

Find the absolute maximum and minimum values of a function inside or on the boundary of a region.

Examples of these are given in the collapsed sections below.

To start the vec_calc package, execute the following commands:

> libname:=libname,"C:/mylib/vector";

> with(vec_calc): vc_aliases:

Warning, the protected names norm and trace have been redefined and unprotected

Warning, the name changecoords has been redefined

Package:   vec_calc   Version 4.3

For all HELP, execute: ?vec_calc

To use aliases, execute:   vc_aliases;

The Unconstrained Problem:

Find all critical points of a function and classify each as a local maximum, a local minimum or a saddle point.

Exa mp le:

Classify the critical points of the function:

> f:=(x,y)->x*y*exp(-x^2/2-y^2/8);

>

Solution:

Compute the gradient of f, set it equal to zero and solve for the critical points:

> delf:=GRAD(f);

> eqs:=equate(delf(x,y),[0,0]);

> critpts:=solve(eqs,{x,y});

We see there are 5 critical points given by:

> p1:=subs(critpts[1],[x,y]);

> p2:=subs(critpts[2],[x,y]);

> p3:=subs(critpts[3],[x,y]);

> p4:=subs(critpts[4],[x,y]);

> p5:=subs(critpts[5],[x,y]);

Use the second derivative test to determine if each critical point is a maximum, a minimum or a saddle point. Note, the test may fail. First, compute the Hessian and the leading principal minor determinants:

> Hf:=HESS(f): matrix(Hf(x,y));

> leading_principal_minor_determinants(Hf(x,y)):

Leading Principal Minor Determinants:

At each critical point, evaluate the Hessian and the leading principal minor determinants and interpret the results:

> 'p1'=p1; H1:=Hf(op(p1)); LPMD(H1):

Leading Principal Minor Determinants:

Since D[2] is negative, the first critical point (0,0) is a saddle point.

> 'p2'=p2; H2:=Hf(op(p2)); LPMD(H2):

Leading Principal Minor Determinants:

Since D[2] is positive and D[1] is negative, the second critical point (1,2) is a local maximum.

> 'p3'=p3; H3:=Hf(op(p3)); LPMD(H3):

Leading Principal Minor Determinants:

Since D[2] is positive and D[1] is positive, the third critical point (1,-2) is a local minimum.

> 'p4'=p4; H4:=Hf(op(p4)); LPMD(H4):

Leading Principal Minor Determinants:

Since D[2] is positive and D[1] is positive, the fourth critical point (-1,2) is a local minimum.

> 'p5'=p5; H5:=Hf(op(p5)); LPMD(H5):

Leading Principal Minor Determinants:

Since D[2] is positive and D[1] is negative, the fifth critical point (-1,-2) is a local maximum.

To confirm the conclusions, use a contour plot: (Try rotating the plot.)

> contourplot3d(f(x,y), x=-2..2, y=-3..3, axes=boxed, thickness=2, numpoints=2000, shading=zhue);

> contourplot3d(f(x,y), x=-2..2, y=-3..3, axes=boxed, orientation=[-90,0],thickness=2, numpoints=2000, shading=zhue);

(1,2) and (-1,-2) are a local maxima. (1,-2) and (-1,2) are a local minima. And (0,0) is a saddle point.

>

The Constrained Problem:

Find the absolute maximum and minimum values of a function inside or on the boundary of a region.

Example:

Extremize the function:

> f:=(x,y)->x*y*exp(-x^2/2-y^2/8);

inside or on the ellipse g(x,y)=1 where

> g:=(x,y)->x^2/4 + y^2/16;

>

Solution:

The interior critical points were found in the unconstrained example. There are three methods of finding the critical points on the boundary.

Boundary Method I: Eliminate a Variable

Solve the constraint for one variable:

> y0:=solve(g(x,y)=1,y);

Notice that we named the solution y0 instead of y so that we can still use y as a variable. Also notice that there are 2 solutions for the upper and lower halves of the ellipse. We must handle these separately.

For the upper half of the boundary, substitute the solution into the function and differentiate:

> f1:=makefunction(x,f(x,y0[1]));

> Df1:=D(f1);

Find the x-coordinate at each critical point and substitute back to find the y-coordinate:

> x0:=solve(Df1(x)=0,x);

> y1:=subs(x=x0[1],y0[1]); b1:=[x0[1],y1];

> y2:=subs(x=x0[2],y0[1]); b2:=[x0[2],y2];

Repeat for the lower half of the boundary:

> f2:=makefunction(x,f(x,y0[2]));

> Df2:=D(f2);

> x0:=solve(Df2(x)=0,x);

> y3:=subs(x=x0[1],y0[2]); b3:=[x0[1],y3];

> y4:=subs(x=x0[2],y0[2]); b4:=[x0[2],y4];

Finally, we tabulate the values of the function at all interior and boundary critical points and identify the absolute maximum and minimum:

> p1; f(op(p1));

> p2; f(op(p2)); evalf(%);

> p3; f(op(p3)); evalf(%);

> p4; f(op(p4)); evalf(%);

> p5; f(op(p5)); evalf(%);

> b1; f(op(b1)); evalf(%);

> b2; f(op(b2)); evalf(%);

> b3; f(op(b3)); evalf(%);

> b4; f(op(b4)); evalf(%);

So we see that the absolute maxima occur at the interior points (1,2) and (-1,-2), and the absolute minima occur at the interior points (1,-2) and (-1,2).

>

Boundary Method II: Parametrize the Boundary

Define the parametrization:

> r:=makefunction(t,[2*cos(t),4*sin(t)]);

Restrict the function to the boundary:

> fr:=makefunction(t,simplify(f(op(r(t)))));

Find the critical points on the boundary:

> Dfr:=D(fr);

> bndcritpts:=solve(Dfr(t)=0,t);

> b1:=r(bndcritpts[1]);

> b2:=r(bndcritpts[2]);

Since the equation is non-polynomial, solve may not give all solutions. So we plot the function for one period:

> plot(Dfr,-Pi..Pi);

From the plot and its symmetries, it is obvious that solve missed two more solutions.

> b3:=r(3*Pi/4);

> b4:=r(-3*Pi/4);

Finally, we tabulate the values of the function at all interior and boundary critical points and identify the absolute maximum and minimum:
(This was done with the first method. So we won't redo it here.)

>

Boundary Method III: Lagrange Multiplier Method

Find the gradient of the function and the gradient of the constraint:

> delf:=GRAD(f);

> delg:=GRAD(g);

Set up the Lagrange multiplier equations and solve for the critical points on the boundary:

> eqs:=equate(delf(x,y),lambda*delg(x,y));

> sol:=solve({op(eqs),g(x,y)=1},{x,y,lambda});

Since the solutions involve a RootOf, we resolve them using allvalues:

> sol1:=allvalues(sol[1]);

> b1:=subs(sol1[1],[x,y]);

> b4:=subs(sol1[2],[x,y]);

> sol2:=allvalues(sol[2]);

> b3:=subs(sol2[1],[x,y]);

> b2:=subs(sol2[2],[x,y]);

Finally, we tabulate the values of the function at all interior and boundary critical points and identify the absolute maximum and minimum:
(This was done with the first method. So we won't redo it here.)

>

>