Re: Multivariate minimization

[Fabrice Rossi <rossi at ufrmd dot dauphine dot fr>]

Hi Przem

The vector BFGS is indeed one of the best methods for high dimensions. 
The current implementation is basic but should work. I've used it for 
neural network learning with more than 2000 parameters.

Concerning the Hessian matrix, the problem with the vector BFGS is that 
(as implied by the name) it does not manipulate a matrix (in the BFGS, 
the matrix is an approximation of the inverse of the Hessian). The way 
this is done is simply to replace the matrix of the full BFGS by the 
identity matrix, which is not what you are looking for, I guess ;-) Byt 
the way, the name vector BFGS is my invention. The canonical name is 
limited memory BFGS.

Implementing a full BFGS is not that difficult, especially if you start 
with the vector BFGS code. BUT the running cost will become tremendous 
as vector operations will be replaced by matrix operations. Moreover, 
you will end up with an approximation of the inverse of the hessian.

Did you try a very simple numerical approximation of the Hessian by 
finite difference? This is easy to program and with smooth functions, it 
works rather well (mainly because you know the exact value of the gradient).

Good luck.

Fabrice

Przemyslaw Sliwa wrote:
> Dear friends,
>
> I have some questions regarding the multivariate minimisation routines.
> I have t0 minimise a highly non-linear function depending on several
> variables (about 5000). I want to use the vector BFGS method because I
> have heard it is the best method for high dimensions. Is it correct???
>
> Secondly I have some design problems. The direction matrix in the BFGS
> method is an approximation of the Hessian matrix (matrix of second
> derivatives). At the optimum this approximation equals to the true
> Hessian. I am using the routine to maximise the loglikelihood function and
> I have to approximate the Hessisn, which is a task of estimating 12502500
> distinct elements of the Hessian. Therefore I would like to ask if it is
> not possible to return somehow the approximation of the Hessian at the end
> of the optimisation procedure?? This would save a lot of time and energy.
>
> The NAG procedures have an option which allows the user to return the
> approximation of the Hessian.
>
> My problem is that the estimation at the end of the optimisation is
> sometimes not positive (negative when minimising) definite due to the
> numerical accuracy. The BFGS method uses an approximation which is always
> positive definite.
>
> Thanks four your help,
>
> Przem