# Polynomial roots finding algorithm

My initial problem is a parameter estimation problem that is solved by minimining a least-square criterion with the Gauss-Newton algorithm. However finding a good initial iterate is very tedious. I've managed to recast the problem as a polynomial root finding one, but I don't know if it can be efficiently solved (in a relatively fast and precise manner).

The initial problem is to estimate the parameters $[x_0,y_0,\dot{x},\dot{y}]^\intercal$ given a vector of measurments $\mathbf{z}=[z_1,z_2,...,z_N]^\intercal$.

Where

\begin{align} z_k&=\dot{r}_1(k)+\dot{r}_2(k) \\ &=\frac{ \dot{x}(x_k+a)+\dot{y}y_k}{\sqrt{(x_k+a)^2+y_k^2}}+\frac{ \dot{x}(x_k-a) +\dot{y}y_k}{\sqrt{(x_k-a)^2+y_k^2}} \end{align} Where $a$ is a known constant. $\dot{x}$ and $\dot{y}$ are unknown constant and, for convenience : \begin{align} x_k=x_0+\dot{x}k\Delta t \\ y_k=y_0+\dot{y}k\Delta t \end{align}

In fact, $[x_0,y_0,\dot{x},\dot{y}]$ is the position and velocity of a target, $\dot{r}_1(k)$ is the range between the target and a sensor located in $[-a,0]^\intercal$ at time step $k$ and $\dot{r}_2(k)$ is the range between the target and a sensor located in $[a,0]^\intercal$.

So the locus of points $[x_k,y_k]^\intercal$ such that $r_1(k)+r_2(k)=\sqrt{(x_k+a)^2+y_k^2}+\sqrt{(x_k-a)^2+y_k^2}$ is an ellipse with foci $[-a,0]^\intercal$ and $[a,0]^\intercal$.

As such it is possible to rewrite $r_1(k)+r_2(k)$ as :

\begin{align} r_1(k)+r_2(k)=2\sqrt{a^2+x_k^2+y_k^2} \end{align} Deriving and squarring yields

\begin{align} &\dot{r}_1(k)+\dot{r}_2(k)=\frac{2\dot{x}x_k+2\dot{y}y_k}{\sqrt{a^2+x_k^2+y_k^2}} \\ \iff& z_k^2=\frac{(2\dot{x}x_k+2\dot{y}y_k)^2}{a^2+x_k^2+y_k^2} \end{align}

My idea is, instead of minimizing the least square criterion $$C(\mathbf{x})=\sum^{N}_{k=1}(z_k-\dot{r}_1(\mathbf{x},k)+\dot{r}_2(\mathbf{x},k))^2$$ with the gauss-newton algorithm, which I can't manage to do succesfuly because of the non-convexity, I would like to find the roots of the (or the global minimizer of the squared-) system of polynomials in $\mathbf{x}$ :

$$(2\dot{x}x_k+2\dot{y}y_k)^2-z_k^2(a^2+x_k^2+y_k^2)=0$$

Finally my question is : Is this a good strategy to bypass the non-convexity of the original problem, and if it is, how do i proceed to find the roots of the polynomial system OR the global minimizer knowing that I don't want to use algorithms that are too computational intensive ?

• The system is overdetermined and will have no solution unless somehow your measurements $z_k$ have no noise whatsoever; even then finding roots of systems of polynomial equations is not a computationally easy problem. I would focus instead on how to find a better initial guess for your Newton solve. – user7530 Jun 12 '15 at 15:51
• what if i sqare the last equation and try to minimize it ? I'm just interested in the global optima. Is there realy no efficient methods to optimize a polynomial cost function ? – Antoine Bassoul Jun 12 '15 at 19:41