Thread Subject: How to use optimset for fminsearch to run Levenberg-Marquardt instead of Nelder-Mead?

Dear All,

I have searched the newsgroup for "fminsearch optimset" with combinations on "Levenberg-Marquardt" but I am still not finding what I am looking for. I hope you can help.

Question: I am suspecting that fminsearch cannot be changed to use any other optimization algorithm than Nelder-Mead and that my changes to the optimset argument are simply ignored. Is this true? If not, any suggestions on how I can change fminsearch to work with Levenberg-Marquardt? Alternatively, what other Matlab function would be appropriate for this task?

Application: I am trying to estimate a projection matrix and I want to use fminsearch to find the optimal parameters to minimize the reprojection error, i.e. the screen distance between some ground truth markers projected on the screen and some additional test markers also projected to the screen.

My code, using Matlab 7.3.0.298 (R2006b) on Ubuntu Dapper Drake, looks like this:

% Here I try to change the fminsearch's default optimiser from Nelder-Mead to Levenberg-Marquardt and also make it run for a little longer
options = optimset('MaxFunEvals', 10000, 'MaxIter', 10000);
options = optimset(options, 'LevenbergMarquardt, 'on');

% Here I call fminsearch with a function handle to the function that calculates an error, an array of parameter estimates that are to be changed such that the error returned by the function in the function handle is minimized. This error is reported back to errval, and I can also see if the optimizer terminated prematurely in flag. The output data structure also gives me further information.
[estimates errval flag output] = fminsearch(@psuedoHuberCostFunction, [rx ry rz tx ty tz fx fy px py], options);

Observations:

1. The code as written here above runs, but the output.algorithm, which indicates which algorithm that was used, says that Nelder Mead was used.
2. If I change the call to optimset to any other string than 'LevenbergMarquardt', this results in an error.

Motivation: I want to see if Levenberg-Marquardt with its adaptable step length can deal with a more complex parameter surface compared to Nelder-Mead and therefore is a better choice for camera calibrations with some alignment noise between correspondence points.

Thanks for your time and help.

Magnus

Update:

Following a recommendation of a colleague I tried the fminsearch on an identical set of data for the two cases when optimset was set to use Nelder-Mead (NM) and when it was set to Levenberg-Marquardt (LM). The output shows that in the NM case the optimizer never finishes but quits with flag 0 after 1406 iterations. In the LM case the optimizer quite successfully with flag 1 with 2241 iterations.

This would imply that the optimset argument does make a difference but that the algorithm field in the output structure still reads "Nelder-mead simplex direct search" even if it in fact is using LM.

/M.



"Magnus " <magax@itn.liu.se> wrote in message <hcbn39$k4a$1@fred.mathworks.com>...
> Dear All,
>
> I have searched the newsgroup for "fminsearch optimset" with combinations on "Levenberg-Marquardt" but I am still not finding what I am looking for. I hope you can help.
>
> Question: I am suspecting that fminsearch cannot be changed to use any other optimization algorithm than Nelder-Mead and that my changes to the optimset argument are simply ignored. Is this true? If not, any suggestions on how I can change fminsearch to work with Levenberg-Marquardt? Alternatively, what other Matlab function would be appropriate for this task?
>
> Application: I am trying to estimate a projection matrix and I want to use fminsearch to find the optimal parameters to minimize the reprojection error, i.e. the screen distance between some ground truth markers projected on the screen and some additional test markers also projected to the screen.
>
> My code, using Matlab 7.3.0.298 (R2006b) on Ubuntu Dapper Drake, looks like this:
>
> % Here I try to change the fminsearch's default optimiser from Nelder-Mead to Levenberg-Marquardt and also make it run for a little longer
> options = optimset('MaxFunEvals', 10000, 'MaxIter', 10000);
> options = optimset(options, 'LevenbergMarquardt, 'on');
>
> % Here I call fminsearch with a function handle to the function that calculates an error, an array of parameter estimates that are to be changed such that the error returned by the function in the function handle is minimized. This error is reported back to errval, and I can also see if the optimizer terminated prematurely in flag. The output data structure also gives me further information.
> [estimates errval flag output] = fminsearch(@psuedoHuberCostFunction, [rx ry rz tx ty tz fx fy px py], options);
>
> Observations:
>
> 1. The code as written here above runs, but the output.algorithm, which indicates which algorithm that was used, says that Nelder Mead was used.
> 2. If I change the call to optimset to any other string than 'LevenbergMarquardt', this results in an error.
>
> Motivation: I want to see if Levenberg-Marquardt with its adaptable step length can deal with a more complex parameter surface compared to Nelder-Mead and therefore is a better choice for camera calibrations with some alignment noise between correspondence points.
>
> Thanks for your time and help.
>
> Magnus

Update:

In the little test I mentioned previously I tried to determine if fminsearch could use Levenberg-Marquardt instead of Nelder-Mead. I did this by including and excluding the following options as argument to the fminsearch.

options = optimset('MaxFunEvals', 10000, 'MaxIter', 10000);
options = optimset(options, 'LevenbergMarquardt, 'on')

I found that without these options fminsearch quite prematurely with flag 0 after approx 1400 iterations but with the options included fminsearch completed after some 2000 iterations. Because the results were different I prematurely concluded that Levenberg-Marquardt was used instead of Nelder-Mead. This is not the case as I was wrong on two accounts:

Firstly, by looking in the fminsearch.m code I can see that: a) Line 78: The default number of MaxIter and MaxFunEvals is 200*numberOfVariables, b) Line 111-112: numberOfVariables is defined as the number of elements in the parameter array.

The reason why fminsearch quit prematurely at 1400 iterations was not because of a different optimization algorithm but because the MaxFunEvals had been exceeded. MaxFunEvals is not called once for every iteration, thus it was larger than numberOfVariables * 200, which in my case with 10 parameters is 2000.

Secondly, in changing the options to use the Levenberg-Marquardt algorithm I also allowed for more iterations and more function evaluations. It is the change in these variables that cause the fminsearch to eventually reach a minima.

This is further supported by c) Line 417: Only here is ouput.algorithm set to any value that would specify if any other algorithm is used.

