MCS algorithm - Revision history

82.69.126.43: /* External links */Fixed link which had died two years ago

2024-04-06T18:50:50Z

External links: Fixed link which had died two years ago

← Previous revision		Revision as of 18:50, 6 April 2024
Line 29:		Line 29:

	==External links==		==External links==
	* [https://~~www.mat.univie.ac~~.at~~/~neum~~/software/mcs/ Homepage of the algorithm]		* [https://arnold-neumaier.at/software/mcs/ Homepage of the algorithm]
	* [https://www.mat.univie.ac.at/~neum/glopt/janka/dix_sze_eng.html Performance of the algorithm relative to others]		* [https://www.mat.univie.ac.at/~neum/glopt/janka/dix_sze_eng.html Performance of the algorithm relative to others]

Citation bot: Add: s2cid. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 2984/3499

2023-02-02T16:20:52Z

Add: s2cid. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 2984/3499

← Previous revision		Revision as of 16:20, 2 February 2023
Line 2:		Line 2:

	[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]
	For [[mathematical optimization]], '''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>		For [[mathematical optimization]], '''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|s2cid=254652321 \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|s2cid=1855536 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>

	To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.		To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.

JoeNMLC: /* top */ ce lead, add wikilink, rm context tag

2022-03-23T19:49:24Z

top: ce lead, add wikilink, rm context tag

← Previous revision		Revision as of 19:49, 23 March 2022
Line 1:		Line 1:
	{{Context\|date=October 2009}}

	[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]		[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]

	[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]
		⚫	For [[mathematical optimization]], '''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>

⚫	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>

	To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.		To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.

Najko32 at 16:38, 3 August 2021

2021-08-03T16:38:24Z

← Previous revision		Revision as of 16:38, 3 August 2021
Line 3:		Line 3:
	[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]		[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]

	[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]

	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>		'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>

WikiCleanerBot: v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2021-08-03T00:16:47Z

v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 00:16, 3 August 2021
Line 5:		Line 5:
	[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]

	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.		'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>

	To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.		To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.
Line 26:		Line 26:

	==Recursive implementation==		==Recursive implementation==
	MCS is designed to be implemented in an efficient [[recursion (computer science)\|recursive]] manner with the aid of [[tree (data structure)\|trees]]. 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 <ref name="mcs" />.		MCS is designed to be implemented in an efficient [[recursion (computer science)\|recursive]] manner with the aid of [[tree (data structure)\|trees]]. 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.<ref name="mcs" />

	==References==		==References==

OAbot: Open access bot: hdl added to citation with #oabot.

2021-08-02T03:11:36Z

Open access bot: hdl added to citation with #oabot.

← Previous revision		Revision as of 03:11, 2 August 2021
Line 5:		Line 5:
	[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]

	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y}}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.		'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.

	To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.		To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.

Najko32 at 00:03, 31 July 2021

2021-07-31T00:03:11Z

← Previous revision		Revision as of 00:03, 31 July 2021
Line 3:		Line 3:
	[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]		[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]

	[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt.\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]

	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y}}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.		'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y}}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.

Najko32 at 00:02, 31 July 2021

2021-07-31T00:02:19Z

← Previous revision		Revision as of 00:02, 31 July 2021
Line 12:		Line 12:

	==Simplified workflow==		==Simplified workflow==
	The MCS workflow is ~~presented~~ in Figures 1 and 2. Each step of the algorithm can be split into four stages:		The MCS workflow is visualized in Figures 1 and 2. Each step of the algorithm can be split into four stages:
	# Identify a potential candidate for splitting (magenta, thick).		# Identify a potential candidate for splitting (magenta, thick).
	# Identify the optimal splitting direction and the expected optimal position of the splitting point (green).		# Identify the optimal splitting direction and the expected optimal position of the splitting point (green).

Najko32 at 00:01, 31 July 2021

2021-07-31T00:01:16Z

← Previous revision		Revision as of 00:01, 31 July 2021
Line 3:		Line 3:
	[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]		[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]

	[[File:MCS himmelblau.gif\|thumb\|400px\|alt=~~-empty-~~\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt.\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]

	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y}}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.		'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y}}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.

Najko32: Removed the 'unreferenced' message since references have been added in the previous edit.

2021-07-30T23:58:32Z

Removed the 'unreferenced' message since references have been added in the previous edit.

← Previous revision		Revision as of 23:58, 30 July 2021
Line 1:		Line 1:
	{{unreferenced\|date=July 2012}}
	{{Context\|date=October 2009}}		{{Context\|date=October 2009}}

← Previous revision		Revision as of 16:20, 2 February 2023
Line 2:		Line 2:

	[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]
	For [[mathematical optimization]], '''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>		For [[mathematical optimization]], '''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|s2cid=254652321 \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|s2cid=1855536 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>

	To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.		To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.

← Previous revision		Revision as of 19:49, 23 March 2022
Line 1:		Line 1:
	{{Context\|date=October 2009}}

	[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]		[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]

	[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]
		⚫	For [[mathematical optimization]], '''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>

⚫	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>

	To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.		To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.

← Previous revision		Revision as of 16:38, 3 August 2021
Line 3:		Line 3:
	[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]		[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]

	[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS-himmelblau-new.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]

	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>		'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]].<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>

← Previous revision		Revision as of 03:11, 2 August 2021
Line 5:		Line 5:
	[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]

	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y}}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.		'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y\|hdl=10.1007/s10898-012-9951-y \|hdl-access=free }}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.

	To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.		To do so, the n-dimensional [[Candidate solution\|search space]] is represented by a set of non-intersecting hypercubes (boxes). The boxes are then iteratively split along an axis plane according to the value of the function at a representative point of the box (and its neighbours) and the box's size. These two splitting criteria combine to form a global search by splitting large boxes and a local search by splitting areas for which the function value is good.

← Previous revision		Revision as of 00:03, 31 July 2021
Line 3:		Line 3:
	[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]		[[File:MCS algorithm.gif\|thumb\|400px\|alt=A cartoon centipede reads books and types on a laptop.\|''Figure 1:'' MCS algorithm (''without'' local search) applied to the two-dimensional [[Rosenbrock function]]. The global minimum <math>f_{min}=0</math> is located at <math>(x,y)=(1,1)</math>. MCS identifies a position with <math>f\approx 0.002</math> within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.]]

	[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt.\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]		[[File:MCS himmelblau.gif\|thumb\|400px\|alt=no alt\|''Figure 2:'' MCS (without local search) applied to the [[Himmelblau's function]] with four local minima where <math>f(x)=0</math>.]]

	'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y}}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.		'''Multilevel Coordinate Search''' ('''MCS''') is an efficient<ref>{{cite journal \|last1=Rios \|first1=L. M. \|last2=Sahinidis \|first2=N. V. \|title=Derivative-free optimization: a review of algorithms and comparison of software implementations \|journal=Journal of Global Optimization \|date=2013 \|volume=56 \|issue=3 \|pages=1247–1293 \|doi=10.1007/s10898-012-9951-y\|url=https://link.springer.com/article/10.1007/s10898-012-9951-y}}</ref> [[algorithm]] for bound constrained [[global optimization]] using [[function (mathematics)\|function]] values [[derivative-free optimization\|only]]<ref name="mcs">{{cite journal \|last1=Huyer \|first1=W. \|last2=Neumaier \|first2=A. \|title=Global Optimization by Multilevel Coordinate Search \|journal=Journal of Global Optimization \|date=1999 \|volume=14 \|issue=4 \|pages=331–355 \|doi=10.1023/A:1008382309369 \|url=https://link.springer.com/article/10.1023/A:1008382309369}}</ref>.