Why does Pattern Search take so long?
11 次查看(过去 30 天)
显示 更早的评论
Hello,
Could anyone please help me figure out the following?
This is the first time I have tried the pattern search solver for my optimization problem with 29 unknowns. The problem only has lower and upper bounds. I have successfully worked with a number of local optimizers like lsqnonlin on the same problem.
I wonder why pattern search took a tremendous amount of time (compared with local solvers) for the same number of function evaluations (100,000 in this case) as with local solvers. Please look at the options I am using:
opts = psoptimset( 'Cache','on', 'CompletePoll','on', 'InitialMeshSize',0.1, ...
'MaxIter',1e4, 'MaxFunEvals',1e5, 'ScaleMesh','off' );
When I run optimization (please see below), it hits the maximum number of function evaluations allowed. This in itself might not be good, but the issue is the overall time being more than 4,000 seconds:
tic; [param, fval, exitflag, output] = patternsearch( fun, guess_new, [], [], [], [], ...
zeros(1,29), ones(1,29), [], opts ); toc
Maximum number of function evaluations exceeded: increase options.MaxFunEvals.
Elapsed time is 4131.745766 seconds.
Whenever I simply run the same function this many times (100,000), it only takes around 800 seconds. Similarly, when passing the same function to fmincon or lsqnonlin, it takes 800-900 seconds for 100,000 function counts.
Besides, from my point of view, the default pattern, which is 'GPS Positive basis 2N', should take 58 function counts at each iteration: this is due to having 29 unknown as well as using 'on' for 'CompletePoll'. If I limit MaxFunEvals to 100,000, the number of iterations taken before hitting the limit and stopping the optimization should be (100000 / 58) = 1724. However, it can be seen from the output structure that the actual iteration number is greater than 1724:
output
output =
function: [function_handle]
problemtype: 'boundconstraints'
pollmethod: 'gpspositivebasis2n'
searchmethod: []
iterations: 1948
funccount: 100000
meshsize: 3.9063e-04
maxconstraint: 0
message: 'Maximum number of function evaluations exceeded: increase options.MaxFunEvals.'
This, together with the timing issue, makes me think how pattern search worked in this particular case. I would greatly appreciate any help.
Thank you in advance,
Igor.
0 个评论
采纳的回答
Alan Weiss
2014-1-6
编辑:Alan Weiss
2014-1-6
Perhaps the Cache option should be 'off'. Please let us know if that makes a difference.
If the problem is suitable for lsqnonlin or fmincon, then those solvers will undoubtedly be more efficient. As you probably know, patternsearch is less efficient than they are. patternsearch is recommended for nonsmooth functions, while Optimization Toolbox solvers are for smooth functions.
Alan Weiss
MATLAB mathematical toolbox documentation
9 个评论
Alan Weiss
2014-1-10
Based on your latest description, it seems to me that lsqnonlin accompanied by larger-than-default finite difference steps, and possibly central finite differences, is your best bet.
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation
更多回答(0 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Surrogate Optimization 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!