1 |
A simplicial homology algorithm for Lipschitz optimisationEndres, Stefan January 2017 (has links)
The simplicial homology global optimisation (SHGO) algorithm is a general purpose
global optimisation algorithm based on applications of simplicial integral homology and
combinatorial topology. SHGO approximates the homology groups of a complex built on
a hypersurface homeomorphic to a complex on the objective function. This provides both
approximations of locally convex subdomains in the search space through Sperner's lemma
(Sperner, 1928) and a useful visual tool for characterising and e ciently solving higher
dimensional black and grey box optimisation problems. This complex is built up using
sampling points within the feasible search space as vertices. The algorithm is specialised
in nding all the local minima of an objective function with expensive function evaluations
e ciently which is especially suitable to applications such as energy landscape exploration.
SHGO was initially developed as an improvement on the topographical global
optimisation (TGO) method rst proposed by T orn (1986; 1990; 1992). It is proven that
the SHGO algorithm will always outperform TGO on function evaluations if the objective
function is Lipschitz smooth. In this dissertation SHGO is applied to non-convex problems
with linear and box constraints with bounds placed on the variables. Numerical experiments
on linearly constrained test problems show that SHGO gives competitive results
compared to TGO and the recently developed Lc-DISIMPL algorithm (Paulavi cius and
Zilinskas, 2016) as well as the PSwarm and DIRECT-L1 algorithms. Furthermore SHGO
is compared with the TGO, basinhopping (BH) and di erential evolution (DE) global
optimisation algorithms over a large selection of black-box problems with bounds placed
on the variables from the SciPy (Jones, Oliphant, Peterson, et al., 2001{) benchmarking
test suite. A Python implementation of the SHGO and TGO algorithms published under
a MIT license can be found from https://bitbucket.org/upiamcompthermo/shgo/. / Dissertation (MEng)--University of Pretoria, 2017. / Chemical Engineering / MEng / Unrestricted
|
Page generated in 0.0216 seconds