A Comparison of Stochastic Methods for Global Optimization


Deutsche Version
This page conains some results of my diploma-thesis (ps.gz, 991K) entitled "Vergleich Stochastischer Verfahren zur Globalen Optimierung".

A substantial part of the work was the test of programs. All tests were performed with a maximum of 20000 function evaluations.
The tables given below contain not the genuine function values f, but modified f ':

f ' = (f - f*) / (fm- f* )

f* is the best function value of a specific testfunction calculated by any program. fm is defined, as by each program the median of all function evaluations of the current test problem is calculatet and then the median of this mediane is determined.

This table contains the best function values found after 1000, 2500, 5000, 10000 and 20000 evaluations. The best function values found (of a test problem) have been underlined. Not all programs always achieved the necessary number of function evaluations; In this case the best value found by the program is given in the table.
The following two links show tables, subject to the following abort criterion:

fk is the best function value found after at most k function evaluations.

q = p * (fk'' - fk' ) / (fk' - fk )
q estimates the progress which can be expected, whereby p was found with the help of the least square-method. k, k' and k'' are three successive values of following shape: k = 20000 / 2s
First a program optimizes, until k function evaluations were made. Then it is checked whether q < 1 applies. In this case, then the program is aborted and the best found function value is output. Otherwise the program optimizes until the number of function evaluations reaches the next label k (s is reduced by one).
This process is repeated until q < 1 or another abort criterion is satisfied.
Each Program performed at least 156 function evaluations to produce this table . The least square-method was applied with a smallest label of k'' = 20000 / 211.
Each Program performed at least 312 function evaluations to produce this table . The least square-method was applied with a smallest label of k'' = 20000 / 29.
In both cases the best function value found (all programs in addition with the abort condition) are underlined. If a program would have still further-minimized after 20000 function evaluations, this is characterized by an asterisk.
Because of the modification one can identify the best function values at all (all programs / without abort condition) within these two tables by the entry "0".

I also expandet a table showing some results on the testset of Dixon and Szegö originally published by Neumaier and Huyer. Shown are the number of evaluations needet to approximate a global optimum with a relative error of .01% (12000 evaluations maximum).

Here is a short
description of the test functions , a position table of the functions representing the difficulty to optimize them, and the following link leads to a descripton of the
tested programs (including further links).

The page of Arnold Neumaier on global optimization -- Global Optimization (Arnold Neumaier) -- contains still much further information about this topic.

vpk@mat.univie.ac.at