A more difficult problem

The Moré-Garbow-Hillstrom test suite contains some relatively difficult minimization problems. bfgsmin by itself can solve some of these problems, but not all of them, since some have multiple local minima, or completely flat regions where a gradient-based method will not be able to find a decreasing direction of search. The ''Biggs EXP6'' problem #18 is one for which bfgsmin fails to find the global minimum. This program shows how the global minimum may be found by combining an initial search that uses samin to find good starting values with refinement using bfgsmin to sharpen up the final results. The samin results from running this program, which use a fast temperature reduction and a fairly low limit on function evaluations are:


\begin{singlespace}
\texttt{NO CONVERGENCE: MAXEVALS exceeded}
\par
\texttt{Stag...
...par
\texttt{1.076916 0.000000}
\par
\texttt{1.118343 0.000000}
\end{singlespace}

Then come the BFGS iterations to sharpen up the results. The final BFGS results are:


\begin{singlespace}
\texttt{BFGSMIN intermediate results: Iteration 33}
\par
\te...
...xttt{1.0000 -0.0000 0.0000}
\par
\texttt{1.0000 0.0000 0.0000}
\end{singlespace}

An alternative which will often be faster, but is less sure to find the global minimum, is to call bfgsmin with many random starting values and a limited number of iterations. This is implemented in battery.m. You can see an example in This program. This leads to the results


\begin{singlespace}
\texttt{BFGSMIN intermediate results: Iteration 130}
\par
\t...
...xttt{1.0000 -0.0000 0.0000}
\par
\texttt{1.0000 0.0000 0.0000}
\end{singlespace}

The minimum is found correctly, and you can see that the problem is not identified.

Søren Hauberg 2008-04-29