Geometrics contraints solving with BFGS

Question

I want to use the BFGS method for geometrics constraints solving.

My problem is not about the functioning of the BFGS: I have tested several functions and it's ok, it finds the minimum of the function after a certain number of iterations.

My problem is how to adapt my geometric equations problems to the BFGS.

For example, if I have this problem:

Triangle Example

I have 3 circles equations to define my triangle: $$ f1 = (P2x -P1x)^2 + (P2y-P1y)^2 - 200^2 = 0$$ $$ f2 = (P3x -P2x)^2 + (P3y-P2y)^2 - 300^2 = 0$$ $$ f3 = (P3x -P1x)^2 + (P3y-P1y)^2 - 250² = 0$$

Consider that $P1$ is fixed $(100,100)$ and $P2y = P1y = 100$ (horizontal constraint).

We have 3 unknown variables ($P2x$, $P3x$ , and $P3y$) and 3 equations.

If I use the notation $X_1,\ldots,X_n$, I have: $$ f_1(X) = (X_1 -100)^2 + (100-100)^2 - 200^2 = 0$$ $$ f_2(X) = (X_2 -X_1)^2 + (X_3-100)^2 - 300^2 = 0$$ $$ f_3(X)= (X_2 -100)^2 + (X_3-100)^2 - 250^2 = 0$$

My objective is to get the values of $X_1$, $X_2$, and $X_3$ with BFGS.

If I consider the function $F(X)$ like the sum of $f_1(X)$ , $f_2(X)$ and $f_3(X)$, the BFGS algorithm return to me the values such as the gradient of $F(X)$ is equal to $0$ (minimum of the function). $(100, 100, 100)$ in this case.

But what I want is the roots of $F(X)$ and not the minimum.

I have also seen the technique of summing the squares of functions to define $F(X)$, like this:

\begin{align} f_1(x_1,\ldots,x_n) &= 0 \\ f_2(x_1,\ldots,x_n) &= 0 \\ \vdots\;\;\;\;&\\ f_{m-1}(x_1,\ldots,x_n) &= 0 \\ f_m(x_1,\ldots,x_n) &= 0 \\ F(\vec{X}) &= \sum_{i=1}^m f_i^2 \end{align}

But it does not seems to work.

Would anybody have an idea of what I have to do ?

Thanks in advance

Answer 1

It is indeed possible to look for the zeros of a function $$ F(\vec{x})=\sum_i f_i(\vec{x}) $$ with an optimization algorithm, by minimizing $$ E(\vec{x})=\sum_i f_i(\vec{x})^2 $$ Clearly, $E\geq0$ by definition, and $E=0$ iff $f_i(\vec{x})=0\;\forall\; i$.

Some things to remember:

• Some algorithms (e.g. BFGS) can get stuck in local minima. Hence the initial values may matter.
• Looking to minimize $F$ directly may not work, since some of the $f_i$ may be negative and cancel each other out!
• There do exist algorithms specialized for root finding, but (as the asker noted) using optimization may be better in some cases (e.g. returning an approximate answer).