How to use optimset for fminsearch to run Levenberg-Marquardt instead of Nelder-Mead?
in [Matlab]
|
Prev: MATLAB Out-of-core Solution
Next: SNR estimation
From: Magnus on 29 Oct 2009 05:26 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
From: Magnus on 29 Oct 2009 08:20 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(a)itn.liu.se> wrote in message <hcbn39$k4a$1(a)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
From: Magnus on 29 Oct 2009 10:58 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(a)itn.liu.se> wrote in message <hcc19l$neo$1(a)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(a)itn.liu.se> wrote in message <hcbn39$k4a$1(a)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
From: John D'Errico on 29 Oct 2009 11:20 "Magnus " <magax(a)itn.liu.se> wrote in message <hccahp$d2b$1(a)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
From: Steven Lord on 29 Oct 2009 11:58
"Magnus " <magax(a)itn.liu.se> wrote in message news:hccahp$d2b$1(a)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(a)mathworks.com comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ |