I am looking for an algorithm to find the point that minimizes the sum of the great circle distances to a set of fixed points on a sphere.

In more detail: Given $x_1,\ldots, x_k$ fixed points in the $\mathbb{R}^n$ sphere. All of them have non-negative coefficients, i.e., $\|x_i\| = 1$ and $x_{ij} \geq 0$. I wish an algorithm to find the point $y$ such that $\|y\|=1$ minimizing $\sum_{i=1}^k d_{x_i}(y)$, where $d_{x_i}(y) = \arccos( \langle x,y \rangle)$.

I know this is considered a facility location problem but I can't find any algorithm that solves this particular problem.

  • $\begingroup$ Have you tried gradient descent or some other mathematical optimization procedure? $\endgroup$
    – D.W.
    Sep 9, 2015 at 18:16
  • $\begingroup$ I am working on an local search algorithm which involves calculating gradient and hessian and proyect them on the tangent plane look for minimum there and move in that direction. The problem I encounter is that hessian is not defined when $y=x_i$ for any $i$. The Hessian coeficients tend to infinity when $y \to x_i$ and the gradient tends to zero. I am not sure how to deal with that problem. $\endgroup$
    – Manuel
    Sep 9, 2015 at 19:43
  • $\begingroup$ Does this affect gradient descent? Gradient descent doesn't require computing the Hessian; only the Jacobian. Newton-style methods (e.g., BFGS) use the Hessian (the first two derivatives, basically); gradient descent uses only the Jacobian (the first derivative, basically). So, maybe gradient descent will fare better? Anyway, that sounds like good information to include in the question. A standard piece of advice for improving your question is: tell us what approach you've tried, and why you rejected that approach or what difficulties you ran into. $\endgroup$
    – D.W.
    Sep 9, 2015 at 21:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.