forum.alglib.net

ALGLIB forum
It is currently Sun Nov 10, 2024 5:44 am

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 2 posts ] 
Author Message
 Post subject: Computation of Jacobian and Hessian using Finite Differences
PostPosted: Wed Feb 15, 2023 7:22 pm 
Offline

Joined: Wed Feb 15, 2023 7:05 pm
Posts: 1
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


Top
 Profile  
 
 Post subject: Re: Computation of Jacobian and Hessian using Finite Differe
PostPosted: Thu Feb 16, 2023 9:10 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 925
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 2 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group