Numerical Nonlinear Global Optimization

Numerical algorithms for constrained nonlinear optimization can be broadly categorized into gradient-based methods and direct search methods. Gradient-based methods use first derivatives (gradients) or second derivatives (Hessians). Examples are the sequential quadratic programming (SQP) method, the augmented Lagrangian method, and the (nonlinear) interior point method. Direct search methods do not use derivative information. Examples are Nelder-Mead, genetic algorithm and differential evolution, and simulated annealing. Direct search methods tend to converge more slowly, but can be more tolerant to the presence of noise in the function and constraints.

Typically, algorithms only build up a local model of the problems. Furthermore, many such algorithms insist on certain decrease of the objective function, or decrease of a merit function which is a combination of the objective and constraints, to ensure convergence of the iterative process. Such algorithms will, if convergent, only find local optima, and are called local optimization algorithms. In Mathematica local optimization problems can be solved using FindMinimum.

Global optimization algorithms, on the other hand, attempt to find the global optimum, typically by allowing decrease as well as increase of the objective/merit function. Such algorithms are usually computationally more expensive. Global optimization problems can be solved exactly using Minimize or numerically using NMinimize.

This solves a nonlinear programming problem,

using Minimize,which gives an exact solution

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.

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.

The constraints to NMinimize and NMaximize may be either a list or a 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 the limits of working with approximate numbers. Specify a domain for a variable using Element, for example, Element[x, Integers] or xIntegers. Variables must be either integers or real numbers, and will be assumed to be real numbers unless specified otherwise. Constraints are generally enforced by adding penalties when points leave the feasible region.

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 a≤x≤b 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 x, the default initial region of -1≤x≤1 is used. Different variables can have initial regions defined in different ways.

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.

With the default method, 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, differential evolution is used. For everything else, it uses Nelder-Mead, but if Nelder-Mead does poorly, it switches to differential evolution.

Because the methods used by NMinimize may not improve every iteration, convergence is only checked after several iterations have occurred.

The Nelder-Mead method is a direct search method. For a function of n variables, the algorithm maintains a set of n+1 points forming the vertices of a polytope in n-dimensional space. This method is often termed the "simplex" method, which should not be confused with the well-known simplex method for linear programming.

At each iteration, n+1 points x₁, x₂, ..., x_n+1 form a polytope. The points are ordered so that f (x₁)≤f (x₂)≤...≤f (x_n+1). A new point is then generated to replace the worst point x_n+1.

Let c be the centroid of the polytope consisting of the best n points, . A trial point x_t is generated by reflecting the worst point through the centroid, x_t=c+ (c-x_n+1), where >0 is a parameter.

If the new point x_t is neither a new worst point nor a new best point, f (x₁)≤f (x_t)≤f (x_n), x_t replaces x_n+1.

If the new point x_t is better than the best point, f (x_t)<f (x₁), the reflection is very successful and can be carried out further to x_e=c+ (x_t-r), where >1 is a parameter to expand the polytope. If the expansion is successful, f (x_e)<f (x_t), x_e replaces x_n+1; otherwise the expansion failed, and x_t replaces x_n+1.

If the new point x_t is worse than the second worst point, f (x_t)≥f (x_n), the polytope is assumed to be too large and needs to be contracted. A new trial point is defined as

where 0<<1 is a parameter. If f (x_c)<Min (f (x_n+1), f (x_t)), the contraction is successful, and x_c replaces x_n+1. Otherwise a further contraction is carried out.

The process is assumed to have converged if the difference between the best function values in the new and old polytope, as well as the distance between the new best point and the old best point, are less than the tolerances provided by AccuracyGoal and PrecisionGoal.

Strictly speaking, Nelder-Mead is not a true global optimization algorithm; however, in practice it tends to work reasonably well for problems that do not have many local minima.

Differential evolution is a simple stochastic function minimizer.

The algorithm maintains a population of m points, {x₁, x₂, ..., x_j, ..., x_m}, where typically mn, with n being the number of variables.

During each iteration of the algorithm, a new population of m points is generated. The j^th new point is generated by picking three random points, x_u, x_v and x_w, from the old population, and forming x_s=x_w+s (x_u-x_v), where s is a real scaling factor. Then a new point x_new is constructed from x_j and x_s by taking the i^th coordinate from x_s with probability and otherwise taking the coordinate from x_j. If f (x_new)<f (x_j), then x_new replaces x_j in the population. The probability is controlled by the "CrossProbability" option.

The process is assumed to have converged if the difference between the best function values in the new and old populations, as well as the distance between the new best point and the old best point, are less than the tolerances provided by AccuracyGoal and PrecisionGoal.

The differential evolution method is computationally expensive, but is relatively robust and tends to work well for problems that have more local minima.

Simulated annealing is a simple stochastic function minimizer. It is motivated from the physical process of annealing, where a metal object is heated to a high temperature and allowed to cool slowly. The process allows the atomic structure of the metal to settle to a lower energy state, thus becoming a tougher metal. Using optimization terminology, annealing allows the structure to escape from a local minimum, and to explore and settle on a better, hopefully global, minimum.

At each iteration, a new point, x_new, is generated in the neighborhood of the current point, x. The radius of the neighborhood decreases with each iteration. The best point found so far, x_best, is also tracked.

If f (x_new)≤f (x_best), x_new replaces x_best and x. Otherwise, x_new replaces x with a probability e^{b (i, ⁢f , f₀)}. Here b is the function defined by BoltzmannExponent, i is the current iteration, ⁢f is the change in the objective function value, and f₀ is the value of the objective function from the previous iteration. The default function for b is .

Like the RandomSearch method, SimulatedAnnealing uses multiple starting points, and finds an optimum starting from each of them.

The default number of starting points, given by the option SearchPoints, is min (2 d, 50), where d is the number of variables.

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.

The random search algorithm works by generating a population of random starting points and uses a local optimization method from each of the starting points to converge to a local minimum. The best local minimum is chosen to be the solution.

The possible local search methods are Automatic and "InteriorPoint". The default method is Automatic, which uses FindMinimum with unconstrained methods applied to a system with penalty terms added for the constraints. When Method is set to "InteriorPoint", a nonlinear interior-point method is used.

The default number of starting points, given by the option SearchPoints, is min (10 d, 100), where d is the number of variables.

Convergence for RandomSearch is determined by convergence of the local method for each starting point.

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.