Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
MCS algorithm
open-in-new
<h2 id="simplified-workflow">Simplified workflow</h2> <p>The MCS workflow is visualized in Figures 1 and 2. Each step of the algorithm can be split into four stages: </p> <ol><li>Identify a potential candidate for splitting (magenta, thick).</li> <li>Identify the optimal splitting direction and the expected optimal position of the splitting point (green).</li> <li>Evaluate the objective function at the splitting point or recover it from the already computed set; the latter applies if the current splitting point has already been reached when splitting a neighboring box.</li> <li>Generate new boxes (magenta, thin) based on the values of the objective function at the splitting point.</li></ol> <p>At each step the green point with the temporary yellow halo is the unique <i>base point</i> of the box; each box has an associated value of the objective, namely its value at the box's base point. </p><p>In order to determine if a box will be split two separate splitting criteria are used. The first one, <i>splitting by rank</i>, ensures that large boxes that have not been split too often will be split eventually. If it applies then the splitting point is easily determined at a fixed fraction of the length of the side being split. The second one, <i>splitting by expected gain</i>, employs a local one-dimensional parabolic quadratic model (surrogate) along a single coordinate. In this case the splitting point is defined as the minimum of the surrogate along a line segment and the box is split only if the interpolant value (serving as a proxy for the true value of the objective) is lower than the current best sampled function value. </p> <h2 id="convergence">Convergence</h2> <p>The algorithm is guaranteed to converge to the global minimum in the long run (i.e. when the number of function evaluations and the <i>search depth</i> are arbitrarily large) if the objective function is continuous in the neighbourhood of the global minimizer. This follows from the fact that any box will become arbitrarily small eventually, hence the spacing between samples tends to zero as the number of function evaluations tends to infinity. </p> <h2 id="recursive-implementation">Recursive implementation</h2> <p>MCS is designed to be implemented in an efficient <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursive</a> manner with the aid of <a href="/facts/Tree_(data_structure)/RcXz9noF">trees</a>. With this approach the amount of memory required is independent of problem dimensionality since the sampling points are not stored explicitly. Instead, just a single coordinate of each sample is saved and the remaining coordinates can be recovered by tracing the history of a box back to the root (initial box). This method was suggested by the authors and used in their original implementation.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="external-links">External links</h2> <ul><li><a href="https://arnold-neumaier.at/software/mcs/">Homepage of the algorithm</a></li> <li><a href="https://www.mat.univie.ac.at/~neum/glopt/janka/dix_sze_eng.html">Performance of the algorithm relative to others</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Rios, L. M.; Sahinidis, N. V. (2013). "Derivative-free optimization: a review of algorithms and comparison of software implementations". Journal of Global Optimization. 56 (3): 1247–1293. doi:10.1007/s10898-012-9951-y. hdl:10.1007/s10898-012-9951-y. S2CID 254652321. <a href="https://link.springer.com/article/10.1007/s10898-012-9951-y" target="_blank">https://link.springer.com/article/10.1007/s10898-012-9951-y</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Huyer, W.; Neumaier, A. (1999). "Global Optimization by Multilevel Coordinate Search". Journal of Global Optimization. 14 (4): 331–355. doi:10.1023/A:1008382309369. S2CID 1855536. <a href="https://link.springer.com/article/10.1023/A:1008382309369" target="_blank">https://link.springer.com/article/10.1023/A:1008382309369</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Huyer, W.; Neumaier, A. (1999). "Global Optimization by Multilevel Coordinate Search". Journal of Global Optimization. 14 (4): 331–355. doi:10.1023/A:1008382309369. S2CID 1855536. <a href="https://link.springer.com/article/10.1023/A:1008382309369" target="_blank">https://link.springer.com/article/10.1023/A:1008382309369</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>