Conclusion: fminsearch only uses Nelder-Mead and ignores 'LevenbergMarquardt', 'on' in the optimset input argument. No warning or error is given.

/M.

"Magnus " <magax@itn.liu.se> wrote in message <hcc19l$neo$1@fred.mathworks.com>...
> Update:
>
> Following a recommendation of a colleague I tried the fminsearch on an identical set of data for the two cases when optimset was set to use Nelder-Mead (NM) and when it was set to Levenberg-Marquardt (LM). The output shows that in the NM case the optimizer never finishes but quits with flag 0 after 1406 iterations. In the LM case the optimizer quite successfully with flag 1 with 2241 iterations.
>
> This would imply that the optimset argument does make a difference but that the algorithm field in the output structure still reads "Nelder-mead simplex direct search" even if it in fact is using LM.
>
> /M.
>
>
>
> "Magnus " <magax@itn.liu.se> wrote in message <hcbn39$k4a$1@fred.mathworks.com>...
> > Dear All,
> >
> > I have searched the newsgroup for "fminsearch optimset" with combinations on "Levenberg-Marquardt" but I am still not finding what I am looking for. I hope you can help.
> >
> > Question: I am suspecting that fminsearch cannot be changed to use any other optimization algorithm than Nelder-Mead and that my changes to the optimset argument are simply ignored. Is this true? If not, any suggestions on how I can change fminsearch to work with Levenberg-Marquardt? Alternatively, what other Matlab function would be appropriate for this task?
> >
> > Application: I am trying to estimate a projection matrix and I want to use fminsearch to find the optimal parameters to minimize the reprojection error, i.e. the screen distance between some ground truth markers projected on the screen and some additional test markers also projected to the screen.
> >
> > My code, using Matlab 7.3.0.298 (R2006b) on Ubuntu Dapper Drake, looks like this:
> >
> > % Here I try to change the fminsearch's default optimiser from Nelder-Mead to Levenberg-Marquardt and also make it run for a little longer
> > options = optimset('MaxFunEvals', 10000, 'MaxIter', 10000);
> > options = optimset(options, 'LevenbergMarquardt, 'on');
> >
> > % Here I call fminsearch with a function handle to the function that calculates an error, an array of parameter estimates that are to be changed such that the error returned by the function in the function handle is minimized. This error is reported back to errval, and I can also see if the optimizer terminated prematurely in flag. The output data structure also gives me further information.
> > [estimates errval flag output] = fminsearch(@psuedoHuberCostFunction, [rx ry rz tx ty tz fx fy px py], options);
> >
> > Observations:
> >
> > 1. The code as written here above runs, but the output.algorithm, which indicates which algorithm that was used, says that Nelder Mead was used.
> > 2. If I change the call to optimset to any other string than 'LevenbergMarquardt', this results in an error.
> >
> > Motivation: I want to see if Levenberg-Marquardt with its adaptable step length can deal with a more complex parameter surface compared to Nelder-Mead and therefore is a better choice for camera calibrations with some alignment noise between correspondence points.
> >
> > Thanks for your time and help.
> >
> > Magnus

"Magnus " <magax@itn.liu.se> wrote in message <hccahp$d2b$1@fred.mathworks.com>...
> Update:
>
> In the little test I mentioned previously I tried to determine if fminsearch could use Levenberg-Marquardt instead of Nelder-Mead. I did this by including and excluding the following options as argument to the fminsearch.
>
> options = optimset('MaxFunEvals', 10000, 'MaxIter', 10000);
> options = optimset(options, 'LevenbergMarquardt, 'on')
>
> I found that without these options fminsearch quite prematurely with flag 0 after approx 1400 iterations but with the options included fminsearch completed after some 2000 iterations. Because the results were different I prematurely concluded that Levenberg-Marquardt was used instead of Nelder-Mead. This is not the case as I was wrong on two accounts:
>
> Firstly, by looking in the fminsearch.m code I can see that: a) Line 78: The default number of MaxIter and MaxFunEvals is 200*numberOfVariables, b) Line 111-112: numberOfVariables is defined as the number of elements in the parameter array.
>
> The reason why fminsearch quit prematurely at 1400 iterations was not because of a different optimization algorithm but because the MaxFunEvals had been exceeded. MaxFunEvals is not called once for every iteration, thus it was larger than numberOfVariables * 200, which in my case with 10 parameters is 2000.
>
> Secondly, in changing the options to use the Levenberg-Marquardt algorithm I also allowed for more iterations and more function evaluations. It is the change in these variables that cause the fminsearch to eventually reach a minima.
>
> This is further supported by c) Line 417: Only here is ouput.algorithm set to any value that would specify if any other algorithm is used.
>
> Conclusion: fminsearch only uses Nelder-Mead and ignores 'LevenbergMarquardt', 'on' in the optimset input argument. No warning or error is given.

