Black Box Optimization with Data Analysis
by Kevin Kofler
This page presents an algorithm solving black box global optimization problems
using mainly methods from data analysis and an implementation of this algorithm.
As documentation, you may download a copy of the thesis.
The main goal of my thesis was to cross the barrier between the fields of
optimization and data analysis by applying methods from data analysis to
optimization problems. In particular, I applied data analysis techniques to
obtain information about black box functions, i.e. functions for which we do
not know an algebraic expression.
I presented both an algorithm and a reference implementation to solve
optimization problems where:
- both the objective function and the constraints may be black box
functions,
- we do not have any gradient or Hessian information for those black box
functions,
- the functions are assumed to be expensive to compute, thus the number of
function evaluations shall be kept as small as possible,
using methods from data analysis:
- covariance models,
- Gaussian mixture models (GMMs) and the Expectation-Maximization (EM)
iteration and
- ratio-reject.
The algorithm is a so-called incomplete global optimizer, i.e. it attempts to
find a global solution for the optimization problem, but is unable to guarantee
globality. In fact, it cannot even guarantee always finding a local optimum, due
to the lack of gradients and any sort of global information. Despite this lack
of guarantees, the algorithm performs well in practice.
The implementation is licensed under the GNU General Public License, version 3
or later, with special exceptions allowing to link with the
third-party optimizers used.
You can cite the thesis as follows:
Kevin Kofler: Black Box Optimization with Data Analysis. Diploma thesis. Universität Wien, 2007. http://www.tigen.org/kevin.kofler/bbowda/
Please include a citation like the above if you use my work in any research paper.
Downloads:
- current source archive (release 2, in tar.xz format, recommended)
Release 2 contains some compilation fixes and some updates for new versions of dependency libraries. See the included ChangeLog file for the full list of changes.
- original source archive as documented in the thesis (in 7-Zip / p7zip format)
This version is kept for archival purposes only, please use release 2 instead!
- documentation (diploma thesis) (The thesis is in English, only the title page contains some German.)
- preprint of a journal paper version of the thesis (February 2010)