Advanced Documentation: NMinimize

NMinimize and NMaximize implement several algorithms for finding constrained global optima. The methods are flexible enough to cope with functions that are not differentiable or continuous, and are not easily trapped by local optima.

Keep in mind, however, that finding a global optimum can be arbitrarily difficult, even without constraints, and so the methods used may fail. It may frequently be useful to optimize the function several times with different starting conditions and take the best of the results.

Numerically finding global optima.

This finds the maximum of .

In[1]:=

Out[1]=

This finds the minimum of subject to the constraints and .

In[2]:=

Out[2]=

The constraints may be either a list or logical combination of equalities, inequalities, and domain specifications. Equalities and inequalities may be nonlinear. Any strong inequalities will be converted to weak inequalities due to limits of working with approximate numbers. Specify domains using Element—for example, Element[x, Integers] or x Integers. Currently only Integers and Reals (default) are accepted, and only variables may be given a domain. Constraints are generally enforced by adding penalties when points leave the feasible region.

Constraints can contain logical operators like And, Or, and so on.

In[3]:=

Out[3]=

Here is restricted to being an integer.

In[4]:=

Out[4]=

In order for NMinimize to work, it needs a rectangular initial region in which to start. This is similar to giving other numerical methods a starting point or starting points. The initial region is specified by giving each variable a finite upper and lower bound. This is done by including in the constraints, or x, a, b in the variables. If both are given, the bounds in the variables are used for the initial region, and the constraints are just used as constraints. If no initial region is specified for a variable , the default initial region of is used. Different variables can have initial regions defined in different ways.

Here the initial region is taken from the variables. The problem is unconstrained.

In[5]:=

Out[5]=

Here the initial region is taken from the constraints.

In[6]:=

Out[6]=

Here the initial region for is taken from the constraints, the initial region for is taken from the variables, and the initial region for is taken to be the default. The problem is unconstrained in and , but not .

In[7]:=

Out[7]=

NMinimize options.

The polynomial has global minima at NelderMead finds one of the minima.

In[8]:=

Out[8]=

We can find the other minimum by using a different RandomSeed.

In[9]:=

Out[9]=

NMinimize and NMaximize have several optimization methods available: Automatic, DifferentialEvolution, NelderMead, RandomSearch, and SimulatedAnnealing. The optimization method is controlled by the Method option, which either takes the method as a string, or takes a list whose first element is the method as a string and whose remaining elements are method-specific options. All method-specific option left-hand sides should also be given as strings.

The following function has a large number of local minima.

In[10]:=

Out[12]=

Here we use RandomSearch.

In[13]:=

Out[13]=

Here we use RandomSearch with more starting points and find the global minimum.

In[14]:=

Out[14]=

Automatic

With MethodAutomatic, NMinimize picks which method to use based on the type of problem. If the objective function and constraints are linear, LinearProgramming is used. If there are integer variables, or if the head of the objective function is not a numeric function, DifferentialEvolution is used. For everything else, it uses NelderMead, and if NelderMead does poorly, it tries DifferentialEvolution.

This is a ContourPlot of a function in two variables over the unit disk.

In[15]:=

Out[17]=

Here we minimize the function inside the unit disk using NMinimize.

In[18]:=

Out[18]=

Here we minimize the function inside the unit disk using Minimize.

In[19]:=

Out[19]=

The Minimize answer is numerically the same as the NMinimize answer.

In[20]:=

Out[20]=

DifferentialEvolution

DifferentialEvolution is a genetic algorithm that maintains a population of specimens, , represented as vectors of real numbers ("genes"). Every iteration, each chooses random integers , , and and constructs the mate , where is the value of ScalingFactor. Then is mated with according to the value of CrossProbability, giving us the child . At this point competes against for the position of in the population. The default value of SearchPoints is Automatic, which is Min[10*d, 50], where is the number of variables.

DifferentialEvolution is quite robust, but generally slower than other methods due to the relatively large set of points it maintains.

Here we minimize the function inside the unit disk using DifferentialEvolution.

In[21]:=

