3
$\begingroup$

I am trying to implement a Gauss-Newton algorithm for non-linear optimisation. Unfortunately despite searching through the library and the internet I can't figure out quite how to use it in my case. As such I am hoping that I have come to the right place to ask for some assistance? Thank you to anyone willing to help me.

My problem consists of minimising a function $f(\vec x)$ where $\mathbb R^n \ni \vec x = (x_1, \dots ,x_n)$ and $f:\mathbb R^n\rightarrow \mathbb R$. Physically $f$ is a chi squared value $f=y-e(\vec x)$ where $y$ is the target value and $e(\vec x)$ is the test function evaluated at guess $\vec x$.

I begin by computing $f(\vec x+\delta \vec x)$ and $f(\vec x)$. Here $\vec x+\delta \vec x=x_1+\delta x_1,\dots , x_n+\delta x_n$. I then evaluate numerical derivatives using the following quotient formula, \begin{equation} \frac{\partial f(\vec x)}{\partial x_i} = \frac{f(x_1,\dots , x_i+\delta x_i,\dots ,x_n)-f(\vec x)}{\delta x_i}\qquad \forall i =1,\dots ,n \end{equation} I must then combine this into the Jacobian $\vec J$, \begin{equation} \vec J = \bigg(\frac{\partial f(\vec x)}{\partial x_1}\ \frac{\partial f(\vec x)}{\partial x_2} \cdots \frac{\partial f(\vec x)}{\partial x_n}\bigg) \end{equation} I can take the transpose of $\vec J$ denoted $\vec J^T$.

So far I can code the above (in C++). However The next part becomes confusing for me personally. In particular I do not know how to write the following matrix equation. \begin{equation} (\vec J \vec J^T)\delta \vec x = \vec Jf \end{equation} In fact I am not certain that this is the correct procedure?

Therefore, with numerical derivatives in place how can I obtain $\delta \vec x$ for the next iteration of the descent? Again many thanks for your time.

$\endgroup$
5
  • 1
    $\begingroup$ More suitable for scicomp.stackexchange.com ? $\endgroup$ Mar 22, 2016 at 21:21
  • $\begingroup$ @AntonTrunov I think so, yes. The question seems to be principally about implementation, which is off-topic, here. $\endgroup$ Mar 22, 2016 at 23:20
  • 1
    $\begingroup$ I think this is fine and on-topic here. We don't migrate questions that are on-topic here (even if it might be a slightly better fit on another site, we don't migrate it -- the poster chose where they want to post it, and if it's on-topic here, we don't migrate it against their will -- we only consider migrating if it is off-topic here). So it's fine for this to stay here. $\endgroup$
    – D.W.
    Mar 23, 2016 at 4:54
  • $\begingroup$ Maybe this would be on-topic and well received for Mathematics as well. $\endgroup$
    – Juho
    Apr 5, 2016 at 17:52
  • $\begingroup$ Do you really mean Gauss-Newton? Gauss-Newton is for minimizing sums of squares, but I can't see any evidence that your $f(x)$ has the form of sum of squares. $\endgroup$
    – D.W.
    Jul 3, 2017 at 15:03

1 Answer 1

2
$\begingroup$

Solve the equation multiplying both terms of the equation for the inverse of the hessian matrix $\vec{J} \vec{J}^T$ on the left side:

$$ \delta \vec{x} = (\vec{J} \vec{J}^T)^{-1} \cdot \vec{J}f $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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