0

I'm looking at this post, over on Stack Overflow. The relevant portion is as follows:

...first, you need a cost function... which would be something like

$err(x,y,z) = \sum_{i=1}^n\sqrt{[(x-xi)^2 + (y-yi)^2 + (z-zi)^2]} - di$

...where $x, y, z$ are coordinates of the current point in the numerical solution and $xi, yi, zi$ and $di$ are the coordinates and distance towards the $i$th reference point. In order to solve this - my advice is NOT to use Newton/Gauss or Newton methods. You need first and second derivative of the aforementioned function - and those have a finite discontinuation in some points in space - hence that is not a smooth function and these methods won't work. What will work is direct search family of algorithms for optimization of functions (finding minimums and maximums. in our case - you need minimum of the error/cost function).

Where I'm lost

I've seen cost functions only in the context of machine learning and, admittedly, to limited extent. Why is it that a 'cost function' works here, "intuitively"?

Moreover, it isn't obvious to me precisely what sort of algorithm OP is referring to ("direct search family of algorithms"), nor how that would be applied to a summation such as this in practice.

Could someone please elaborate, and offer a more in-depth explanation?

Many thanks.

10GeV
  • 1,371
  • I'm not sure I agree with the comment that "direct search" algorithms should be used for this problem. I would need to see the final "cost function" that you end up minimizing, but it seems likely that you will be solving some typical convex problem and that faster methods will be available, even if the cost function is not smooth. There are faster ways to minimize the function $\text{err}(x,y,z)$ given here. Although, if you really only have three variables in your optimization problem, a brute force grid search might be fine and would be simple to implement. – littleO Nov 14 '20 at 20:03
  • @littleO Perhaps you could suggest a method? – 10GeV Nov 14 '20 at 20:04
  • By the way I don't think $d_i$ should be inside the radical. It seems to have been transcribed incorrectly. – littleO Nov 14 '20 at 20:12
  • @littleO Yes, apologies. I'll correct that, thanks for pointing it out. What alternatives to a brute force grid search are feasible? In my case, I can't necessarily put bounds on the potential solution (i.e. define a search interval). Or perhaps brute force grid search could be used in combination with some method of estimating an initial value? – 10GeV Nov 14 '20 at 20:13
  • Thanks. Now that that's been corrected, I think there's something strange about this function $\text{err}(x,y,z)$ because the numbers $d_i$ have no effect on the minimizer of this function. You could change the $d_i$ values and your minimizer would not change. I think perhaps each term in the sum should be squared. – littleO Nov 15 '20 at 00:29
  • @littleO. I think that absolute values must be used. – Claude Leibovici Nov 17 '20 at 10:54

1 Answers1

1

As @littleO commented, this is a very strange setting of the problem.

The distance between the source and the current point is $$\tilde d_i=\sqrt{(x-x_i)^2 + (y-y_i)^2 + (z-z_i)^2}$$ while the measured value is $d_i$. So, if you have three points and no noise you can solve for $(x,y,z)$ the three equations $\tilde d_i=d_i$.

Otherwise, you could do it using as a "cost function"

$$\text{err}(x,y,z) = \sum_{i=1}^n\color{red}{\Bigg|}\sqrt{(x-x_i)^2 + (y-y_i)^2 + (z-z_i)^2}-d_i\color{red}{\Bigg|} $$ which is a totally different story (and, I would say, a very difficult problem from a numerical point of view.

If you are interested by a solution which would give you good estimates of $(x,y,z)$ to start with, let me know and I shall edit.

Claude Leibovici
  • 260,315
  • Thanks for the answer. Yes, I'd be interested in a solution which could provide good estimates (if nothing else, to serve as a starting point for some solution finder) – 10GeV Nov 17 '20 at 12:27
  • 1
    @KeithMadison. I did not remember that i made this answer (age problem !!); Have a look at https://math.stackexchange.com/questions/1338323/finding-an-unknown-location-with-known-distances-from-location/1338429#1338429 If it is not clear, just ping me. Cheers :-) – Claude Leibovici Nov 17 '20 at 12:40