{"id":899,"date":"2014-05-20T10:38:43","date_gmt":"2014-05-20T15:38:43","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=899"},"modified":"2017-09-24T19:27:18","modified_gmt":"2017-09-25T00:27:18","slug":"selecting-the-granularity-you-want-in-globalsearch-or-multistart","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2014\/05\/20\/selecting-the-granularity-you-want-in-globalsearch-or-multistart\/","title":{"rendered":"Selecting the Granularity You Want in GlobalSearch or MultiStart"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>I'd like to introduce this week's guest blogger <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/answers\/contributors\/1033975-alan-weiss\">Alan Weiss<\/a>. Alan writes documentation for mathematical toolboxes here at MathWorks.<\/p><p>Do you use <tt>GlobalSearch<\/tt> or <tt>MultiStart<\/tt> for finding multiple local solutions to your optimization problems? Both of these solvers can report the locations and objective function values of the local solutions they find, as well as the starting points that led to each local solution.<\/p><p>Sometimes, though, the solvers report too many local solutions. Their definition of what constitutes \"distinct\" solutions can differ from yours. This article shows the problem, and two solutions. One solution involves setting <tt>GlobalSearch<\/tt> or <tt>MultiStart<\/tt> tolerances. But this can be difficult if you don't know beforehand how close solutions can be. The other involves the <tt>clumpthem<\/tt> function; download it <a href=\"https:\/\/blogs.mathworks.com\/images\/loren\/2014\/clumpthem.m\">here<\/a>.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#d2f91f3c-eee1-4c30-9823-31b334ef67fb\">A Function with Six Local Minima<\/a><\/li><li><a href=\"#76a840de-f60e-4853-b36d-8c9309f4d7fa\"><tt>MultiStart<\/tt> Finds 50 Local Minima<\/a><\/li><li><a href=\"#990ab153-d4d1-4402-bcc2-23c3830d8ff9\">Clump the Minima with <tt>MultiStart<\/tt><\/a><\/li><li><a href=\"#5136da42-db50-48da-a5e8-76fd92a59e49\">Clump the Minima Programmatically<\/a><\/li><li><a href=\"#4e45f037-390c-467e-9ae6-21a1bb679df1\">Performance<\/a><\/li><li><a href=\"#2d12c745-34d9-4f25-a69c-507ff4931ebd\">Feedback<\/a><\/li><\/ul><\/div><h4>A Function with Six Local Minima<a name=\"d2f91f3c-eee1-4c30-9823-31b334ef67fb\"><\/a><\/h4><p>For example, look at the <a href=\"https:\/\/www.mathworks.com\/help\/gads\/run-the-solver.html\">six-hump camelback function<\/a> described in the documentation.  Get the <a href=\"https:\/\/blogs.mathworks.com\/images\/loren\/2014\/sixhumps.m\"><tt>sixhumps<\/tt> code<\/a>.<\/p><pre class=\"codeinput\">sixmin = sixhumps\r\n<\/pre><pre class=\"codeoutput\">sixmin = \r\n    @(x)(4*x(:,1).^2-2.1*x(:,1).^4+x(:,1).^6\/3+x(:,1).*x(:,2)-4*x(:,2).^2+4*x(:,2).^4)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2014\/clumpingBlogPost_01.png\" alt=\"\"> <img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2014\/clumpingBlogPost_02.png\" alt=\"\"> <p>You can see in the contour plot that there are six local minima. The colored asterisks mark the minima.<\/p><h4><tt>MultiStart<\/tt> Finds 50 Local Minima<a name=\"76a840de-f60e-4853-b36d-8c9309f4d7fa\"><\/a><\/h4><p>Take a look at the number of local minima reported by running <tt>MultiStart<\/tt> with the <a href=\"https:\/\/www.mathworks.com\/help\/optim\/ug\/fmincon.html\"><tt>fmincon<\/tt><\/a> local solver and active-set algorithm.<\/p><pre class=\"codeinput\">ms = MultiStart;\r\nopts = optimoptions(@fmincon,<span class=\"string\">'Algorithm'<\/span>,<span class=\"string\">'active-set'<\/span>);\r\nproblem = createOptimProblem(<span class=\"string\">'fmincon'<\/span>,<span class=\"string\">'x0'<\/span>,[-1,2],<span class=\"keyword\">...<\/span>\r\n<span class=\"string\">'objective'<\/span>,sixmin,<span class=\"string\">'lb'<\/span>,[-3,-3],<span class=\"string\">'ub'<\/span>,[3,3],<span class=\"keyword\">...<\/span>\r\n<span class=\"string\">'options'<\/span>,opts);\r\nrng <span class=\"string\">default<\/span> <span class=\"comment\">% for reproducibility<\/span>\r\n[xminm,fminm,flagm,outptm,manyminsm] = run(ms,problem,50); <span class=\"comment\">% run fmincon 50 times<\/span>\r\nsize(manyminsm)\r\n<\/pre><pre class=\"codeoutput\">\r\nMultiStart completed the runs from all start points.\r\n\r\nAll 50 local solver runs converged with a positive local solver exit flag.\r\nans =\r\n     1    50\r\n<\/pre><p>How could there be 50 separate minima reported when you know that there are only six points that are local minima? The answer is that many of these minima are close to each other. For example, the first three points look the same.<\/p><pre class=\"codeinput\">manyminsm(1).X\r\nmanyminsm(2).X\r\nmanyminsm(3).X\r\n<\/pre><pre class=\"codeoutput\">ans =\r\n    -0.089843      0.71266\r\nans =\r\n    -0.089844      0.71265\r\nans =\r\n    -0.089834      0.71265\r\n<\/pre><p>Of course, these reported minima aren't really the same.<\/p><pre class=\"codeinput\">norm(manyminsm(1).X - manyminsm(2).X)\r\n<\/pre><pre class=\"codeoutput\">ans =\r\n   7.6691e-06\r\n<\/pre><p>The point is, its default tolerances cause <tt>MultiStart<\/tt> to report different minima if they differ by more than 1e-6 in value or position. And these minima are more than 1e-6 apart.<\/p><h4>Clump the Minima with <tt>MultiStart<\/tt><a name=\"990ab153-d4d1-4402-bcc2-23c3830d8ff9\"><\/a><\/h4><p>You can loosen the default <tt>MultiStart<\/tt> tolerances to have <tt>MultiStart<\/tt> automatically combine similar minima.<\/p><pre class=\"codeinput\">rng <span class=\"string\">default<\/span> <span class=\"comment\">% for reproducibility<\/span>\r\nms.TolX = 1e-3;\r\nms.TolFun = 1e-4;\r\n[xminloose,fminloose,flagloose,outptloose,manyminsloose] = run(ms,problem,50);\r\nsize(manyminsloose)\r\n<\/pre><pre class=\"codeoutput\">\r\nMultiStart completed the runs from all start points.\r\n\r\nAll 50 local solver runs converged with a positive local solver exit flag.\r\nans =\r\n     1     6\r\n<\/pre><p>Loosening the tolerances caused <tt>MultiStart<\/tt> to give just the six truly different local minima. But this process involved rerunning the solver.<\/p><h4>Clump the Minima Programmatically<a name=\"5136da42-db50-48da-a5e8-76fd92a59e49\"><\/a><\/h4><p>Wouldn't it be better to clump the minima without running the solver again? That is the point of the <tt>clumpthem<\/tt> function. It takes <tt>MultiStart<\/tt> or <tt>GlobalSearch<\/tt> solutions and clumps them to the tolerances you want. For example<\/p><pre class=\"codeinput\">clumped = clumpthem(manyminsm,1e-3,1e-4); <span class=\"comment\">% the first tolerance is TolX, then TolFun<\/span>\r\nsize(clumped)\r\n<\/pre><pre class=\"codeoutput\">ans =\r\n     1     6\r\n<\/pre><p>The answers you get either way are identical.<\/p><pre class=\"codeinput\">isequal(manyminsloose(1).X, clumped(1).X)\r\n<\/pre><pre class=\"codeoutput\">ans =\r\n     1\r\n<\/pre><p>How does <tt>clumpthem<\/tt> work? It uses the fact that <tt>MultiStart<\/tt> and <tt>GlobalSearch<\/tt> return solutions in order, from best (lowest objective function value) to worst. It takes the first solution and compares it to the second, both in terms of objective function values and distance between the solutions. If both comparisons are below the tolerances, <tt>clumpthem<\/tt> removes the second solution, adding its starting point to the list of <tt>X0<\/tt> starting points. If the objective function value of the second solution is too high, then <tt>clumpthem<\/tt> starts a new clump. If the objective function difference is small enough, but the distance between solutions is too large, <tt>clumpthem<\/tt> proceeds to compare the first solution with the third. It continues in this way until it runs out of solutions to clump.<\/p><p>This procedure is quite speedy, as you will see in the next section.<\/p><h4>Performance<a name=\"4e45f037-390c-467e-9ae6-21a1bb679df1\"><\/a><\/h4><p>Check the speed of <tt>clumpthem<\/tt>.<\/p><pre class=\"codeinput\">tic;\r\nclumped = clumpthem(manyminsm,1e-3,1e-4);\r\ntoc\r\n<\/pre><pre class=\"codeoutput\">Elapsed time is 0.006322 seconds.\r\n<\/pre><p><tt>MultiStart<\/tt> is much slower, even with this fairly simple function:<\/p><pre class=\"codeinput\">rng <span class=\"string\">default<\/span> <span class=\"comment\">% for reproducibility<\/span>\r\ntic;\r\n[xminloose,fminloose,flagloose,outptloose,manyminsloose] = run(ms,problem,50);\r\ntoc\r\n<\/pre><pre class=\"codeoutput\">\r\nMultiStart completed the runs from all start points.\r\n\r\nAll 50 local solver runs converged with a positive local solver exit flag.\r\nElapsed time is 0.863509 seconds.\r\n<\/pre><h4>Feedback<a name=\"2d12c745-34d9-4f25-a69c-507ff4931ebd\"><\/a><\/h4><p>Do you use <tt>MultiStart<\/tt> or <tt>GlobalSearch<\/tt> to search for multiple local solutions? Have you been annoyed by finding spurious differences in solutions? Tell us about it <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=899#respond\">here<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_14d67a29a8624ff5a6824e8dbe4faa9b() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='14d67a29a8624ff5a6824e8dbe4faa9b ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 14d67a29a8624ff5a6824e8dbe4faa9b';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2014 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_14d67a29a8624ff5a6824e8dbe4faa9b()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2014a<br><\/p><\/div><!--\r\n14d67a29a8624ff5a6824e8dbe4faa9b ##### SOURCE BEGIN #####\r\n%% Selecting the Granularity You Want in GlobalSearch or MultiStart\r\n% I'd like to introduce this week's guest blogger\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/answers\/contributors\/1033975-alan-weiss Alan Weiss>.\r\n% Alan writes documentation for mathematical toolboxes here at MathWorks. \r\n%\r\n% Do you use <https:\/\/www.mathworks.com\/help\/gads\/globalsearch-class.html\r\n% |GlobalSearch|> or\r\n% <https:\/\/www.mathworks.com\/help\/gads\/multistart-class.html |MultiStart|>\r\n% for finding multiple local solutions to your optimization problems? Both\r\n% of these solvers can report the locations and objective function values\r\n% of the local solutions they find, as well as the starting points that led\r\n% to each local solution.\r\n%\r\n% Sometimes, though, the solvers report too many local solutions. Their\r\n% definition of what constitutes \"distinct\" solutions can differ from\r\n% yours. This article shows the problem, and two solutions. One solution\r\n% involves setting |GlobalSearch| or |MultiStart| tolerances. But this can\r\n% be difficult if you don't know beforehand how close solutions can be. The\r\n% other involves the |clumpthem| function; download it\r\n% <https:\/\/blogs.mathworks.com\/images\/loren\/2014\/clumpthem.m here>.\r\n%\r\n%% A Function with Six Local Minima\r\n% For example, look at the\r\n% <https:\/\/www.mathworks.com\/help\/gads\/run-the-solver.html six-hump\r\n% camelback function> described in the documentation.  Get the\r\n% <https:\/\/blogs.mathworks.com\/images\/loren\/2014\/sixhumps.m |sixhumps|\r\n% code>.\r\nsixmin = sixhumps\r\n%%\r\n% You can see in the contour plot that there are six local minima. The\r\n% colored asterisks mark the minima.\r\n%% |MultiStart| Finds 50 Local Minima\r\n% Take a look at the number of local minima reported by running\r\n% |MultiStart| with the\r\n% <https:\/\/www.mathworks.com\/help\/optim\/ug\/fmincon.html |fmincon|> local\r\n% solver and active-set algorithm.\r\nms = MultiStart;\r\nopts = optimoptions(@fmincon,'Algorithm','active-set');\r\nproblem = createOptimProblem('fmincon','x0',[-1,2],...\r\n'objective',sixmin,'lb',[-3,-3],'ub',[3,3],...\r\n'options',opts);\r\nrng default % for reproducibility\r\n[xminm,fminm,flagm,outptm,manyminsm] = run(ms,problem,50); % run fmincon 50 times\r\nsize(manyminsm)\r\n\r\n%%\r\n% How could there be 50 separate minima reported when you know that there\r\n% are only six points that are local minima? The answer is that many of\r\n% these minima are close to each other. For example, the first three points\r\n% look the same.\r\nmanyminsm(1).X\r\nmanyminsm(2).X\r\nmanyminsm(3).X\r\n\r\n%%\r\n% Of course, these reported minima aren't really the same.\r\nnorm(manyminsm(1).X - manyminsm(2).X)\r\n\r\n%%\r\n% The point is, its default tolerances cause |MultiStart| to report different\r\n% minima if they differ by more than 1e-6 in value or position. And these\r\n% minima are more than 1e-6 apart.\r\n\r\n%% Clump the Minima with |MultiStart|\r\n% You can loosen the default |MultiStart| tolerances to have |MultiStart|\r\n% automatically combine similar minima.\r\nrng default % for reproducibility\r\nms.TolX = 1e-3;\r\nms.TolFun = 1e-4;\r\n[xminloose,fminloose,flagloose,outptloose,manyminsloose] = run(ms,problem,50);\r\nsize(manyminsloose)\r\n%%\r\n% Loosening the tolerances caused |MultiStart| to give just the six truly\r\n% different local minima. But this process involved rerunning the solver.\r\n%% Clump the Minima Programmatically\r\n% Wouldn't it be better to clump the minima without running the solver\r\n% again? That is the point of the |clumpthem| function. It takes\r\n% |MultiStart| or |GlobalSearch| solutions and clumps them to the\r\n% tolerances you want. For example\r\nclumped = clumpthem(manyminsm,1e-3,1e-4); % the first tolerance is TolX, then TolFun\r\nsize(clumped)\r\n%%\r\n% The answers you get either way are identical.\r\nisequal(manyminsloose(1).X, clumped(1).X)\r\n%%\r\n% How does |clumpthem| work? It uses the fact that |MultiStart| and\r\n% |GlobalSearch| return solutions in order, from best (lowest objective\r\n% function value) to worst. It takes the first solution and compares it to\r\n% the second, both in terms of objective function values and distance\r\n% between the solutions. If both comparisons are below the tolerances,\r\n% |clumpthem| removes the second solution, adding its starting point to the\r\n% list of |X0| starting points. If the objective function value of the\r\n% second solution is too high, then |clumpthem| starts a new clump. If the\r\n% objective function difference is small enough, but the distance between\r\n% solutions is too large, |clumpthem| proceeds to compare the first\r\n% solution with the third. It continues in this way until it runs out of\r\n% solutions to clump.\r\n%\r\n% This procedure is quite speedy, as you will see in the next section.\r\n%% Performance\r\n% Check the speed of |clumpthem|.\r\ntic;\r\nclumped = clumpthem(manyminsm,1e-3,1e-4);\r\ntoc\r\n%%\r\n% |MultiStart| is much slower, even with this fairly simple function:\r\nrng default % for reproducibility\r\ntic;\r\n[xminloose,fminloose,flagloose,outptloose,manyminsloose] = run(ms,problem,50);\r\ntoc\r\n%% Feedback\r\n% Do you use |MultiStart| or |GlobalSearch| to search for multiple local\r\n% solutions? Have you been annoyed by finding spurious differences in\r\n% solutions? Tell us about it\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=899#respond here>.\r\n\r\n\r\n##### SOURCE END ##### 14d67a29a8624ff5a6824e8dbe4faa9b\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2014\/clumpingBlogPost_01.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>I'd like to introduce this week's guest blogger <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/answers\/contributors\/1033975-alan-weiss\">Alan Weiss<\/a>. Alan writes documentation for mathematical toolboxes here at MathWorks.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2014\/05\/20\/selecting-the-granularity-you-want-in-globalsearch-or-multistart\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[39,60],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/899"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=899"}],"version-history":[{"count":5,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/899\/revisions"}],"predecessor-version":[{"id":2445,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/899\/revisions\/2445"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=899"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=899"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=899"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}