# NMaximize not finding global maximum

I'm trying to find the place on a highway that's furthest from it's nearest gas station. Here are the functions I'm using.

dist[x_?NumericQ, stations_] := Abs[x - Nearest[stations, x][[1]]];
maxdist[lowerbound_, upperbound_, stations_] :=
NMaximize[{dist[x, stations], lowerbound < x < upperbound}, x];


Here are the mile markers of my gas stations:

stations={22, 25, 27, 31, 34, 42, 47, 52, 54, 62, 63, 70, 71, 74, 78, 80,
84, 101, 106, 110, 115, 136, 137, 143, 149, 151, 154, 169, 174, 175, 176,
182, 184, 196, 206, 215, 220, 221, 226, 231, 245, 254, 257, 264, 270,
272};


maxdist[20,272,stations] yields {8.5,{x->92.5}}

But that's obviously not the largest, as dist[125.5,stations] gives 10.5. Why is NMaximize not finding that global maximum?

A side note: There is an obvious workaround that avoids NMaximize (see below), but I'm curious to know why NMaximize isn't working.

maxdist2[lowerbound_, upperbound_, stations_] := Max[Table[dist[x,
stations], {x, lowerbound, upperbound, 0.5}]]

• simply your function is nonlinear and NMaximise is not guaranteed to find a global maximum. Plot[dist[x, stations], {x, 20, 272}] – george2079 Jun 23 '17 at 17:06
• @george2079 Hmm... I suppose that is probably it. But why does the documentation suggest that it tries to find the global maximum? From the documentation: "NMaximize always attempts to find a global maximum of f subject to the constraints given." I guess it tried but failed. Maybe Nearest[] is making it hard for it. – Shane Jun 23 '17 at 17:11
• its the if linear .. otherwise bullet items under details that bite you here. – george2079 Jun 23 '17 at 17:13
• Indeed. So I guess the documentation doesn't promise anything. I just expected a slightly better effort from NMaximize than the one I got! Thanks for the explanation! – Shane Jun 23 '17 at 17:16
• total aside but if you are on the highway the distance to a gas station that is behind you doesn't do you much good (Wish whoever coded my garmin understood that! ) – george2079 Jun 23 '17 at 17:20

if you really have this simple 1-d problem you know the answer is the midpoint between the furthest spaced stations. get the answer quickly like this:

(Mean /@ #)[[Ordering[Abs[Subtract @@@ #]][[-1]]]] &@
Partition[Sort@stations, 2, 1] // N


125.5

• This is very nice, but your comment is actually a better answer than this as my question is on the cause of the failure (and I have my own workaround in the question). Maybe edit this to incorporate your comments and I'll select this as the answer? – Shane Jun 23 '17 at 17:13

We can find the maximum difference between two stations simply with

max = MaximalBy[Partition[stations, 2, 1], Differences]


{{115, 136}}

Mean @@ max // N


125.5