Understanding the minimization of this "cost function"

100 Views Asked by At

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.

1

There are 1 best solutions below

2
On

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.