Find minimum or maximum of multi-variable function

[teerasak]

I'm not sure whether there is a function or command which can find the minimum or maximum of multi-variable function e.g

find min of Sqrt((x-14)^2 + (y-55)^2) + Sqrt((x-23)^2 + (y-95)^2)

Or any application which can help finding this kind of problem?

[jlind]

(08-28-2019 07:14 AM)teerasak Wrote:  I'm not sure whether there is a function or command which can find the minimum or maximum of multi-variable function e.g.

find min of Sqrt((x-14)^2 + (y-55)^2) + Sqrt((x-23)^2 + (y-95)^2)

Or any application which can help finding this kind of problem?

This is a multivariate calculus problem with the function f(x,y) = z, where z is the unstated dependent variable for the equation you gave for the third z-axis. Fortunately your two independent variables, x and y, aren't completely jumbled together. Conceptually it's the same approach as univariate calculus. The zeroes of the first partial derivatives will help identify maxima, minima, and saddle points, if there are any, where the slope of the tangent plane is zero. This involves finding partial derivatives of f(x,y) as part of the solution and it sets up a partial derivative vector called the gradient. A gradient is the same concept as a slope in three (or more) dimensions as a plane (in three dimensions) or a hyper-plane in four or more dimensions. When the set of all (x,y) are found that are zeroes of both the partial derivatives with respect to both x and y, it's called the set of zero vectors. Among them should be (if they exist) the global maximum, the global minimum, other local maxima, other local minima, and a phenomenon not found in univariate calculus, saddle points. Local maxima are other hilltops not as tall as the tallest peak in the mountain range. A saddle point looks like a saddle, and it's the low spot between two or more peaks that rises in their direction and falls off in the directions between the peaks.

See this video from the Kahn Academy and its follow-on videos to give you a conceptual idea of what you'll need to do . . .
https://www.khanacademy.org/math/multiva...and-minima

With regard to the HP Prime, look for the Gradient tools in its derivative calculus toolbox. Hope this helps get you started. The conceptual aspect of what you want to do is well over half the battle. You'll undoubtedly have to poke around a bit to find what you need to use and how to use it in the calculator. Looked for some things in the Prime documentation which isn't as helpful as it could be. Been decades since I did this stuff. All we had was pencils, engineering pads, a slide rule, and the CAS calculator was the CRC Handbook of Mathematical Tables (which has sections on derivatives and integrals). :-D

BTW, don't think of math involving three or more independent variables in hyperspaces as being that exotic. There are a multitude of practical applications for it in maximizing or minimizing aspects of physical processes and systems with multiple inputs or controls when responses are non-linear.

John

[parisse]

This is the sum of distances of M(x,y) to 2 points A(14,55) and B(23,95). Therefore the min is any point in the segment AB. Multivariate calculus would fail here, because the minimum is not isolated (the gradient is 0 in the segment).

[roadrunner]

If you plot the equation n the 3D app:

sqrt((X-14)^2+(Y-55)^2)+sqrt((X-23)^2+(Y-95)^2)

Tap Menu/Zoom/Out 4 or 5 times, then go to the plot setup the new Zoom values are not saved. Is there a way to use Menu/Zoom/Out and have the zoom settings saved in Xmin, Xmax, Ymin, Ymax, Zmin, and Zmax?

-road

[teerasak]

@jlind, Thank you. It is time to come back to review multi-variable calculus which has gone from my head. Thank you for the info and link.

@parissee, you are right. So the minimum for this case is the distance between two point, which is 41. However, I’m not sure, in HP prime, is there the command to find Min/max of multi-variable function? One tools I use is 3D graph. It helps but quite difficult to read the value, and no tools to find extremum in the graph.

@roadrunner, I faced the same issue too. For this problem, I zoom out few time to see the 3D graph. After I quit from the plot, and come back, the scale go back to default.

[teerasak]

I tried to find derivative of the function to x and to y, and use solve command to find the value x, and y to make the derivative to zero, as in the pictures.

I got strange calculation result c_0. What does it mean? I try to evaluate it numerically, it still leave c_0 as the result.

[Csaba Tizedes]

(08-29-2019 07:19 PM)teerasak Wrote:  So the minimum for this case is the distance between two point, which is 41.

Just put a third point and you will jump to the complex problems world. If you interested, here you can find a sloooow solution on a TI-83:





Csaba

[parisse]

(08-29-2019 07:19 PM)teerasak Wrote:  @parissee, you are right. So the minimum for this case is the distance between two point, which is 41. However, I’m not sure, in HP prime, is there the command to find Min/max of multi-variable function? One tools I use is 3D graph. It helps but quite difficult to read the value, and no tools to find extremum in the graph.

