forum.alglib.net

Hello,

I am writing you because I would like to know more about how the computation of the Jacobian and Hessian matrix is done by alglib when the user doesn't specify analytical expressions for them when using an LM optimizer for example. I have used the library's minlm subpackage and I have noticed that it doesn't take much time at each iteration to compute both these matrices for a function that is rather costly to evaluate. If I were to reimplement the finite difference approximations, I would need at least N function evaluations for the Jacobian and N + N^2/2 function evaluations for the Hessian.

I have tried to look a closer look at the library's code but quite frankly couldn't figure out how the finite difference approximations are carried with such efficiency. Nevertheless, I have stumbled upon one function's (minlmsetacctype) comment that may steer me in the right direction :

"AccType=1 is recommended when Jacobian calculation cost is prohibitive
high (several Mx1 function vector calculations followed by several NxN
Cholesky factorizations are faster than calculation of one M*N Jacobian).
It should also be used when we have no Jacobian, because finite difference
approximation takes too much time to compute."

It seems here that Cholesky factorizations are used to compute the Jacobian in a faster way. Can someone please explain to me how it is done ?
And what about the Hessian ? Is it an approximation à la BFGS that is used to update it at each step ?

I greatly appreciate your help and thank you in advance for your response,
Kind regards

Hi!

It is called secant updates of the quadratic model.

You can google "levenberg marquardt secant updates" for a detailed explanation, but shortly speaking - after computing step with finite differences Jacobian, the solver tries to perform cheap update of the internally stored Jacobian using information obtained from the step. This update needs just one function vector evaluation, not N, so it is really cheap. On the other hand, it is definitely imprecise, and updated Jacobian quickly becomes irrelevant, so after several steps the solver recomputes Jacobian from scratch anyway.