forum.alglib.net

ALGLIB forum
It is currently Thu Mar 28, 2024 6:04 pm

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: Levenberg-Marquardt performance scaling
PostPosted: Wed Mar 06, 2013 10:38 am 
Offline

Joined: Wed Mar 06, 2013 9:25 am
Posts: 1
Hi,

I've been using ALGLIB's Levenberg-Marquardt implementation (VJ mode, no acceleration, reusing state) for bounded non-linear optimisation, but it seems that the performance scales really badly. Example timings:

problem size: 360 unknowns and 427 squared sums
objective function total time (for all evaluations of the objective function and jacobian) : 0.485 secs
minlmoptimize total time: 8.836 secs

problem size: 144 unknowns and 169 squared sums
objective function total time (for all evaluations of the objective function and jacobian) : 0.1 secs
minlmoptimize total time: 0.745 secs

problem size: 40 unknowns and 55 squared sums
objective function total time (for all evaluations of the objective function and jacobian) : 0.048
minlmoptimize total time: 0.1 secs


So in the last case, total time is 2x total objective function time.
For the case before, it's 7x.
For my slowest case, total evaluation time is 18x the total objective function time.
I've tried it with same squared sums but less unknowns, and the performance is significantly better.

I'm using all tolerances equal to zero, as I was trying to get the best results possible as parts of my calculations are done in floating point precision.
Is there any quick hint to increase performance? Is there any chance that I can get much better performance with large problems? If I can only use tolerances, which ones would be suggested for such large problems?

Thanks,
Babis


Top
 Profile  
 
 Post subject: Re: Levenberg-Marquardt performance scaling
PostPosted: Wed Mar 06, 2013 12:52 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
Levenberg-Marquardt scales badly when number of unknowns increases. Iteration cost is proportional to O(M*N^2), where N is for unknowns, and M is for squared sums. I have several ideas about algorithm improvement, but it is impossible to prevent growth of iteration cost.


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 48 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