RegionNearest is definitely a lot faster for discretized regions.

In[1]:= region = ImplicitRegion[(x - 2)^4 + (y - 3)^4 <= 1, {x, y}]

Out[1]= ImplicitRegion[(-2 + x)^4 + (-3 + y)^4 <= 1, {x, y}]

In[15]:= AbsoluteTiming @ RegionNearest[region, {-1, 2.1}]

Out[15]= {0.0891469, {1.02305, 2.4537}}

In[13]:= dregion = DiscretizeRegion[region];

In[16]:= AbsoluteTiming @ RegionNearest[dregion, {-1, 2.1}]

Out[16]= {0.00009683, {1.02987, 2.42768}}

Thanks Daniel for explaining. Now the big question: is this considered a bug? Or should one be aware of possible other 'closer' points if one uses 'numerical' input (either starting point or region)?

Oh it's definitely a bug! Or at very least an "issue", even if one concludes that using RegionNearest[] in this way is a bad thing to do. As Sander's first reply to my post shows above, we get inconsistent results using (-0.5,4) vs. (+0.5,4) even for y=x^2, so there is some right-handed bias to the algorithm which (to me) hints at a much deeper problem with the way it searches for a global minimum.

At the very least, the documentation should have mention under Possible Issues that RegionNearest[] and RegionDistance[] may return values at a local minimum. NMinimize[] has a similar disclaimer (which personally I think should be more prominent).

For some reason I am not surprised that NMinimize[] sometimes falls into the trap of a local minimum. That's what happens. (Our students do this all the time, blindly setting the first derivative to zero without plotting the function to see what it looks like.)

But a function called RegionNearest[] sounds like it should "just work", especially for an easy case like this. Well the bug report has been submitted, so let's see what the developers come up with.

I greatly appreciate all the insights shared in these replies, thank you.

What you've done is flatten out the local minimum by discretizing the region?

I'll rephrase. Did the discretization turn the region around the local minimum into a linear function so there was no minimum there?

Thank you for the insightful replies and I shall report this behavior for RegionNearest[]. Do I get a free waffle-maker from Wolfram for finding a bug? :)

I had wondered if RegionNearest[] called ArgMin[] or NArgMin[] at a lower level. How does one determine which functions are used by other functions? Is that documented or proprietary?

It was also interesting (for me anyway) to see that using EuclideanDistance[] reproduces the same problem that I found with RegionNearest[], i.e.

Minimize[{EuclideanDistance[{x, y}, {-1/2, 4}], y - x^2 == 0}, {x, y}] // N  

gives the correct result, while

Minimize[{EuclideanDistance[{x, y}, {-0.5, 4}], y - x^2 == 0}, {x, y}] 

gives the same wrong answer as before. (Note that in the second case, Minimize[] calls NMinimize[] to deal with the inexact value for x.) However, calling Minimize[] or NMinimize[] with my own squared-distance function, a quartic polynomial, works correctly for both (-1/2,4) and (-0.5/4). This is all shown in the original notebook that I attached.

For completeness, I shall mention that under "Possible Issues" for NMinimize[] in the Help documentation, it states "For nonlinear functions, NMinimize[] may sometimes find only a local minimum". Fair warning, although I hoped it would not matter whether my point was on the left or right of the y-axis when dealing with an even polynomial function like y=x^2.

I do not know the implications of such a change, but it sounds reasonable in most instances. At least if there was an option to force these functions to rationalise.

Meanwhile

myRegionNearest[reg_, p_] :=  N@RegionNearest[Rationalize[reg], Rationalize[p]]

might -with the obvious tweaks- work for the time being.

Cheers,

Marco

Hi,

I suppose that the problem is in ArgMin or more precisely NArgMin, which is/are used by RegionNearest:

ArgMin[{Sqrt[Abs[x + 0.5]^2 + Abs[y - 4]^2], {x, y} \[Element] ImplicitRegion[-x^2 + y == 0, {x, y}]}, {x, y}]
(*{1.834, 3.36355}*)

You can help it with:

ArgMin[{(x + 0.5)^2 + (y - 4)^2, {x, y} \[Element]  ImplicitRegion[-x^2 + y == 0, {x, y}] \[And] x < 0}, {x, y}]

but that's certainly not intended. ArgMin uses NArgMin when dealing with approximate numbers. And that seems to cause problems. The following option will help to mitigate the issue:

NArgMin[{(x + 0.5)^2 + (y - 4)^2, {x, y} \[Element] ImplicitRegion[-x^2 + y == 0, {x, y}]}, {x, y}, Method -> "DifferentialEvolution"]
(*{-1.90557, 3.63119}*)

Cheers,

Marco