There is an extrema command in Xcas to do that, but it seems it is not available in the Prime CAS.

[teerasak]

@parisse , that's really unfortunate for not having that command. So need to find out from derivative and solve equation. Thank you for information.

[jte]

(08-28-2019 05:29 PM)roadrunner Wrote:  If you plot the equation n the 3D app:

sqrt((X-14)^2+(Y-55)^2)+sqrt((X-23)^2+(Y-95)^2)

Tap Menu/Zoom/Out 4 or 5 times, then go to the plot setup the new Zoom values are not saved. Is there a way to use Menu/Zoom/Out and have the zoom settings saved in Xmin, Xmax, Ymin, Ymax, Zmin, and Zmax?

I've noticed this too and have been meaning to go over the Graph 3D interface, but have now explicitly put this on the list of things to be fixed.

[jte]

One thing that can be done is to graph the zero sets of the two partial derivatives and see where they overlap. I'm attaching a screen shot of what comes up in the Advanced Graphing app if you do that.

   

That there are three colours is, unfortunately, not as obvious as might be desired.

If you switch the tracing mode to intersections between the two sets (via Trace / PoI / Intersections with...), it's fairly clear that you can trace along the line segment between (14,55) and (23,95).

(...although Trace / Inside can give nicer coordinates near the line segment endpoints.) Using a long hold to position the cursor also shows a difference in the overlap region, in that you must choose which set to use with the tracing cursor.

[toml_12953]

(08-28-2019 02:33 PM)jlind Wrote:  

(08-28-2019 07:14 AM)teerasak Wrote:  I'm not sure whether there is a function or command which can find the minimum or maximum of multi-variable function e.g.

find min of Sqrt((x-14)^2 + (y-55)^2) + Sqrt((x-23)^2 + (y-95)^2)

Or any application which can help finding this kind of problem?

This is a multivariate calculus problem with the function f(x,y) = z, where z is the unstated dependent variable for the equation you gave for the third z-axis.

Are you a teacher? If not, you should be. Even I understood your explanation!

[jte]

Another plot you could consider is one showing where there two partial derivatives are non-negative and then look for overlapping boundaries. Two things to watch out for with this approach is where the partial derivatives are discontinuous or are locally constant (zero in particular). With this example, the regions are larger and the three colours more obvious in an Advanced Graphing plot, as shown by the attached screenshot.

   

[jte]

Oh!.... now that my brain is actually starting to engage... using AND is certainly another possibility, to plot where both partial derivatives are zero.

       

[rawi]

Quote:I'm not sure whether there is a function or command which can find the minimum or maximum of multi-variable function e.g

find min of Sqrt((x-14)^2 + (y-55)^2) + Sqrt((x-23)^2 + (y-95)^2)

Or any application which can help finding this kind of problem?

I have written a program called NMO for optimization for multivariate functions using Nelder-Mead-Method (a variant of the Simplex Method) that can be found her: https://www.hpmuseum.org/forum/thread-16426.html

You have to put in a function FUNCX() with L1(1) as x and L1(2) as y which in your case looks like this (> stands for STO |> ):

EXPORT FUNCX()
BEGIN
LOCAL Q1;
SQRT((L1(1)-14)^2+(L1(2)-55)^2)+SQRT((L1(1)-23)+(L1(2)-95)^2) > Q1;
RETURN Q1;
END;

Then you have to put starting values in L1, e.g. {14,55} > L1

Then call NMO

Put in 0.5 for S0 (ininitial step width) and 0.0001 for E0 (termination criterion) and 500 for ITM (maximum number of iterations) and press OK.

Within seconds the procedure stops at Minimum 41.000000. At list L1 you see the minimum value is exactly your starting point 14 and 55.
The same is the case if you start with x=23 and y=95. We get the same minimum 41.00000 for x=23 and y=95

If we start with {0,0} we get exactly the same function value 41.000000 with x = 15.7478 and y = 62,7679.

So your problem seems to have multiple minima.

[jte]

(08-16-2021 08:57 AM)rawi Wrote:  

Quote:I’m not sure whether there is a function or command which can find the minimum or maximum of multi-variable function e.g

find min of Sqrt((x-14)^2 + (y-55)^2) + Sqrt((x-23)^2 + (y-95)^2)

Or any application which can help finding this kind of problem?

I have written a program called NMO for optimization for multivariate functions using Nelder-Mead-Method (a variant of the Simplex Method) that can be found her: https://www.hpmuseum.org/forum/thread-16426.html

I just tried it out! I did notice what seems to be a slight typo: “Parmater” (instead of “Parameter”, I’m assuming…).

Quote:You have to put in a function FUNCX() with L1(1) as x and L1(2) as y which in your case looks like this (> stands for STO |> ):

