The Tomlab solver glbSolve.m solves box-bounded
global optimization problems using only function values. The algorithm
implemented is an improved version of the Jones et al. DIRECT algorithm.
In comparative tests glbSolve.m has shown to perform very well on
standard test problems. The Applied Optimization and Modeling group (TOM)
freely distributes an early version of glbSolve.m, written in pure
Matlab code as a stand-alone version called gblSolve.m. The current
Tomlab version is more efficient implementation, as seen in the
CPU time test below. The difference is more striking, the more function
evaluations are needed. This is especially important if accuracy is needed
or the dimension of the problem is larger.
Comparison between the Tomlab version and the free version of glbSolve
The tests are made on a Dell Dimension 733 MHz running Matlab 6.0.0.
All problems are part of the standard Tomlab distribution.
The Problem Number is the corresponding Tomlab test problem number
in the file glb_prob.m.
The solvers are running until the global optimum is found with
relative accuracy 1E-5 or the number of iterations have reached 500.
The timings include a one line per iteration printout.
Test of glbFast and glcFast, new Fortran Mex versions of glbSolve and glcSolve
The test also shows the results
for the new Tomlab solver glbFast,
which is a Fortran MEX implementation of
glbSolve.m. It is order of magnitude faster.
The results for
glcFast, the Fortran MEX version of
glcSolve, are also shown.
They solve constrained global optimization problems, but
because of a slight change in the DIRECT algorithm, they
might be faster for box-bounded problems without constraints.
This is often seen for higher dimensional problems.
Note that the fastest way to solve the test problems is to use
||Number of variables
||Number of function evaluations
||Number of iterations
||Time in seconds
||Time in seconds
glbSolve implements the algorithm DIRECT by D. R. Jones,
C. D. Perttunen and B. E. Stuckman presented in the paper
Lipschitzian Optimization Without the Lipschitz Constant,
JOTA Vol. 79, No. 1, October 1993.
glbSolve is using the algorithm conhull
to return all points on the convex hull,
even redundant ones.
conhull is based on the algorithm GRAHAMSHULL,
pages 108-109 in Computational Geometry
by Franco P. Preparata and Michael Ian Shamos.