There is no reason to assume that fminsearch will use
a wildly different algorithm that has not been coded
into it. Fminsearch is a Nelder/Mead optimizer, to
minimize a general function. LM is a method that is
specifically for nonlinear least squares problems.

In fact, there is no reason for fminsearch to even test
to see if you have set some parameters that it will never
look at. In fact, it does not do so.

John

"Magnus " <magax@itn.liu.se> wrote in message
news:hccahp$d2b$1@fred.mathworks.com...

*snip*

> Conclusion: fminsearch only uses Nelder-Mead and ignores
> 'LevenbergMarquardt', 'on' in the optimset input argument. No warning or
> error is given.

That's correct. The reference page for FMINSEARCH lists the options it uses
in the Options section:

http://www.mathworks.com/access/helpdesk/help/toolbox/optim/ug/fminsearch.html

as does this section of the Optimization Toolbox documentation:

http://www.mathworks.com/access/helpdesk/help/toolbox/optim/ug/f19175.html

and the documentation for the optimization functions included as part of
MATLAB itself:

http://www.mathworks.com/access/helpdesk/help/techdoc/math/f2-14970.html#f2-23135

None of these places indicate that FMINSEARCH uses the LevenbergMarquardt
option, so it doesn't.

I predict that your next question will be why it doesn't error or warn if
you pass it an option that it doesn't use -- to that I echo John's comment
at the end of his post, and also offer an additional suggestion. Suppose
you were comparing the behavior of two of the optimizers, one of which uses
an option that the other does not, and you want to perform as close to an
apples-to-apples comparison as you can. In order to do so, you may pass the
same options structure into both optimizers and let each use only the
options it wants to use.

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ

John, Steven,

Thank you for your answers. Now I understand how this works. Before I looked "under the hood" of fminsearch I was under the impression that you could tell fminsearch to work with various solvers through the algorithm field in the optimset structure. Now I realize that I should have read the first table, last column, on this page more carefully as it describes the mapping between solver and optimset fields: http://www.mathworks.com/access/helpdesk/help/toolbox/optim/index.html?/access/helpdesk/help/toolbox/optim/ug/f19175.html

I can see how it could seem to be a "wild" assumption trying to pull a screwdriver out of a bread knife thinking its a Swiss army knife.

To conclude: Only parts of the optimset structure is applicable depending on which solver you are working with, and I see now that far from all optimset fields are applicable to all solvers. I get it now. Thanks for setting me on the right track.

/M.






