Thread Subject:

How to compute gradient to give to fminunc?

Hello!
I've read many times about fminunc and how it needs a gradient to work optimally and to use the large-scale algorithm.
How can I find it?
I mean... If I have to minimize an analytical function I can compute analytically the gradient and that's no problem.
What about a function where I can't find an analytical expression for the gradient??
i.e.: image registration.

Is there a way to compute the gradient efficiently? I would say no, and therefore that the only feasible option is to let fminunc compute it using finite differences.

Am I getting it right??

Since you also had to calculate the gradient using a finite difference
approximation, you can also let FMINUNC do it for you.
So - yes, you got it right.

Best wishes
Torsten.

"Luca " <l.presottoRE@MOVE.campus.unimib.NOTit> wrote in message <js1tlf$m4c$1@newscl01ah.mathworks.com>...
> Hello!
> I've read many times about fminunc and how it needs a gradient to work optimally and to use the large-scale algorithm.
> How can I find it?
> I mean... If I have to minimize an analytical function I can compute analytically the gradient and that's no problem.
> What about a function where I can't find an analytical expression for the gradient??
> i.e.: image registration.
===============

There's no reason most image registration cost functions wouldn't have an analytical expression for the gradient. However, you have to use a differentiable resampler, unlike in previous threads where you were using linear interpolation resampling. If you use spline interpolation, this tool would probably help you get its derivatives

http://www.mathworks.com/matlabcentral/fileexchange/24996-spline-derivative

There's also no reason why the gradient calculation has to be a 1-line expression, if that's what you were worried about. A derivative calculation can be given by a process, implemented in an mfile. FMINUNC only cares that given an x, it can call a function to obtain grad(x).

"Matt J" wrote in message <js1vov$2kc$1@newscl01ah.mathworks.com>...

> There's no reason most image registration cost functions wouldn't have an analytical expression for the gradient. However, you have to use a differentiable resampler, unlike in previous threads where you were using linear interpolation resampling. If you use spline interpolation, this tool would probably help you get its derivatives
>
> http://www.mathworks.com/matlabcentral/fileexchange/24996-spline-derivative
=========
Ok. I'm not working with image registration now but that's not the point.
Anyway you gave me a good idea to calculate _part_ of the gradient of my objective function analitically. My objective function is the sum of two different terms. A true objective function and a penalty function on the parameters. The gradient of penalty function can be written analitically in one line and is extremely simple and easy to compute.

Now for the difficult part. I need to fit a function to some points using squared difference as the objective function. Is it possible to derive the gradient analitically? I would say no. Am I right?? (my function is a gaussian with 3 free parameters, amplitude, sigma and center. How can I compute analitically d(SD(gaussian,targetPoint))/d(PAR) ?).
In any case... Thanks to your answer I got an idea also here. Due to a peculiarity of my problem I can compute the gradient of my objective function with finite differences much more efficiently than fminunc.
To make it simple I have let's just say that I have thousands of parameters and a very large 3d matrix. But each 3 parameters describe only a line of this matrix. Therefore if I have to compute the finite difference on par(1:3) I can compute it only on Values(:,1,1);

"Luca " <l.presottoRE@MOVE.campus.unimib.NOTit> wrote in message <js22kq$g0d$1@newscl01ah.mathworks.com>...
>
>
> Now for the difficult part. I need to fit a function to some points using squared difference as the objective function. Is it possible to derive the gradient analitically? I would say no. Am I right?? (my function is a gaussian with 3 free parameters, amplitude, sigma and center. How can I compute analitically d(SD(gaussian,targetPoint))/d(PAR) ?).
===============

No, you're not right. The gradient calculation looks very easy, especially if it's Gaussian fitting. The derivative of a Gaussian with respect to its mean, for example, is

-(x-mu)*exp(-(x-mu)^2/2)

Everything else you need to compute the derivative of the overall function follows very simply from the chain rule. More generally, the gradient of the general form
norm(err(x))^2 is 2*Gradient(err(x))*err(x)

 

"Matt J" wrote in message <js23bb$j1b$1@newscl01ah.mathworks.com>...

> Everything else you need to compute the derivative of the overall function follows very simply from the chain rule. More generally, the gradient of the general form
> norm(err(x))^2 is 2*Gradient(err(x))*err(x)

Blimey, you were right! It seemed so impossible to me at the beginning, it's very counterintuitive. But I get quite an easy expression actually.
That will speed up my code a lot! First thing I will implement on monday.