Out[21]=

DifferentialEvolution specific options.

The following constrained optimization problem has a global minimum of .

In[22]:=Clear[f,c,v,x1,x2,y1,y2,y3]

In[23]:=

With the default settings for DifferentialEvolution, we get an unsatisfactory solution.

In[26]:=

Out[26]=

By adjusting ScalingFactor, we get a much better result. In this case, the increased ScalingFactor gives DifferentialEvolution better mobility with respect to the integer variables.

In[27]:=

Out[27]=

NelderMead

NelderMead is an implementation of the Nelder-Mead simplex algorithm. For simplicity, we assume here that minimization is being done. We start with the highest vertex, , of a simplex, and reflect it across the centroid, , of the remaining points to a new point, , such that equals the ReflectRatio.

If is lower than all other vertices, we expand reflection by finding the point such that equals the ExpandRatio. Then the lower of and replaces in the simplex and the process starts over.

If is lower than the highest vertex but not lower than the lowest vertex, replaces and the process starts over.

Finally, if is the highest vertex, we construct so that equals the ContractRatio. If is lower than , we replace with and start over; otherwise, we move each of the simplex vertices, , toward the lowest vertex , giving new vertices, , where matches the value of ShrinkRatio, and start over.

Here we minimize the function inside the unit disk using NelderMead.

In[28]:=

Out[28]=

NelderMead specific options.

Here is a function with several local minima that are all different depths and are generally difficult to optimize.

In[29]:=

With the default parameters, NelderMead is too easily trapped in a local minimum.

In[30]:=

By using settings that are more aggressive and less likely to make the simplex smaller, we get better results.

In[31]:=

RandomSearch

RandomSearch is a simple method that generates a large set of points and uses each one as the starting point for FindMinimum. Since FindMinimum does not allow constraints, a modified objective function is used. The default value of SearchPoints is Automatic, which is Min[10*d, 100], where is the number of variables.

RandomSearch is fast, but does not scale very well with the dimension of the search space. It also suffers from many of the same limitations as FindMinimum. It is not well suited for discrete problems and others where derivatives or secants give little useful information about the problem.

Here we minimize the function inside the unit disk using RandomSearch.

In[32]:=

Out[32]=

RandomSearch specific options.

Here again is a function with several local minima that are all different depths and are generally difficult to optimize.

In[33]:=

With the default number of SearchPoints, we sometimes do not find the minimum.

In[37]:=

By using many more SearchPoints, we get better answers.

In[38]:=

Here we generate points on a grid for use as initial points.

In[39]:=

Out[39]=

SimulatedAnnealing

SimulatedAnnealing is an implementation of a biased random-walk search method. It generates a random set of starting points, and for each starting point picks a random direction in which to move. If the move is a better point, it is accepted. If the move is not a better point, we calculate a probability and compare it to a random value , and if we accept the new point despite it not being an improvement. The probability is given by where is the function defined by BoltzmannExponent, is the current iteration, is the change in objective function value, and is the value of the objective function from the previous iteration. For each starting point, this is repeated until the maximum number of iterations is reached, the method converges to a point, or the method stays at the same point consecutively for the number of iterations given by LevelIterations. When BoltzmannExponentAutomatic, the function used is Function[i, df, f0, -df*Log[i+1] / 10]. The default value of SearchPoints is Automatic, which is Min[2*d, 50], where is the number of variables.

SimulatedAnnealing is generally a bit faster than DifferentialEvolution but may not do as well on some problems.

Here we minimize a function in two variables using SimulatedAnnealing.

In[40]:=

Out[40]=

SimulatedAnnealing specific options.

Here is a function with many local minima.

In[41]:=

By default, the step size for SimulatedAnnealing is not large enough to escape from the local minima.

In[44]:=

Out[44]=

By increasing the PerturbationScale, we take larger step sizes and find a much better solution.

In[45]:=

Out[45]=

Here BoltzmannExponent is set to use an exponential cooling function, which gives faster convergence. (Note that the modified PerturbationScale is still being used as well.)

In[46]:=

Out[46]=