"Steven Lord" <slord@mathworks.com> wrote in message <hcce1u$rug$1@fred.mathworks.com>...
>
> "Magnus " <magax@itn.liu.se> wrote in message
> news:hccahp$d2b$1@fred.mathworks.com...
>
> *snip*
>
> > Conclusion: fminsearch only uses Nelder-Mead and ignores
> > 'LevenbergMarquardt', 'on' in the optimset input argument. No warning or
> > error is given.
>
> That's correct. The reference page for FMINSEARCH lists the options it uses
> in the Options section:
>
> http://www.mathworks.com/access/helpdesk/help/toolbox/optim/ug/fminsearch.html
>
> as does this section of the Optimization Toolbox documentation:
>
> http://www.mathworks.com/access/helpdesk/help/toolbox/optim/ug/f19175.html
>
> and the documentation for the optimization functions included as part of
> MATLAB itself:
>
> http://www.mathworks.com/access/helpdesk/help/techdoc/math/f2-14970.html#f2-23135
>
> None of these places indicate that FMINSEARCH uses the LevenbergMarquardt
> option, so it doesn't.
>
> I predict that your next question will be why it doesn't error or warn if
> you pass it an option that it doesn't use -- to that I echo John's comment
> at the end of his post, and also offer an additional suggestion. Suppose
> you were comparing the behavior of two of the optimizers, one of which uses
> an option that the other does not, and you want to perform as close to an
> apples-to-apples comparison as you can. In order to do so, you may pass the
> same options structure into both optimizers and let each use only the
> options it wants to use.
>
> --
> Steve Lord
> slord@mathworks.com
> comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
>

Hi Magnus,
fminsearch is the implementation of Nelder-Mead simplex method only. Could
you confirm that by only changing an option (LevenbergMarquardt) that is not
applicable to fminsearch, you obtained a different result for your problem?
Your problem doesn't have any randomness, right?

Best Regards,
Derya

