Minimizing sum of squared distances from point to spheres

Question

Given some spheres with known radius and known origin in three dimensional space, I want to find the point P that lies "closest" to all these spheres. The meassure of closeness, I guess, will be the sum of the squared distances from the point P to each of the spheres.

Is there any good solution to this problem? Any numerical solution that will converge to give the correct answer, or any fixed solution? As far as I know this problem is neither convex nor linear, so I am fearing the worst.

(With close to sphere, I mean close to the boundary of the sphere. If it lies outside or inside does not matter.)

Answer 1

The distance from $P$ to a sphere $S_i$ can be expressed as

$d_i = \max \{ ||P-C_i||_2 - R_i, R_i - ||P-C_i||_2\},$

so that your problem is

$\min \sum d^2_i $

$ d_i \geq ||P-C_i||_2 - R_i \quad i=1,...$

$ d_i \geq R_i - ||P-C_i||_2\quad i=1,...$

This is a nonconvex smooth nonlinear optimization problem, due to the second set of constraints. In general I guess some randomized algorithm coupled with smooth local searches would do. But of course depends on how many spheres.

Answer 2

You might be able to formulate this as a Lagrange multiplier problem. As said, the squared distance from (x, y, z) to a sphere with radius $r_1$ and centre $(a_1, b_1, c_1)$ is $d_1^2 = (x-a_1)^2+(y-b_1)^2+(z-c_1)^2 - r_1^2$ and minus this if the point is inside the sphere. Let's look for a solution outside the 3 spheres (well separated spheres?). Then we have the Lagrange function

$L = d_1^2+d_2^2+d_3^2 - \alpha C_1-\beta C_2-\gamma C_3$

where $C_1$ is the constraint $(x_1-a_1)^2+(y_1-b_1)^2+(z_1-c_1)^2 - r_1^2 = 0$ and $C_1$ and $C_2$ are similarly defined in terms of variables $(x_2, y_2, z_2)$ and $(x_3, y_3, z_3)$.
The Lagrange equations to solve will then be in terms of 15 variables $(x, y, z)$, $(x_1, y_1, z_1)$, $(x_2, y_2, z_2)$, $(x_3, y_3, z_3)$ and $\alpha , \beta , \gamma$. Mathematica or some such might be able to solve these equations.

Answer 3

If the centers are given by the points $y_i$ and the radii are $r_i$, the function to minimize is:

$$ f(x) = \sum_{i=1}^N (\|x-y_i\| - r_i)^2 $$

The function is not differentiable at the centers $y_i$, but everywhere else the gradient is given by the formula:

$$ \nabla f(x) = 2 \sum_{i=1}^N x-y_i - r_i\frac{x-y_i}{\|x-y_i\|} $$

So minimizers of $f$ are either one of the centers, or else satisfy $\nabla f(x)=0$, equivalently: $$ x = \frac{1}{N}\sum_{i=1}^N y_i + r_i\frac{x-y_i}{\|x-y_i\|} $$

This suggests using the fixed-point iteration:

$$ \begin{aligned} x_0 &= \frac{1}{N}\sum_{i=1}^N y_i \\ x_{t+1} &= \frac{1}{N}\sum_{i=1}^N y_i + r_i\frac{x_{t}-y_i}{\|x_t-y_i\|} \end{aligned} $$ No guarantees this will work, but testing it out on a few problems with 1000 points in $\mathbb{R}^3$, and it seemed to converge linearly.