Find a point that minimizes the sum squared difference of the distances to a set of other points I have n points in Euclidean space $\{\mathbf{a_1}, \mathbf{a_2}, ... , \mathbf{a_n}\}$, and the desired distances to them $\{d_1, d_2, ..., d_n\}$. How can I find the optimal point $\mathbf{x}$ that minimizes $\sum_{i=1}^n [\lVert \mathbf{x} - \mathbf{a}_i \rVert - d_i]^2$
What I am doing now is put x somewhere, and differentiate the objective. However, gradient descent very often end up in local minima.

Using automaticallyGenerated's answer as a basis for the discussion, you need to minimize
$$\Phi(x,y)=\sum_{i=1}^{n} \left(\sqrt{(x-x_i)^2+(y-y_i)^2}-d_i\right)^2$$ which is highly nonlinear and "good" starting values are required.
You can get those easily if, in a prelimary step, you consider that you have $n$ equations
$$f_i=(x-x_i)^2+(y-y_i)^2-d_i^2=0$$
Now, write the $\frac {n(n-1)}2$ equations $[(i=1,2,\cdots,n-1) \quad\text{and} \quad(j=i+1,i+2,\cdots n)]$
$$f_i-f_j=2(x_i-x_j)x+2(y_i-y_j)y=(d_i^2-x_i^2-y_i^2)-(d_j^2-x_j^2-y_j^2)$$ and a simple linear regression (or matrix calculations) will give you estimates for $x$ and $y$.
If you still want to improve these guesses, minimize in a second step
$$\Psi(x,y)=\sum_{i=1}^{n} \left({(x-x_i)^2+(y-y_i)^2}-d_i^2\right)^2$$ which is better conditioned that $\Phi(x,y)$. For sure, start with the guesses obtained in the first step and obtain new estimates.
Now, you are ready for the minimization of $\Phi(x,y)$ and this would not present any problem. This could even be done using Newton-Raphson method for solving $$\frac{\partial \Phi(x,y) }{\partial x }=\frac{\partial \Phi(x,y) }{\partial y }=0$$ even using numerical derivatives.
