The Nelder-Mead optimization<\/strong> algorithm is a widely used approach for non-differentiable objective functions.<\/p>\n As such, it is generally referred to as a pattern search algorithm and is used as a local or global search procedure, challenging nonlinear and potentially noisy and multimodal function optimization problems.<\/p>\n In this tutorial, you will discover the Nelder-Mead optimization algorithm.<\/p>\n After completing this tutorial, you will know:<\/p>\n Let\u2019s get started.<\/p>\n How to Use the Nelder-Mead Optimization in Python This tutorial is divided into three parts; they are:<\/p>\n Nelder-Mead<\/a> is an optimization algorithm named after the developers of the technique, John Nelder<\/a> and Roger Mead<\/a>.<\/p>\n The algorithm was described in their 1965 paper titled \u201cA Simplex Method For Function Minimization<\/a>\u201d and has become a standard and widely used technique for function optimization.<\/p>\n It is appropriate for one-dimensional or multidimensional functions with numerical inputs.<\/p>\n Nelder-Mead is a pattern search optimization algorithm<\/a>, which means it does require or use function gradient information and is appropriate for optimization problems where the gradient of the function is unknown or cannot be reasonably computed.<\/p>\n It is often used for multidimensional nonlinear function optimization problems, although it can get stuck in local optima.<\/p>\n Practical performance of the Nelder\u2013Mead algorithm is often reasonable, though stagnation has been observed to occur at nonoptimal points. Restarting can be used when stagnation is detected.<\/p>\n<\/blockquote>\n \u2014 Page 239, Numerical Optimization<\/a>, 2006.<\/p>\n A starting point must be provided to the algorithm, which may be the endpoint of another global optimization algorithm or a random point drawn from the domain.<\/p>\n Given that the algorithm may get stuck, it may benefit from multiple restarts with different starting points.<\/p>\n The Nelder-Mead simplex method uses a simplex to traverse the space in search of a minimum.<\/p>\n<\/blockquote>\n \u2014 Page 105, Algorithms for Optimization<\/a>, 2019.<\/p>\n The algorithm works by using a shape structure (called a simplex) composed of n<\/em> + 1 points (vertices), where n<\/em> is the number of input dimensions to the function.<\/p>\n For example, on a two-dimensional problem that may be plotted as a surface, the shape structure would be composed of three points represented as a triangle.<\/p>\n The Nelder-Mead method uses a series of rules that dictate how the simplex is updated based on evaluations of the objective function at its vertices.<\/p>\n<\/blockquote>\n \u2014 Page 106, Algorithms for Optimization<\/a>, 2019.<\/p>\n The points of the shape structure are evaluated and simple rules are used to decide how to move the points of the shape based on their relative evaluation. This includes operations such as \u201creflection<\/em>,\u201d \u201cexpansion<\/em>,\u201d \u201ccontraction<\/em>,\u201d and \u201cshrinkage<\/em>\u201d of the simplex shape on the surface of the objective function.<\/p>\n In a single iteration of the Nelder\u2013Mead algorithm, we seek to remove the vertex with the worst function value and replace it with another point with a better value. The new point is obtained by reflecting, expanding, or contracting the simplex along the line joining the worst vertex with the centroid of the remaining vertices. If we cannot find a better point in this manner, we retain only the vertex with the best function value, and we shrink the simplex by moving all other vertices toward this value.<\/p>\n<\/blockquote>\n \u2014 Page 238, Numerical Optimization<\/a>, 2006.<\/p>\n The search stops when the points converge on an optimum, when a minimum difference between evaluations is observed, or when a maximum number of function evaluations are performed.<\/p>\n Now that we have a high-level idea of how the algorithm works, let\u2019s look at how we might use it in practice.<\/p>\n The Nelder-Mead optimization algorithm can be used in Python via the minimize() function<\/a>.<\/p>\n This function requires that the \u201cmethod<\/em>\u201d argument be set to \u201cnelder-mead<\/em>\u201d to use the Nelder-Mead algorithm. It takes the objective function to be minimized and an initial point for the search.<\/p>\n The result is an OptimizeResult<\/a> object that contains information about the result of the optimization accessible via keys.<\/p>\n For example, the \u201csuccess<\/em>\u201d boolean indicates whether the search was completed successfully or not, the \u201cmessage<\/em>\u201d provides a human-readable message about the success or failure of the search, and the \u201cnfev<\/em>\u201d key indicates the number of function evaluations that were performed.<\/p>\n Importantly, the \u201cx<\/em>\u201d key specifies the input values that indicate the optima found by the search, if successful.<\/p>\n We can demonstrate the Nelder-Mead optimization algorithm on a well-behaved function to show that it can quickly and efficiently find the optima without using any derivative information from the function.<\/p>\n In this case, we will use the x^2 function in two-dimensions, defined in the range -5.0 to 5.0 with the known optima at [0.0, 0.0].<\/p>\n We can define the objective()<\/em> function below.<\/p>\n We will use a random point in the defined domain as a starting point for the search.<\/p>\n The search can then be performed. We use the default maximum number of function evaluations set via the \u201cmaxiter<\/em>\u201d and set to N*200, where N is the number of input variables, which is two in this case, e.g. 400 evaluations.<\/p>\n After the search is finished, we will report the total function evaluations used to find the optima and the success message of the search, which we expect to be positive in this case.<\/p>\n Finally, we will retrieve the input values for located optima, evaluate it using the objective function, and report both in a human-readable manner.<\/p>\n Tying this together, the complete example of using the Nelder-Mead optimization algorithm on a simple convex objective function is listed below.<\/p>\n Running the example executes the optimization, then reports the results.<\/p>\n Note<\/strong>: Your results may vary<\/a> given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.<\/p>\n In this case, we can see that the search was successful, as we expected, and was completed after 88 function evaluations.<\/p>\n We can see that the optima was located with inputs very close to [0,0], which evaluates to the minimum objective value of 0.0.<\/p>\n Now that we have seen how to use the Nelder-Mead optimization algorithm successfully, let\u2019s look at some examples where it does not perform so well.<\/p>\n The Nelder-Mead optimization algorithm works well for a range of challenging nonlinear and non-differentiable objective functions.<\/p>\n Nevertheless, it can get stuck on multimodal optimization problems and noisy problems.<\/p>\n To make this concrete, let\u2019s look at an example of each.<\/p>\n A noisy objective function is a function that gives different answers each time the same input is evaluated.<\/p>\n We can make an objective function artificially noisy by adding small Gaussian random numbers to the inputs prior to their evaluation.<\/p>\n For example, we can define a one-dimensional version of the x^2 function and use the randn() function<\/a> to add small Gaussian random numbers to the input with a mean of 0.0 and a standard deviation of 0.3.<\/p>\n The noise will make the function challenging to optimize for the algorithm and it will very likely not locate the optima at x=0.0.<\/p>\n The complete example of using Nelder-Mead to optimize the noisy objective function is listed below.<\/p>\n Running the example executes the optimization, then reports the results.<\/p>\n Note<\/strong>: Your results may vary<\/a> given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.<\/p>\n In this case, the algorithm does not converge and instead uses the maximum number of function evaluations, which is 200.<\/p>\n The algorithm may converge on some runs of the code but will arrive on a point away from the optima.<\/p>\n Many nonlinear objective functions may have multiple optima, referred to as multimodal problems.<\/p>\n The problem may be structured such that it has multiple global optima that have an equivalent function evaluation, or a single global optima and multiple local optima where algorithms like the Nelder-Mead can get stuck in search of the local optima.<\/p>\n The Ackley function<\/a> is an example of the latter. It is a two-dimensional objective function that has a global optima at [0,0] but has many local optima.<\/p>\n The example below implements the Ackley and creates a three-dimensional plot showing the global optima and multiple local optima.<\/p>\n Running the example creates the surface plot of the Ackley function showing the vast number of local optima.<\/p>\n 3D Surface Plot of the Ackley Multimodal Function<\/p>\n<\/div>\n We would expect the Nelder-Mead function to get stuck in one of the local optima while in search of the global optima.<\/p>\n Initially, when the simplex is large, the algorithm may jump over many local optima, but as it contracts, it will get stuck.<\/p>\n We can explore this with the example below that demonstrates the Nelder-Mead algorithm on the Ackley function.<\/p>\n Running the example executes the optimization, then reports the results.<\/p>\n Note<\/strong>: Your results may vary<\/a> given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.<\/p>\n In this case, we can see that the search completed successfully but did not locate the global optima. It got stuck and found a local optima.<\/p>\n Each time we run the example, we will find a different local optima given the different random starting point for the search.<\/p>\n This section provides more resources on the topic if you are looking to go deeper.<\/p>\n In this tutorial, you discovered the Nelder-Mead optimization algorithm.<\/p>\n Specifically, you learned:<\/p>\n Do you have any questions?<\/strong> The post How to Use Nelder-Mead Optimization in Python<\/a> appeared first on Machine Learning Mastery<\/a>.<\/p>\n<\/div>\n Go to Source<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n
![\"How](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2021\/01\/How-to-Use-the-Nelder-Mead-Optimization-in-Python.jpg\")
<\/p>\n
Photo by Don Graham<\/a>, some rights reserved.<\/p>\n<\/div>\nTutorial Overview<\/h2>\n
\n
\n
Nelder-Mead Algorithm<\/h2>\n
\n
\n
\n
\n
Nelder-Mead Example in Python<\/h2>\n
...\r\n# perform the search\r\nresult = minimize(objective, pt, method='nelder-mead')<\/pre>\n
...\r\n# summarize the result\r\nprint('Status : %s' % result['message'])\r\nprint('Total Evaluations: %d' % result['nfev'])\r\nprint('Solution: %s' % result['x'])<\/pre>\n# objective function\r\ndef objective(x):\r\n\treturn x[0]**2.0 + x[1]**2.0<\/pre>\n
...\r\n# define range for input\r\nr_min, r_max = -5.0, 5.0\r\n# define the starting point as a random sample from the domain\r\npt = r_min + rand(2) * (r_max - r_min)<\/pre>\n
...\r\n# perform the search\r\nresult = minimize(objective, pt, method='nelder-mead')<\/pre>\n
...\r\n# summarize the result\r\nprint('Status : %s' % result['message'])\r\nprint('Total Evaluations: %d' % result['nfev'])<\/pre>\n...\r\n# evaluate solution\r\nsolution = result['x']\r\nevaluation = objective(solution)\r\nprint('Solution: f(%s) = %.5f' % (solution, evaluation))<\/pre>\n# nelder-mead optimization of a convex function\r\nfrom scipy.optimize import minimize\r\nfrom numpy.random import rand\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn x[0]**2.0 + x[1]**2.0\r\n\r\n# define range for input\r\nr_min, r_max = -5.0, 5.0\r\n# define the starting point as a random sample from the domain\r\npt = r_min + rand(2) * (r_max - r_min)\r\n# perform the search\r\nresult = minimize(objective, pt, method='nelder-mead')\r\n# summarize the result\r\nprint('Status : %s' % result['message'])\r\nprint('Total Evaluations: %d' % result['nfev'])\r\n# evaluate solution\r\nsolution = result['x']\r\nevaluation = objective(solution)\r\nprint('Solution: f(%s) = %.5f' % (solution, evaluation))<\/pre>\nStatus: Optimization terminated successfully.\r\nTotal Evaluations: 88\r\nSolution: f([ 2.25680716e-05 -3.87021351e-05]) = 0.00000<\/pre>\n
Nelder-Mead on Challenging Functions<\/h2>\n
Noisy Optimization Problem<\/h3>\n
# objective function\r\ndef objective(x):\r\n\treturn (x + randn(len(x))*0.3)**2.0<\/pre>\n
# nelder-mead optimization of noisy one-dimensional convex function\r\nfrom scipy.optimize import minimize\r\nfrom numpy.random import rand\r\nfrom numpy.random import randn\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn (x + randn(len(x))*0.3)**2.0\r\n\r\n# define range for input\r\nr_min, r_max = -5.0, 5.0\r\n# define the starting point as a random sample from the domain\r\npt = r_min + rand(1) * (r_max - r_min)\r\n# perform the search\r\nresult = minimize(objective, pt, method='nelder-mead')\r\n# summarize the result\r\nprint('Status : %s' % result['message'])\r\nprint('Total Evaluations: %d' % result['nfev'])\r\n# evaluate solution\r\nsolution = result['x']\r\nevaluation = objective(solution)\r\nprint('Solution: f(%s) = %.5f' % (solution, evaluation))<\/pre>\nStatus: Maximum number of function evaluations has been exceeded.\r\nTotal Evaluations: 200\r\nSolution: f([-0.6918238]) = 0.79431<\/pre>\n
Multimodal Optimization Problem<\/h3>\n
# ackley multimodal function\r\nfrom numpy import arange\r\nfrom numpy import exp\r\nfrom numpy import sqrt\r\nfrom numpy import cos\r\nfrom numpy import e\r\nfrom numpy import pi\r\nfrom numpy import meshgrid\r\nfrom matplotlib import pyplot\r\nfrom mpl_toolkits.mplot3d import Axes3D\r\n\r\n# objective function\r\ndef objective(x, y):\r\n\treturn -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20\r\n\r\n# define range for input\r\nr_min, r_max = -5.0, 5.0\r\n# sample input range uniformly at 0.1 increments\r\nxaxis = arange(r_min, r_max, 0.1)\r\nyaxis = arange(r_min, r_max, 0.1)\r\n# create a mesh from the axis\r\nx, y = meshgrid(xaxis, yaxis)\r\n# compute targets\r\nresults = objective(x, y)\r\n# create a surface plot with the jet color scheme\r\nfigure = pyplot.figure()\r\naxis = figure.gca(projection='3d')\r\naxis.plot_surface(x, y, results, cmap='jet')\r\n# show the plot\r\npyplot.show()<\/pre>\n
![\"3D](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/09\/3D-Surface-Plot-of-the-Ackley-Multimodal-Function-1024x768.png\")
<\/p>\n# nelder-mead for multimodal function optimization\r\nfrom scipy.optimize import minimize\r\nfrom numpy.random import rand\r\nfrom numpy import exp\r\nfrom numpy import sqrt\r\nfrom numpy import cos\r\nfrom numpy import e\r\nfrom numpy import pi\r\n\r\n# objective function\r\ndef objective(v):\r\n\tx, y = v\r\n\treturn -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20\r\n\r\n# define range for input\r\nr_min, r_max = -5.0, 5.0\r\n# define the starting point as a random sample from the domain\r\npt = r_min + rand(2) * (r_max - r_min)\r\n# perform the search\r\nresult = minimize(objective, pt, method='nelder-mead')\r\n# summarize the result\r\nprint('Status : %s' % result['message'])\r\nprint('Total Evaluations: %d' % result['nfev'])\r\n# evaluate solution\r\nsolution = result['x']\r\nevaluation = objective(solution)\r\nprint('Solution: f(%s) = %.5f' % (solution, evaluation))<\/pre>\nStatus: Optimization terminated successfully.\r\nTotal Evaluations: 62\r\nSolution: f([-4.9831427 -3.98656015]) = 11.90126<\/pre>\n<\/p>\n
Further Reading<\/h2>\n
Papers<\/h3>\n
\n
Books<\/h3>\n
\n
APIs<\/h3>\n
\n
Articles<\/h3>\n
\n
Summary<\/h2>\n
\n
\nAsk your questions in the comments below and I will do my best to answer.<\/p>\n