cvanaret
[WIP] L-BFGS approximation
Support for L-BFGS.
Limited memory quasi-Newton Hessian approximations will be computed based on the compact QN representation (see Numerical optimization by Nocedal & Wright, pp 181-184). The availability of quasi-Newton approximations will be conditional on the presence of LAPACK.
@worc4021
Do you envisage to flesh out the bodies of the algorithm in this PR as well? When I tried to use BFGS with uno last, I found that one of the callbacks to update representations wasn't being called when I thought it would be and it led to a little bit of chaos. Having not retried it with this candidate I believe that it was around notify_new_primals. In the context of quasi Newton updating we need to distinguish between two types of decision variables we call the Hessian computations with:
- accepted primals, these should be committed to the internal storages of S and Y in
LBFGSHessian.hpp, however, there are also trial candidates which do not enter the accepted S and Y - trial primals, when a candidate point is being evaluated in whatever subsolver method, if the Hessian is requested for it, it should be used in the computation of the return value, however these should not automatically be in S or Y (since s=x-xprevious, so you'd need to keep xprevious anyway to be updating the last column)
When I implement the operations for quasi Newton updates, I usually do not store S and Y but rather use some circular fifo type store and store [x(k-m-1),x(k-m),...,x(k-1),xc] where x(i) is the accepted iterate at i and xc denotes the current trial point (analogous for the derivatives). When the Hessian callback is called, only then do I compute S with those m+1 values and always get the current best approximate. This strategy works well for interior point methods (verified in knitro and ipopt), I'm not sure to what extent this would need to be adapted to deal with sequential programming where there are inner and outer steps etc. Likely, that you will encounter all this in your testing and have to address it already.
Hi @worc4021,
I have added a function notify_accepted_iterate(current_iterate, trial_iterate) that propagates the current iterate and the accepted trial iterate from the ConstraintRelaxationStrategy to the HessianModel; see here.
This allows me to update the QN memory only with the accepted iterates (your first bullet point) and to compute the deltas at iterations $k-1$ and $k$ without storing the iterates themselves.
I agree that, as is, the user callbacks are not ideal to build your own QN update (however I do believe they're called at the right places). Let's see how easy things are with the HessianModel approach.
Your approach of adding the trial iterate xc ``on the fly'' to the memory is interesting. I think I'll add an option to Uno to switch between the traditional approach ($m$ accepted iterates in memory) and your approach ($m$ accepted iterates + the trial iterate).
Hey Charlie, if LBGFS is ready for testing, even if it's not production-ready, we have some black-box cases that we can run. If it is ready, is it in the 2.3 binaries, or shall I wait a bit longer? No rush.
Hi @damienhocking, I'm not quite there yet, but finishing L-BFGS (at least for SQP methods) is at the top of my to-do list. Give me a few weeks, I'll be in touch :)