EXPORT FUNCX()
BEGIN
LOCAL Q1;
SQRT((L1(1)-14)^2+(L1(2)-55)^2)+SQRT((L1(1)-23)+(L1(2)-95)^2) > Q1
RETURN Q1;
END;

Then you have to put starting values in L1, e.g. {14,55} > L1

Then call NMO

Put in 0.5 for S0 (ininitial step width) and 0.0001 for E0 (termination criterion) and 500 for ITM (maximum number of iterations) and press OK.

Within seconds the procedure stops at Minimum 41.000000. At list L1 you see the minimum value is exactly your starting point 14 and 55.
The same is the case if you start with x=23 and y=95. We get the same minimum 41.00000 for x=23 and y=95

If we start with {0,0} we get exactly the same function value 41.000000 with x = 15.7478 and y = 62,7679.

I got the same results once I got all four squaring operations into my local FUNCX.

Code:

{23,95}▶L1; NMO(0.5,0.0001,500); L1
{23,95}

{14,55}▶L1; NMO(0.5,0.0001,500); L1
{14,55}

{0,0}▶L1; NMO(0.5,0.0001,500); L1
{15.7478084758,62.767948195}

(With an Fmin of 41 reported in each case.) Of course, I had to play around and try some other values!

Quote:So your problem seems to have multiple minima.

Yes; the Advanced Graphing plot above (of a line segment) shows where the minima are.

(To be more precise: the plot contains the intersection of the zero sets of the two partial derivatives. This intersection, in turn, contains the extrema [minima, maxima, and saddle points], excepting perhaps the endpoints of the segment [as there are divisions by zero there; some additional care is warranted there], as the partial derivatives exist. Second [partial] derivative tests can further clarify the situation, and could be plotted… or a little thought can be put in whilst looking at the original function. [To rule out the other types of extrema or to recognize it is the sum of distances between two points.])

[Albert Chan]

(08-30-2019 11:01 AM)teerasak Wrote:  I got strange calculation result c_0. What does it mean? I try to evaluate it numerically, it still leave c_0 as the result.

The solution substituted back to sum of distance get it right.

XCAS> a := sqrt((x-14)^2 + (y-55)^2)
XCAS> b := sqrt((x-23)^2 + (y-95)^2)
XCAS> sol := solve(diff(a+b,x)=0 and diff(a+b,y)=0, [x,y])

[[(9*c__0+574)/41,(40*c__0+2255)/41] , [(-9*c__0+574)/41,(-40*c__0+2255)/41]]

XCAS> simplify(subst(a+b, [x,y]=sol[0]))

abs(c__0) + abs(c__0 - 41)

minimum sum of distance = 41

This is equivalent to do translation and rotation by hand (distance preserved)

sum of distance
= (|z - (14+55i)|) + |z - (23+95i)|)
= (|z'| + |z' - (9+40i)|) * |(9-40i)/41|         // z' = z - (14+55i)
= (|z''| + |z'' - 41|)                                    // z'' = z' * (9-40i)/41

z = z' + (14+55i) = z'' * (9+40i)/41 + (14+55i) = (9*z''+574)/41 + (40*z''+2255)/41

[jte]

One thing I didn’t realize until recently is that there certainly is a possibility of a bit of ambiguity in “find the minimum or maximum of…“. I was assuming the location of the extrema was wanted (whereas I’d think it the value of the extrema that was wanted if “find the minimum or maximum value of…” were the expression used). And, conversely, to clarify that it’s the location that’s wanted something like “find the location of the minimum or maximum value of…” could be employed. I’m not sure if there’s patterns in how different people interpret it. (I’m guessing it depends on things like textbooks read and classes attended…)

(08-28-2019 05:29 PM)roadrunner Wrote:  If you plot the equation n the 3D app:

sqrt((X-14)^2+(Y-55)^2)+sqrt((X-23)^2+(Y-95)^2)
⋮

One way to empirically check (non-rigorously) how a value relates to a function is to add a level plane to the plot (add FZ(X,Y)=K for a chosen constant K), as shown by these screenshots:

           

The first and second have a plane at Z=41 added. Peeking beneath doesn’t show any of the function falling below Z=41. For the third, I’ve raised the plane to Z=41.5 and now see a little bit of the surface dropping beneath the horizontal plane.

[jte]

(08-28-2019 05:29 PM)roadrunner Wrote:  … the 3D app: … Tap Menu/Zoom/Out 4 or 5 times, then go to the plot setup the new Zoom values are not saved. …

Thanks for posting. I filed a bug report for this on the bug tracking site I’ve set up. … and the bug got fixed!

(If anyone reading this would like an account on the bug tracker I’ve set up to help organize matters, just let me know by PM.)