1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Firstly, please use mathjax for mathematical formatting. Second, if you want the roots, why dont you use a root finding algorithm (like Newton-Raphson). E.g. here. BFGS is a minimization algorithm which uses the gradient to find when a function stops decreasing, so it's not surprising it returns the minimum. $\endgroup$ – user3658307 Aug 22 '17 at 5:33
  • $\begingroup$ Thanks for your answer. As Newton-Raphson, BFGS can be used to resolve systems of equations, with the avantage of returning a solution even if there are not the same number of variables as equations. $\endgroup$ – Léo Aug 23 '17 at 8:46
  • $\begingroup$ There is examples in this document: Here (pages 2 and 3) $\endgroup$ – Léo Aug 23 '17 at 8:46
  • $\begingroup$ Certainly. However, it is still an optimization algorithm at heart. Hence, it can get stuck in local minima (e.g. sec 2.7 in the paper you link), which perhaps may be worth remembering. Did you try different initializations e.g. random restarts? What happens exactly with the $\sum_i f_i^2$ approach? Also, notice that at $(100,100,100)$ your energy appears to be negative, meaning way better than zero as far as the algorithm is concerned. So why should it stop at zero? It wants the minimum. The $\sum_i f_i^2$ approach handles this particular problem but you dont say what the problem is. $\endgroup$ – user3658307 Aug 23 '17 at 14:35
  • $\begingroup$ Thank you for taking the time to look at my problem. If I consider the function F as the sum of the functions (F = f1 + f2 + … + fn), the result X* will always be the same (100;100;100 in the example above), regardless of the initial values of X. It’s normal because it’s the only solution that cancels the gradient. I’m agree with you that the 'sum of squares' approach seems to be the good way to find roots of the system and not just to minimize it. My problem with this approach is that my X* result grows exponentially at each iteration and not converge towards a solution. $\endgroup$ – Léo Aug 26 '17 at 9:39
0
$\begingroup$

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).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.