# Using NMinimize Properly

I'd like to find the point on a Bezier curve that's closest to some other point. The tricky thing is that because Bezier curves can loop around, the distance function can have multiple local minima along the length of the curve. I figured the easiest way to find the point I'm after would be to use NMinimize. So I create a curve, create a BezierFunction, and then use NMinimize. Here I'm trying to find the Bezier point closest to {9,5}:

bezXY = {{3, -9}, {3., -4}, {14, -4}, {16, -12}};
bezF = BezierFunction[bezXY];
dist2D[p_, q_] := Sqrt[Apply[Plus, (p-q)^2]];
NMinimize[{dist2D[{9, 5}, bezF[t]], 0 <= t <= 1}, t]


This fails with multiple errors of the form:

Part::partw: Part 2 of BezierFunction[1,{{0.,1.}},{3},{{{3.,-9.},{3.,-4.},{14.,-4.},{16.,-12.}},{}},{0},MachinePrecision,Unevaluated][t] does not exist. >>


I believe the problem is that NMinimize is handing bezF values outside of [0,1], in which case bezF doesn't return a point. Restricting the domain of t to [0,1] unfortunately doesn't solve the problem - this line produces similar errors:

NMinimize[{dist2D[{9, 5}, bezF[t]], 0 <= t <= 1}, {{t, 0, 1}}]


I've tried wrapping bezF in various ways so that it always returns something valid. Here's a typical attempt:

bezF2[v_] := bezF[Max[0, Min[1, v]]];


If I use bezF2 instead of bezF in the call to NMinimize, it too fails with multiple errors. Writing bezF2 as a Module doesn't improve things.

I'm not sure exactly what's going wrong here, so I'm not sure how to fix it. Any guidance would be appreciated; the more concrete and practical the better. Thank you!

-

The reason you are having problems is that NMinimize (or FindMinimum for that matter) are Holding the argument of the function, so that you are not getting the evaluated value of bezF at whatever value of t inside the minimisation.

The Trace output from FindMinimum shows what it going on. (The output from NMinimize shows the same issue but it's longer and messier.) For simplicity in the Trace I changed your distance function to the equivalant:

dist2D[p_, q_] := Sqrt[Total[(p - q)^2]];


So we have:

FindMinimum[{dist2D[{9, 5}, bezF[t]], 0 <= t <= 1}, {t, 0.45}] // Trace

{FindMinimum[{dist2D[{9,5},bezF[t]],0<=t<=1},{t,0.45}],
{{{{bezF,BezierFunction[{{0.,1.}},<>]},BezierFunction[{{0.,1.}},<>][t]},
dist2D[{9,5},BezierFunction[{{0.,1.}},<>][t]],
Sqrt[Total[({9,5}-BezierFunction[{{0.,1.}},<>][t])^2]],
{{{{9,5}-BezierFunction[{{0.,1.}},<>][t],
{9-BezierFunction[{{0.,1.}},<>][t],5-BezierFunction[{{0.,1.}},<>][t]}},
{9-BezierFunction[{{0.,1.}},<>][t],5-BezierFunction[{{0.,1.}},<>][t]}^2,
{(9-BezierFunction[{{0.,1.}},<>][t])^2,(5-BezierFunction[{{0.,1.}},<>][t])^2}},
Total[{(9-BezierFunction[{{0.,1.}},<>][t])^2,(5-BezierFunction[{{0.,1.}},<>][t])^2}],
(5-BezierFunction[{{0.,1.}},<>][t])^2+(9-BezierFunction[{{0.,1.}},<>][t])^2},
\[Sqrt]((5-BezierFunction[{{0.,1.}},<>][t])^2+(9-BezierFunction[{{0.,1.}},<>][t])^2),
\[Sqrt]((5-BezierFunction[{{0.,1.}},<>][t])^2+(9-BezierFunction[{{0.,1.}},<>][t])^2)},
{\[Sqrt]((5-BezierFunction[{{0.,1.}},<>][t])^2+(9-BezierFunction[{{0.,1.}},<>][t])^2),0<=t<=1}},
{{t}=.,{t=.},{t=.,Null},{Null}},{{t}=.,{t=.},{t=.,Null},{Null}},
FindMinimum[{dist2D[{9,5},bezF[t]],0<=t<=1},{t,0.45}]}


The distance function is evaluating before the BezierFunction is, and you are ending up with a vector {9, 5} being subtracted from a single BezierFunction expression, which then evaluates to a vector, so you are ending up with a matrix, which then ends up as a vector when you use Total or Plus on it.

So what you really want is the distance between the first element of the point vector {9,5}, and the first element that eventually comes out of the Bezier function, and then the distance between the two second elements, and sum that. That's like the diagonal elements of a matrix, so perhaps you want the matrix trace, Tr.

dist2Da[p_, q_] := Sqrt@Tr[Total[(p - q)^2]];

FindMinimum[{dist2Da[{9, 5}, bezF[t]]}, {t, 0.2}]


{18.2237, {t -> 0.425675}}

This looks like the wrong value for the distance but the right position of the minimum given this plot.

ListLinePlot[Table[{t, dist2D[{9, 5}, bezF[t]]}, {t, 0, 0.99, 0.01}]]


You might be able to get FindMinimum to work without Tr (and possibly the wrong distance measure) using one of the tricks to inject evaluated expressions into Held expressions but so far I have not managed to get this to work.

-