UnconstrainedProblems Package

The package Optimization`UnconstrainedProblems` provides problems from the well-known test suite described in [MGH81], as well as some utilities for displaying data about searches for FindMinimum and FindRoot.

Plotting Search Data

The utility functions FindMinimumPlot and FindRootPlot show search data for FindMinimum and FindRoot for one- and two-dimensional functions. They work with the essentially same arguments as FindMinimum and FindRoot except that they additionally take options, which affect the graphics functions they call to provide the plots, and they do not have the HoldAll attribute as do FindMinimum and FindRoot.

Note that to simplify processing and reduce possible confusion about the function f, FindRootPlot does not accept equations; it finds a root f = 0.

Steps and evaluation points are color coded for easy detection as follows:

Steps are shown with blue lines and blue points.

Function evaluations are shown with green points.

Gradient evaluations are shown with red points.

Hessian evaluations are shown with cyan points.

Residual function evaluations are shown with yellow points.

Jacobian evaluations are shown with purple points.

The search termination is shown with a large black point.

FindMinimumPlot and FindRootPlot return a list containing {result, summary, plot}, where result is the result of FindMinimum or FindRoot. summary is a list of rules showing the numbers of steps and evaluations of the function and its derivatives. plot is the graphics object shown.

This shows in two dimensions the steps and evaluations used by FindMinimum to find a local minimum of the function Cos[x^2-3y]+Sin[x^2+y^2] starting at the point {x,y} = {1,1}. Options are given to ContourPlot so that no contour lines are shown and the function value is indicated by greyscale. Since FindMinimum by default uses the quasi-Newton method, there are only evaluations of the function and gradient that occur at the same points, indicated by the red circles with green centers.

In[1]:=

This shows in two dimensions the steps and evaluations used by FindMinimum to find a local minimum of the function starting at the point {x,y} = {1,1}. Since the problem is a sum of squares, FindMinimum by default uses the Gauss-Newton Levenberg-Marquardt method that derives a residual function and only evaluates it and its Jacobian. Points at which the residual function is evaluated are shown with yellow dots. Where the yellow dots are surrounded by a large purple circle, are points at which the Jacobian was evaluated as well.

In[2]:=

This shows in two dimensions the steps and evaluations used by FindMinimum to find a local minimum of the function starting at the point {x,y} = {1,1} using Newton's method. Points at which the function, gradient, and Hessian were all evaluated are shown by concentric green, red, and cyan circles. Note that in this example, all of the Newton steps satisfied the Wolfe conditions, so there were no points where the function and gradient were evaluated separately from the Hessian, which is not always the case. Note also that Newton's method finds a different local minimum than the default method.

In[3]:=

This shows the steps and evaluations used by FindMinimum to find a local minimum of the function with two starting values superimposed on the plot of the function. Options are given to Plot so that the curve representing the function is thick and purple. With two starting values, FindMinimum uses the derivative-free principal axis method, so there are only function evaluations, indicated by the green dots.

In[4]:=

This shows in two dimensions the steps and evaluations used by FindRoot to find a root of the function {} = {0,0} starting at the point {x,y} = {1,1}. As described earlier, the function is a residual, and the default method in FindRoot evaluates the residual and its Jacobian as shown by the yellow dots and purple circles. Note that this plot is nearly the same as the one produced by FindMinimumPlot with the default method for the function since the residual is the same. FindRootPlot also shows the zero contour of each component of the residual function in red and green.

In[5]:=

Test Problems

All of the test problems presented in [MGH81] have been coded into Mathematica in the Optimization`UnconstrainedProblems` package. A data structure is used so that the problems can be processed for solution and testing with FindMinimum and FindRoot in a seamless way. The lists of problems for FindMinimum and FindRoot are in $FindMinimumProblems and $FindRootProblems respectively, and a problem can be accessed using GetFindMinimumProblem and GetFindRootProblem.

GetFindMinimumProblem and GetFindRootProblem both pass options to be used by other commands. They also accept the option Variables->vars which is used to specify what variables to use for the problems.

This gets the Beale problem in a FindMinimumProblem data structure.

In[6]:=

Out[6]=

This gets Powell's singular function problem in a FindRootProblem data structure.

In[7]:=

Out[7]=

Once you have a FindMinimumProblem or FindRootProblem object, in addition to simply solving the problem, there are various tests that you can run.

Operations with FindMinimumProblem and FindRootProblem data objects.

Any of the previous commands shown can take options that are passed on directly to FindMinimum or FindRoot and override any options for these functions which may have been specified when the problem was set up.

This uses FindRoot to solve the Powell singular function problem and gives the root.

In[8]:=

Out[8]=

This does the same as above, but includes statistics on steps and evaluations required.

In[9]:=

Out[9]=

This uses FindMinimum to solve the Beale problem and averages the timing over several trials to get an average time it takes to solve the problem.

In[10]:=

Out[10]=

This uses FindMinimum to solve the Beale problem, compares the result with a reference solution, and gives a list of rules indicating the results of the test.

In[11]:=

Out[11]=

ProblemTest gives a way to easily compare two different methods for the same problem.

This uses FindMinimum to solve the Beale problem using Newton's method, compares the result with a reference solution, and gives a list of rules indicating the results of the test.

In[12]:=

Out[12]=

Most of the rules returned by these functions are self-explanatory, but a few require some description. Here is a table clarifying those rules.

A very useful comparison is to see how a list of methods do on a particular problem. This is easy to do by setting up a FindMinimumProblem object and mapping a problem test over a list of methods.

This gets the Chebyquad problem. The output has been abbreviated to save space.

In[13]:=

Out[13]//Short=

Here is a list of possible methods.

In[14]:=

This makes a table comparing the different methods in terms of accuracy and computation time.

In[15]:=

Out[15]//TableForm=

It is possible to generate tables of how a particular method does on a variety of problems by mapping over the names in $FindMinimumProblems or $FindRootProblems.

This sets up a function that tests a problem with FindMinimum using its default settings except with a large setting for MaxIterations so that the default (Levenberg-Marquardt) method can run to convergence.

In[16]:=

This makes a table showing some of the results from testing all of the problems in $FindMinimumProblems. It may take several minutes to run.

In[17]:=

Out[17]//TableForm=

The two cases where the spatial accuracy is shown as ERROR are for linear problems, which do not have an isolated minimizer. The one case, which has a spatial accuracy that is quite poor has multiple minimizers, and the method goes to a different minimum than the reference one. Many of these functions have multiple local minima, so be aware that the error may be reported as large only because a method went to a different minimum than the reference one.