How do I know whether a local minima is also global?

Question

In the region $0\leq x\leq 1$ and $0\leq y\leq 1$ I have 1 radio broadcaster placed in $(x_b,y_b)$ and N receivers. The position of the broadcaster is not known. The position of each receiver however is known: $(x_i,y_i)$ as is the distance from the receiver to the broadcaster: $d_i$. There is some noise in the distance measurements that I assume to be normal distributed with mean=0 and the same variance for all receivers.

My goal is to estimate the most likely position of the radio broadcaster: $(x_b,y_b)$.

I do this by minimizing: $$ SE = \sum_i \left[\sqrt{(x_b - x_i)^2+(y_b - y_i)^2} - d_i\right]^2 $$ using scipy.optimize.minimize().

This approach seems to work fine. However how do I know that the local minima I find is also the global minima? In this example I can plot $SE(x_b,y_b)$:

However my real problem is estimating the position: $(x,y,z)$ and the orientation of a camera: $(roll,pitch,yaw)$. There is no way I can visualize 6D space. Therefore I am looking for some other way to check whether a found minima is global.

As far as I understand there are only two ways to show that there is only 1 local minima?

Method I

Show that $$ \frac{\partial SE}{\partial x_b} = \frac{\partial SE}{\partial y_b} = 0 $$ only has 1 solution and that all the eigenvalues of the Hessian of SE in this point are positive.

Method II

Show that SE is convex by showing that all eigenvalues of the Hessian of SE are positive at all points.

Let us try method I.

I find that: $$ \frac{\partial SE}{\partial x_b} = \Sigma_i 2 (x_b - x_i) \frac{\sqrt{(x_b - x_i)^2 + (y_b - y_i)^2} - d_i}{\sqrt{(x_b - x_i)^2 + (y_b - y_i)^2}} $$

$$ \frac{\partial SE}{\partial y_b} = \Sigma_i 2 (y_b - y_i) \frac{\sqrt{(x_b - x_i)^2 + (y_b - y_i)^2} - d_i}{\sqrt{(x_b - x_i)^2 + (y_b - y_i)^2}} $$

How many solutions do $$ \frac{\partial SE}{\partial x_b} = \frac{\partial SE}{\partial y_b} = 0 $$ have? Difficult to tell, I guess it dependens on the $\{(x_i,y_i,d_i)\}$ values?

Method II seems even harder.

Answer 1

One way to do this - although it does not guarantee that you found a global optimum - is to apply one (or more) of the Scipy global optimisers and let them run with a very generous amount of iterations/functions evaluations.

Since you only have 6 parameters, optimisers like SHGO, Dual Annealing, etc… might be able to explore the parameters space well enough to give you a reasonable probability that you found a very good optimum. Multiple random restarts with a local solver is also a possibility.

But beside a fine/grained brute force attack followed by a local optimisation, I don’t see a way to have a guarantee that your optimum is a global one.

If you have your model formulation in Python and you can post it - together with some data to make it runnable - I’d be curious to give it a try with my personal collection of optimisers.

Answer 2

SDP relaxation solution.

The original optimization problem is equivalent to the following one: \begin{align*} (\mathrm{P}) &\min_{x_b,\, y_b;\, \{z_i\}_{i=1}^n} \quad \sum_{i=1}^n [(x_b - x_i)^2 + (y_b - y_i)^2] + \sum_{i=1}^n d_i^2 - \sum_{i=1}^n 2d_i z_i \\ &\mathrm{s.t.}\quad (x_b - x_i)^2 + (y_b - y_i)^2 \ge z_i^2, \quad i = 1, 2, \cdots, n. \end{align*}

Let $$X := \begin{bmatrix} x_b \\ y_b \\ 1 \end{bmatrix}\begin{bmatrix} x_b \\ y_b \\ 1 \end{bmatrix}^\top = \begin{bmatrix} x_b^2 & x_by_b & x_b \\ x_by_b & y_b^2 & y_b \\ x_b & y_b & 1 \end{bmatrix}. $$

The problem (P) is written as \begin{align*} (\mathrm{P}1) &\min_{X;\, \{z_i\}_{i=1}^n} \quad \sum_{i=1}^n [X_{11} + X_{22} - 2x_iX_{13} - 2y_iX_{23} + x_i^2 + y_i^2] + \sum_{i=1}^n d_i^2 - \sum_{i=1}^n 2d_i z_i \\ &\mathrm{s.t.}\quad X_{11} + X_{22} - 2x_iX_{13} - 2y_iX_{23} + x_i^2 + y_i^2\ge z_i^2, \quad i = 1, 2, \cdots, n;\\ &\qquad\,\, X_{33} = 1, \quad \mathrm{rank}(X) = 1, \quad X \succeq 0. \end{align*}

If we drop the constraint $\mathrm{rank}(X) = 1$, we turn to solve the SDP relaxation \begin{align*} (\mathrm{P}2) &\min_{X;\, \{z_i\}_{i=1}^n} \quad \sum_{i=1}^n [X_{11} + X_{22} - 2x_iX_{13} - 2y_iX_{23} + x_i^2 + y_i^2] + \sum_{i=1}^n d_i^2 - \sum_{i=1}^n 2d_i z_i \\ &\mathrm{s.t.}\quad X_{11} + X_{22} - 2x_iX_{13} - 2y_iX_{23} + x_i^2 + y_i^2\ge z_i^2, \quad i = 1, 2, \cdots, n;\\ &\qquad\,\, X_{33} = 1, \quad X \succeq 0. \end{align*}

We can use CVX+Matlab to solve (P2). If the solution to (P2) has a rank one, then we obtain the global minimum of the original problem.

I tested some $n= 20$ randomly generated $x_i$'s, $y_i$'s, and $d$'s. In these examples, it works well.