forum.alglib.net

ALGLIB forum
 It is currently Tue Aug 13, 2024 11:56 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.

 Page 1 of 1 [ 2 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Computation of Jacobian and Hessian using Finite DifferencesPosted: Wed Feb 15, 2023 7:22 pm

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 ?

Kind regards

Top

 Post subject: Re: Computation of Jacobian and Hessian using Finite DifferePosted: Thu Feb 16, 2023 9:10 pm

Joined: Fri May 07, 2010 7:06 am
Posts: 922
Hi!

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 2 posts ]

 All times are UTC

Who is online

Users browsing this forum: No registered users and 102 guests

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

Search for: