Several Variable Max-Min

by
K. D.  Stroyan
University of Iowa

copyright 1997 by Academic Press, Inc. - All rights reserved.

Special Mathematica Functions used in this NoteBook

Needs["Graphics`Colors`"];
Needs["Graphics`FilledPlot`"];
Off[General::"spell1];

Notebook Overview

Mathematica can solve some systems of equations and make the task of maximization or minimization simpler.  Remember that you should always check Mathematica's solutions to see if they make sense, because "extraneous" solutions are possible with nonlinear algebra.

For basics on MAX-min, see the text Chapters 11 and 19 and the Chapter 19 NoteBook MxMnThy.

References to the Text

This NoteBook goes with Chapter 19 of the text.

Example 19.5

Once you have derived the necessary conditions for a max or min, Mathematica's Solve[.] command may be able to solve the equations.  (If the equations are non-algebraic, you may have to approximate them with FindRoot[.].)

The first example below is solved in Chapter 19.  We wish to find a rectangular box of maximum volume subject to the condition that the length plus the girth is less than 108 inches.

Clear[l, w, h, V]; l = 108 - 2 (w + h); V = l w hdVdw = D[V, w]dVdh = D[V, h]

Now we solve for the critical values:

Solve[{dVdw == 0, dVdh == 0}]

The approximate maximum can be found by minimizing -V using the gradient method:  (This approach is only a "local" method, but will work when the critical equations are transcendental.)

FindMinimum[-V, {w, 10}, {h, 5}]

Example 19.7

Example 19.7 MAX-min in a quarter circle:

This problem asks us to find the max and min:

Extremize[ V = w*h*(108-2 w-2 h) : 0 ≤ w, 0 ≤ h, (w^2) + (h^2) ≤ (25^2)]

This region looks like:

region = 
      FilledPlot[{0, (Sqrt[(25^2) - (w^2)])}, {w, 0, 25}, 
        AspectRatio -> Automatic, AxesLabel -> {"w", "h"}, 
        Fills -> {Red}, 
        PlotStyle -> {{Thickness[0.02], Blue}, {Thickness[0.02], Blue}}, 
        DisplayFunction -> Identity]; 
    region = Show[region, 
        Graphics[{Thickness[0.02], Blue, Line[{{0, 0}, {0, 25}}]}], 
        DisplayFunction -> $DisplayFunction];

The critical values of V lie on the boundary or outside the constraints:

\(Clear[V, h, w]; 
V\  = \ w*h*\((108 - 2\ w - 2\ h)\); 

    gradV\  = \ {D[V, w], D[V, h]}; 
Solve[gradV\  == \ {0, 0}]\)

Show[region, 
      Graphics[{PointSize[0.03], 
          Orange, {Point[{0, 0}], Point[{0, 54}], Point[{54, 0}], 
            Point[{18, 18}]}}]]; Print[(18^2) + (18^2), " > 625"];

The straight forward use of FindMinimum goes to these places:

FindMinimum[V, {w, 10}, {h, 10}]FindMinimum[-V, {w, 10}, {h, 10}]

We know that  V = 0  on the boundary components where either  w = 0  or  h = 0.  We also know that  there are no interior critical values and that the

MAX-min on  the Implicit Boundary  (w^2) + (h^2) = (25^2)

Now our boundary optimization question is:

Extremize[ V = w*h*(108-2 w-2 h) : 0 ≤ w, 0 ≤ h, (w^2) + (h^2) = (25^2)]

The total derivative of V is:

\(Clear[dw, dh]; 
dV\  = \ gradV . {dw, dh}\)

and the differential of the constraint is  2 w dw + 2 h dh = 0.  We solve this for dh:

dh  =  -(w/h) dw

and substitute it into the differential dV:

\(dh\  = \ \(-\(w\/h\)\) dw; 
dV\  = \ Collect[dV, dw]\)

eqns = {Expand[(dV/dw)] == 0, (w^2) + (h^2) == (25^2)}

The Critical Equations

The next equations below come from the quarter circle maximization Example 19.7 which we derived in the previous section. (Below we multiply both sides of the first equation by  h to remove it from the denominatior.)   Press <Enter> to solve them.  (The calculation may take some time if your machine doesn't have very much memory.)

\(Clear[eqns]; 

    eqns = {108\ h\^2 - 4\ w\ h\^2 - 2\ h\^3 - 108\ w\^2 + 2\ w\^3 + 
            4\ w\^2\ h == 0, w\^2 + h\^2 == 625}; 

    critpoints = Solve[eqns, {w, h}]\)

The solutions look very complicated.  Remember that you can get numerical results with the N command.

N[ critpoints ]

The only point that lies in the region is the first one, (w, h) = (17.6777, 17.6777).

Another approach to this problem is taken up in Exercise 19.4.2 below.

Example 19.9

If the optimization problem is unconstrained, Mathematica can be used to calculate the partial derivatives and to solve the system of equations resulting from setting these partials equal to zero.

The first distance Example in Chapter 19 of the text involves finding the point on the surface z = (x^2) + 2 (y^2) that is closest to the point (3, 2, 1).  The function to minimize is the distance function below.

Mathematica calculates the partials symbolically.

\(dis := 
      \@\(\((x - 3)\)\^2 + \((y - 2)\)\^2 + \((x\^2 + 2\ y\^2 - 1)\)\^2\); 

    equations\  = \ {D[dis, \ x]\  == \ 0, \ D[dis, \ y]\  == \ 0}\)

Even though Mathematica can solve these equations, this is a complicated formulation of the problem.  We know that the square function is increasing, so it is sufficient to minimize the square of the distance.  Since this results in simpler systems of equations, it is an important reduction of the problem.  Compare the two sets of equations.

\(d2 := \((x - 3)\)\^2 + \((y - 2)\)\^2 + \((x\^2 + 2\ y\^2 - 1)\)\^2; 

    dDdx\  = \ D[d2, \ x]; 
dDdy\  = \ D[d2, \ y]; 

    eqns = {dDdx == 0, dDdy == 0}\)

Now to find the critical points, we can solve the above equations for x and y.

critpoints = Solve[eqns, {x, y}]

The result above involving ToRules and Roots indicates that Mathematica can't solve the equation explicitly.  We can still get approximate solutions with the N command.

N[critpoints]

The only solution that makes sense is the solution, (x, y) = (1.15728, 0.477944).  You should always examine these results to see if they make sense.  Let's compute the value and check to be sure the gradient is zero:

x = 1.15728; \(y = 0.477944; 
\@d2\)Print[dDdx, " dx  + ", dDdy, " dy"]

We can also try the gradient method:

\(Clear[x, y]; 
FindMinimum[\@d2, {x, 1}, {y, 1}]\)

Example 19.10

Parameters for the Text Example

Maximize and minimize the distance to an ellipsoid using Mathematica.  This example is in the text in Chapter 19.  Maximize and minimize the distance from

P = (p1,p2,p3)  to  a (x^2) + b (y^2) + c (z^2) == 20

a = 3; b = 2; c = 1; p1 = 3; p2 = 2; p3 = 1;

The total differential of D:

Clear[x, y, z, dx, dy, dz]; \(d2 := \((x - p1)\)\^2 + \((y - p2)\)\^2 + \((z - p3)\)\^2; 

    dDdx\  = \ D[d2, \ x]; 
dDdy\  = \ D[d2, \ y]; 
dDdz\  = \ D[d2, \ z]; 
    
Print["dD =", dDdx, "dx + ", dDdy, "dy + ", dDdz, "dz"]
      \)

The differential of the constraint:

\(w = a\ x\^2 + b\ y\^2 + c\ z\^2; 
dwdx\  = \ D[w, \ x]; 

    dwdy\  = \ D[w, \ y]; 
dwdz\  = \ D[w, \ z]; 

    Print[dwdx, " dx + ", dwdy, " dy + ", dwdz, " dz = 0"]\)

Solve Constraint Differential for dz:

dz = -((dwdx*dx)/dwdz) - ((dwdy*dy)/dwdz)

Substitute expression for dz into dD:

dD = dDdx dx + dDdy dy + dDdz dz

Together[dD]

pDpx = Coefficient[Simplify[Numerator[Together[dD]]], dx]

pDpy = Coefficient[Simplify[Numerator[Together[dD]]], dy]

Solve for Critical Point Conditions:

criticalpts = NSolve[{pDpx == 0, pDpy == 0, w == 20}, {x, y, z}]

Only the real solutions

(-1.06259,-1.29127,-3.64389)  &  (2.17044,1.59387,0.886994)

make sense in our problem.  Let's check that they are the right thing.

Checks:

x = -1.06259; y = -1.29127; z = -3.64389; Print[pDpx, "   ", pDpy, "   ", w, "  Distance = ", (Sqrt[d2])]

x = 2.17044; y = 1.59387; z = 0.886994; Print[pDpx, "   ", pDpy, "   ", w, "  Distance = ", (Sqrt[d2])]

Summary:
	MAX = 6.99  at  (-1.06259,-1.29127,-3.64389) 
	min =0.931   at   (2.17044,1.59387,0.886994)

Parameters for another Example

We wish to find the points on the ellipsoid

a (x^2) + b (y^2) + c (z^2) == 88

farthest from and closest to

P = (p1,p2,p3)

Are we inside or outside the ellipsoid?

a = 3; b = 2; c = 1; p1 = 3; p2 = 2; p3 = 1;

The total differential of D:

Clear[x, y, z, dx, dy, dz]; \(d2 := \((x - p1)\)\^2 + \((y - p2)\)\^2 + \((z - p3)\)\^2; 

    dDdx\  = \ D[d2, \ x]; 
dDdy\  = \ D[d2, \ y]; 
dDdz\  = \ D[d2, \ z]; 
    
Print["dD =", dDdx, "dx + ", dDdy, "dy + ", dDdz, "dz"]
      \)

The differential of the constraint:

\(w = a\ x\^2 + b\ y\^2 + c\ z\^2; 
dwdx\  = \ D[w, \ x]; 

    dwdy\  = \ D[w, \ y]; 
dwdz\  = \ D[w, \ z]; 

    Print[dwdx, "dx + ", dwdy, "dy + ", dwdz, "dz = 0"]\)

Solve Constraint Differential for dz:

dz = -((dwdx* dx)/dwdz) - ((dwdy*dy)/dwdz)

Substitute expression for dz into dD:

dD = dDdx dx + dDdy dy + dDdz dz

Together[dD]

pDpx = Coefficient[Simplify[Numerator[Together[dD]]], dx]

pDpy = Coefficient[Simplify[Numerator[Together[dD]]], dy]

Solve for Critical Point Conditions:

criticalpts = N[Solve[{pDpx == 0, pDpy == 0, w == 88}, {x, y, z}]]

Only the real solutions (4.90307,2.69818,1.14861), (-1.28193,-1.63024,-8.81786), (-2.78667, -5.20333, 3.2487), and (-1.84784, -2.67019, 7.96848) make sense in our problem.  Let's check that they are the right thing.

Checks:

x = 4.90307; y = 2.69818; z = 1.14861; Print[pDpx, "   ", pDpy, "   ", w, "  Distance = ", (Sqrt[d2])]

x = -1.28193; y = -1.63024; z = -8.81786; Print[pDpx, "   ", pDpy, "   ", w, "  Distance = ", (Sqrt[d2])]

x = -1.84784; y = -2.67019; z = 7.96848; Print[pDpx, "   ", pDpy, "   ", w, "  Distance = ", (Sqrt[d2])]

x = -2.78667; y = -5.20333; z = 3.2487; Print[pDpx, "   ", pDpy, "   ", w, "  Distance = ", (Sqrt[d2])]

Why NOT ask why?

The graph of distance near this critical value looks like a saddle.  Geometrically, this time you are inside the ellipsoid at the point P.  Can you give a geometric explanation of the saddle-like points?

Clear[x, y, z]; d2 := (((x - p1))^2) + (((y - p2))^2) + (((z - p3))^2); z := ((Sqrt[88 - (a (x^2) + b (y^2))])/c); graph = 
      Plot3D[d2, {x, -2, -4}, {y, -4, -6}, 
        AxesLabel -> {"x", "y", "z"}, 
        BoxRatios -> {1, 1, 2}, 
        ViewPoint -> {-3.233, 0.803, 0.595}];

Summary:
Max = 11.3     at (-1.28,-1.63,-8.82) 
	min = 2.03    at (4.90,2.70,1.15)

Using Mathematica for the Constrained Max-Min Problem, but trying to avoid learning about implicit differentiation...

Parameters

Find the roots in the Ellipsoid Example from the text using Mathematica.  We wish to find the point on the ellipsoid

a (x^2) + b (y^2) + c (z^2) == 88
closest to

P = (p1,p2,p3)

This time we "solve" the constraint  x^2 + 2y^2 + z^2 = 88 for z,

"z = Sqrt[(88 - a x^2 - b y^2)/c]"

a = 3; b = 2; c = 1; p1 = 3; p2 = 2; p3 = 1;

Solution with Explicit Positive Square Root

The total differential dD:

Clear[x, y, z, dx, dy]; d2 := (((x - p1))^2) + (((y - p2))^2) + (((z - p3))^2); \(z := \@\(\(88 - a\ x\^2 - b\ y\^2\)\/c\); 
pDpx\  = \ D[d2, \ x]; 

    pDpy\  = \ D[d2, \ y]; 
dD = pDpx\ dx + pDpy\ dy\)

The Critical Solutions?

N[Solve[{pDpx == 0, pDpy == 0}]]

All the real solutions  (-2.78667,-5.20333), (-1.84784,-2.67019), (-1.28193,-1.63024) and (4.90307,2.69818) make sense in our problem now.  Let's check that they are the right thing.

Checks:

x = -2.78667; y = -5.20333; Print[pDpx, "   ", pDpy, "  Distance = ", (Sqrt[d2])]

Print["z = ", z, "   a x^2 + b y^2 + c z^2 = ", 
      a (x^2) + b (y^2) + c (z^2)]

x = -1.84784; y = -2.67019; Print[pDpx, "   ", pDpy, "  Distance = ", (Sqrt[d2])]

Print["z = ", z, "   a x^2 + b y^2 + c z^2 = ", 
      a (x^2) + b (y^2) + c (z^2)]

x = -1.28193; y = -1.63024; Print[pDpx, "   ", pDpy, "  Distance = ", (Sqrt[d2])]

What?  The partial with respect to x is -1.74
            and the partial with respect to y is -1.47???

Print["z = ", z, "   a x^2 + b y^2 + c z^2 = ", 
      a (x^2) + b (y^2) + c (z^2)]

x = 4.90307; y = 2.69818; Print[pDpx, "   ", pDpy, "  Distance = ", (Sqrt[d2])]

Print["z = ", z, "   a x^2 + b y^2 + c z^2 = ", 
      a (x^2) + b (y^2) + c (z^2)]

Summary:
	Largest = 9.69 at (-1.84,-2.68,7.96)
	smallest = 2.03 at (4.90,2.69,1.15)
These answers are not the max and min of the whole problem.

What about the explicit solution with the negative square root?

Clear[x, y, z, dx, dy]; d2 := (((x - p1))^2) + (((y - p2))^2) + (((z - p3))^2); \(z := \(-\@\(\(88 - a\ x\^2 - b\ y\^2\)\/c\)\); 
pDpx\  = \ D[d2, \ x]; 
    
pDpy\  = \ D[d2, \ y]; 
dD = pDpx\ dx + pDpy\ dy\)

N[Solve[{pDpx == 0, pDpy == 0}]]

Exercises

Exercise CD19.4.2: Explicit and Parametric Solutions to Example 19.7

Example 19.7 of the text is stated above.  We know that there are no interior critical values and that  V = 0 when either  w = 0  or  h = 0, so we want the solution to:

The circular boundary optimization question:

Extremize[ V = w*h*(108-2 w-2 h) : 0 ≤ w, 0 ≤ h, (w^2) + (h^2) = (25^2)]

The Explicit Approach

Solve the constraint  (w^2) + (h^2) = (25^2) for  h = ??? and substitute into V:

\(Clear[V, w, h]; 

    h\  = \ \(?? ?;
\ V\  = \ w*h*\((108 - 2\ w - 2\ h)\)\)\)

Solve the 1-D optimization problem:

Extremize[ V = V[w] : 0 ≤ w ≤ 25]

How would you modify this approach to solve the problem on the full circle:

Extremize[ V = w*h*(108-2 w-2 h) :  (w^2) + (h^2) = (25^2)]

The Parametric Approach

We can paramaterize the circular boundary by:

w = 25 Cos[t]
	h = 25 Sin[t]    for  0 ≤ t ≤ π/2

Substitute these into V:

\(Clear[V, w, h, t]; 
V\  = \ w*h*\((108 - 2\ w - 2\ h)\); 

    w\  = \ 25\ Cos[t]; 
h\  = \ 25\ Sin[t]; 
V\)

and solve the 1-D optimization problem:

Extremize[ V = V[t] : 0 ≤ t ≤ π/2]

Extend this approach to solve the whole problem:

Extremize[ V = w*h*(108-2 w-2 h) : 0 ≤ w, 0 ≤ h, (w^2) + (h^2) = (25^2)]

by introducing polar coordiantes:

w = r Cos[t]
	h = r Sin[t]    for  0 ≤ t ≤ π/2  and  0 ≤ r ≤ 25

\(Clear[V, w, h, t, r]; 
V\  = \ w*h*\((108 - 2\ w - 2\ h)\); 

    w\  = \ r\ Cos[t]; 
h\  = \ r\ Sin[t]; 
V\)

and solve the 2-D optimization problem:

Extremize[ V = V[r,t] : 0 ≤ r ≤ 25  &  0 ≤ t ≤ π/2]

How could you extend this approach to the whole circle  (w^2) + (h^2) ≤ (25^2)?

Exercise CD19.5.3

Find the point on the surface  z = (x^2) - ((y^2)/3) nearest to  p = {1,-2,3}.

Exercise CD19.5.4

Find the point on the surface  (x^2) + 2 (y^2) + (z^2) = 88  nearest to  p = {2,-1,-3}.

Exercise CD19.5.6

Find the largest rectangular solid with its faces parallel to the coordiante planes that can be inscribed inside the ellipsoid  ((((x/2)))^2) + ((((y/3)))^2) + (z^2) = 1