Minimizing sum of squared distances from point to spheres 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.)
 A: 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.
A: 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.
A: 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. 