"Magnus " <magax@itn.liu.se> wrote in message
news:hcc19l$neo$1@fred.mathworks.com...
> Update:
>
> Following a recommendation of a colleague I tried the fminsearch on an
> identical set of data for the two cases when optimset was set to use
> Nelder-Mead (NM) and when it was set to Levenberg-Marquardt (LM). The
> output shows that in the NM case the optimizer never finishes but quits
> with flag 0 after 1406 iterations. In the LM case the optimizer quite
> successfully with flag 1 with 2241 iterations.
>
> This would imply that the optimset argument does make a difference but
> that the algorithm field in the output structure still reads "Nelder-mead
> simplex direct search" even if it in fact is using LM.
>
> /M.
>
>
>
> "Magnus " <magax@itn.liu.se> wrote in message
> <hcbn39$k4a$1@fred.mathworks.com>...
>> Dear All,
>>
>> I have searched the newsgroup for "fminsearch optimset" with combinations
>> on "Levenberg-Marquardt" but I am still not finding what I am looking
>> for. I hope you can help.
>>
>> Question: I am suspecting that fminsearch cannot be changed to use any
>> other optimization algorithm than Nelder-Mead and that my changes to the
>> optimset argument are simply ignored. Is this true? If not, any
>> suggestions on how I can change fminsearch to work with
>> Levenberg-Marquardt? Alternatively, what other Matlab function would be
>> appropriate for this task?
>>
>> Application: I am trying to estimate a projection matrix and I want to
>> use fminsearch to find the optimal parameters to minimize the
>> reprojection error, i.e. the screen distance between some ground truth
>> markers projected on the screen and some additional test markers also
>> projected to the screen.
>>
>> My code, using Matlab 7.3.0.298 (R2006b) on Ubuntu Dapper Drake, looks
>> like this:
>>
>> % Here I try to change the fminsearch's default optimiser from
>> Nelder-Mead to Levenberg-Marquardt and also make it run for a little
>> longer
>> options = optimset('MaxFunEvals', 10000, 'MaxIter', 10000);
>> options = optimset(options, 'LevenbergMarquardt, 'on');
>>
>> % Here I call fminsearch with a function handle to the function that
>> calculates an error, an array of parameter estimates that are to be
>> changed such that the error returned by the function in the function
>> handle is minimized. This error is reported back to errval, and I can
>> also see if the optimizer terminated prematurely in flag. The output data
>> structure also gives me further information.
>> [estimates errval flag output] = fminsearch(@psuedoHuberCostFunction, [rx
>> ry rz tx ty tz fx fy px py], options);
>>
>> Observations:
>>
>> 1. The code as written here above runs, but the output.algorithm, which
>> indicates which algorithm that was used, says that Nelder Mead was used.
>> 2. If I change the call to optimset to any other string than
>> 'LevenbergMarquardt', this results in an error.
>>
>> Motivation: I want to see if Levenberg-Marquardt with its adaptable step
>> length can deal with a more complex parameter surface compared to
>> Nelder-Mead and therefore is a better choice for camera calibrations with
>> some alignment noise between correspondence points.
>>
>> Thanks for your time and help.
>>
>> Magnus

Hi Derya.

You have answered to my original postings, but since then this topic has been answered by John and Steve.

http://www.mathworks.com/matlabcentral/newsreader/view_thread/264426

To conclude: It was my mistake as I misunderstood the use of optimset. You may disregard this entire post or, if anything, have a look at the links in the documentation Steve is referring to as I found them very useful.

Thanks for replying.

Magnus

"Derya Ozyurt" <dozyurt@mathworks.com> wrote in message <hcpt1i$h4h$1@fred.mathworks.com>...
> Hi Magnus,
> fminsearch is the implementation of Nelder-Mead simplex method only. Could
> you confirm that by only changing an option (LevenbergMarquardt) that is not
> applicable to fminsearch, you obtained a different result for your problem?
> Your problem doesn't have any randomness, right?
>
> Best Regards,
> Derya
>
> "Magnus " <magax@itn.liu.se> wrote in message
> news:hcc19l$neo$1@fred.mathworks.com...
> > Update:
> >
> > Following a recommendation of a colleague I tried the fminsearch on an
> > identical set of data for the two cases when optimset was set to use
> > Nelder-Mead (NM) and when it was set to Levenberg-Marquardt (LM). The
> > output shows that in the NM case the optimizer never finishes but quits
> > with flag 0 after 1406 iterations. In the LM case the optimizer quite
> > successfully with flag 1 with 2241 iterations.
> >
> > This would imply that the optimset argument does make a difference but
> > that the algorithm field in the output structure still reads "Nelder-mead
> > simplex direct search" even if it in fact is using LM.
> >
> > /M.
> >
> >
> >
> > "Magnus " <magax@itn.liu.se> wrote in message
> > <hcbn39$k4a$1@fred.mathworks.com>...
> >> Dear All,
> >>
> >> I have searched the newsgroup for "fminsearch optimset" with combinations
> >> on "Levenberg-Marquardt" but I am still not finding what I am looking
> >> for. I hope you can help.
> >>
> >> Question: I am suspecting that fminsearch cannot be changed to use any
> >> other optimization algorithm than Nelder-Mead and that my changes to the
> >> optimset argument are simply ignored. Is this true? If not, any
> >> suggestions on how I can change fminsearch to work with
> >> Levenberg-Marquardt? Alternatively, what other Matlab function would be
> >> appropriate for this task?
> >>
> >> Application: I am trying to estimate a projection matrix and I want to
> >> use fminsearch to find the optimal parameters to minimize the
> >> reprojection error, i.e. the screen distance between some ground truth
> >> markers projected on the screen and some additional test markers also
> >> projected to the screen.
> >>
> >> My code, using Matlab 7.3.0.298 (R2006b) on Ubuntu Dapper Drake, looks
> >> like this:
> >>
> >> % Here I try to change the fminsearch's default optimiser from
> >> Nelder-Mead to Levenberg-Marquardt and also make it run for a little
> >> longer
> >> options = optimset('MaxFunEvals', 10000, 'MaxIter', 10000);
> >> options = optimset(options, 'LevenbergMarquardt, 'on');
> >>
> >> % Here I call fminsearch with a function handle to the function that
> >> calculates an error, an array of parameter estimates that are to be
> >> changed such that the error returned by the function in the function
> >> handle is minimized. This error is reported back to errval, and I can
> >> also see if the optimizer terminated prematurely in flag. The output data
> >> structure also gives me further information.
> >> [estimates errval flag output] = fminsearch(@psuedoHuberCostFunction, [rx
> >> ry rz tx ty tz fx fy px py], options);
> >>
> >> Observations:
> >>
> >> 1. The code as written here above runs, but the output.algorithm, which
> >> indicates which algorithm that was used, says that Nelder Mead was used.
> >> 2. If I change the call to optimset to any other string than
> >> 'LevenbergMarquardt', this results in an error.
> >>
> >> Motivation: I want to see if Levenberg-Marquardt with its adaptable step
> >> length can deal with a more complex parameter surface compared to
> >> Nelder-Mead and therefore is a better choice for camera calibrations with
> >> some alignment noise between correspondence points.
> >>
> >> Thanks for your time and help.
> >>
> >> Magnus
>