0

I have $N$ unknown 2D points ${\bf x} = (x,y)$ and I want to minimize:

$f({\bf x}) = \sum_{i=0}^{N-1}{(||x_{i+1} - x_i||_2 - c_i)^2}$

where c are $N-1$ known scalars. What is the simplest form that I can use to solve this? I was thinking to try to express it as a quadratic programming problem by solving for the homogeneous coordinates of the points, and in the end divide by the $3^{rd}$ coordinate:

${\bf x}^TQ{\bf x} + {\bf c}^T{\bf x}$

where ${\bf x}$ is now a $3N\times 1$ vector. The reason the minimization expands to quadratic polynomials with two variables, in the form $ax^2+bxy+cy^2+dx+ey+f$, where $b=0$.

Would this work? If yes, is there any tricky bit that I should be aware of?

Babis
  • 517
  • 1
  • 4
  • 10
  • I don't understand the problem, you are choosing an order for the $x_i$ so that the sum is minimised? – muzzlator Mar 20 '13 at 11:33
  • what do you mean by order? I don't know either $x_i$ or $y_i$ $\forall i \in [1,N]$. I want to calculate them so they minimize the mean squared error of the length differences to some known lengths $c_i$ (ok correcting this bit, my bad) – Babis Mar 20 '13 at 11:42
  • Maybe I do not understand it, but the equation to make the cost functional zero would be $|x_{i+1}-x_{i}|=c_{i}\ \forall i\in{0,\ldots,n-1}$...Now you can think about if it is possible to choose the $x_{i}$ such that the condition is fulfilled. – Alex Mar 20 '13 at 11:47
  • It's as you say, but I actually want to solve it in a least-squares sense, as in my case there is no solution which makes the functional zero. – Babis Mar 20 '13 at 11:50
  • Oh the question has changed, before the $c_i$ were just floating around without a square. It's interesting, I am currently working on the continuous version of this problem – muzzlator Mar 20 '13 at 11:51
  • If you change your functional to $f(x)=\sum_{i=0}^{N-1}\left(|x_{i+1}-x_{i}|^{2}{2}-c{i}^{2}\right)$ it is certainly quadratic...and should do what you want to... – Alex Mar 20 '13 at 12:28

0 Answers0