IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v72y2018i2d10.1007_s10898-018-0645-y.html
   My bibliography  Save this article

A simplicial homology algorithm for Lipschitz optimisation

Author

Listed:
  • Stefan C. Endres

    (University of Pretoria)

  • Carl Sandrock

    (University of Pretoria)

  • Walter W. Focke

    (University of Pretoria)

Abstract

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 and a useful visual tool for characterising and efficiently 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 finding all the local minima of an objective function with expensive function evaluations efficiently 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. It is proven that the SHGO algorithm will always outperform TGO on function evaluations if the objective function is Lipschitz smooth. In this paper 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 as well as the PSwarm, LGO and DIRECT-L1 algorithms. Furthermore SHGO is compared with the TGO, basinhopping (BH) and differential evolution (DE) global optimisation algorithms over a large selection of black-box problems with bounds placed on the variables from the SciPy 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/ .

Suggested Citation

  • Stefan C. Endres & Carl Sandrock & Walter W. Focke, 2018. "A simplicial homology algorithm for Lipschitz optimisation," Journal of Global Optimization, Springer, vol. 72(2), pages 181-217, October.
    • Handle: RePEc:spr:jglopt:v:72:y:2018:i:2:d:10.1007_s10898-018-0645-y
    DOI: 10.1007/s10898-018-0645-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-018-0645-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-018-0645-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Remigijus Paulavičius & Julius Žilinskas, 2014. "Simplicial Lipschitz optimization without the Lipschitz constant," Journal of Global Optimization, Springer, vol. 59(1), pages 23-40, May.
    2. Mishra, SK, 2006. "Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions," MPRA Paper 1005, University Library of Munich, Germany.
    3. J. Herskovits, 1998. "Feasible Direction Interior-Point Technique for Nonlinear Optimization," Journal of Optimization Theory and Applications, Springer, vol. 99(1), pages 121-146, October.
    4. Remigijus Paulavičius & Yaroslav Sergeyev & Dmitri Kvasov & Julius Žilinskas, 2014. "Globally-biased Disimpl algorithm for expensive global optimization," Journal of Global Optimization, Springer, vol. 59(2), pages 545-567, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lloret-Batlle, Roger & Zheng, Jianfeng, 2023. "Jam density and stopbar location estimation with trajectory data at signalized intersections," Transportation Research Part B: Methodological, Elsevier, vol. 173(C), pages 162-175.
    2. Zheng, J.H. & Liang, Z.T. & Li, Zhigang & Wang, F. & Wu, Q.H., 2023. "Online coal consumption characteristics fitting for daily economic dispatch using a data-driven hybrid sequential model," Applied Energy, Elsevier, vol. 341(C).
    3. David Hémous & Simon Lepot & Thomas Sampson & Julian Schärer, 2023. "Trade, Innovation and Optimal Patent Protection," CESifo Working Paper Series 10777, CESifo.
    4. Federico Giorgi & Stefano Herzel & Paolo Pigato, 2023. "A Reinforcement Learning Algorithm for Trading Commodities," CEIS Research Paper 552, Tor Vergata University, CEIS, revised 18 Feb 2023.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. G. Liuzzi & S. Lucidi & V. Piccialli, 2016. "Exploiting derivative-free local searches in DIRECT-type algorithms for global optimization," Computational Optimization and Applications, Springer, vol. 65(2), pages 449-475, November.
    2. Jonas Mockus & Remigijus Paulavičius & Dainius Rusakevičius & Dmitrij Šešok & Julius Žilinskas, 2017. "Application of Reduced-set Pareto-Lipschitzian Optimization to truss optimization," Journal of Global Optimization, Springer, vol. 67(1), pages 425-450, January.
    3. Albertas Gimbutas & Antanas Žilinskas, 2018. "An algorithm of simplicial Lipschitz optimization with the bi-criteria selection of simplices for the bi-section," Journal of Global Optimization, Springer, vol. 71(1), pages 115-127, May.
    4. Linas Stripinis & Remigijus Paulavičius, 2023. "Novel Algorithm for Linearly Constrained Derivative Free Global Optimization of Lipschitz Functions," Mathematics, MDPI, vol. 11(13), pages 1-19, June.
    5. Nazih-Eddine Belkacem & Lakhdar Chiter & Mohammed Louaked, 2024. "A Novel Approach to Enhance DIRECT -Type Algorithms for Hyper-Rectangle Identification," Mathematics, MDPI, vol. 12(2), pages 1-24, January.
    6. Donald R. Jones & Joaquim R. R. A. Martins, 2021. "The DIRECT algorithm: 25 years Later," Journal of Global Optimization, Springer, vol. 79(3), pages 521-566, March.
    7. S. K. Mishra, 2010. "(Computer Algorithms) The Most Representative Composite Rank Ordering of Multi-Attribute Objects by the Particle Swarm Optimization Method," Journal of Quantitative Economics, The Indian Econometric Society, vol. 8(2), pages 165-200.
    8. Keliang Wang & Leonardo Lozano & Carlos Cardonha & David Bergman, 2023. "Optimizing over an Ensemble of Trained Neural Networks," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 652-674, May.
    9. Grigori Chapiro & Angel E. R. Gutierrez & José Herskovits & Sandro R. Mazorche & Weslley S. Pereira, 2016. "Numerical Solution of a Class of Moving Boundary Problems with a Nonlinear Complementarity Approach," Journal of Optimization Theory and Applications, Springer, vol. 168(2), pages 534-550, February.
    10. Rudolf Scitovski, 2017. "A new global optimization method for a symmetric Lipschitz continuous function and the application to searching for a globally optimal partition of a one-dimensional set," Journal of Global Optimization, Springer, vol. 68(4), pages 713-727, August.
    11. Rudolf Scitovski & Kristian Sabo, 2019. "Application of the DIRECT algorithm to searching for an optimal k-partition of the set $$\mathcal {A}\subset \mathbb {R}^n$$ A ⊂ R n and its application to the multiple circle detection problem," Journal of Global Optimization, Springer, vol. 74(1), pages 63-77, May.
    12. SK Mishra, 2007. "Estimation of Zellner-Revankar Production Function Revisited," Economics Bulletin, AccessEcon, vol. 3(14), pages 1-7.
    13. Mishra, SK, 2012. "Construction of Pena’s DP2-based ordinal synthetic indicator when partial indicators are rank scores," MPRA Paper 39088, University Library of Munich, Germany.
    14. Konstantin Barkalov & Roman Strongin, 2018. "Solving a set of global optimization problems by the parallel technique with uniform convergence," Journal of Global Optimization, Springer, vol. 71(1), pages 21-36, May.
    15. S K Mishra, 2007. "Globalization and Structural Changes in the Indian Industrial Sector: An Analysis of Production Functions," The IUP Journal of Managerial Economics, IUP Publications, vol. 0(4), pages 56-81, November.
    16. E. F. Campana & M. Diez & G. Liuzzi & S. Lucidi & R. Pellegrini & V. Piccialli & F. Rinaldi & A. Serani, 2018. "A multi-objective DIRECT algorithm for ship hull optimization," Computational Optimization and Applications, Springer, vol. 71(1), pages 53-72, September.
    17. Christopher M. Cotnoir & Balša Terzić, 2017. "Decoupling linear and nonlinear regimes: an evaluation of efficiency for nonlinear multidimensional optimization," Journal of Global Optimization, Springer, vol. 68(3), pages 663-675, July.
    18. Mickaël Binois & David Ginsbourger & Olivier Roustant, 2020. "On the choice of the low-dimensional domain for global optimization via random embeddings," Journal of Global Optimization, Springer, vol. 76(1), pages 69-90, January.
    19. Yaroslav D. Sergeyev & Marat S. Mukhametzhanov & Dmitri E. Kvasov & Daniela Lera, 2016. "Derivative-Free Local Tuning and Local Improvement Techniques Embedded in the Univariate Global Optimization," Journal of Optimization Theory and Applications, Springer, vol. 171(1), pages 186-208, October.
    20. Remigijus Paulavičius & Yaroslav Sergeyev & Dmitri Kvasov & Julius Žilinskas, 2014. "Globally-biased Disimpl algorithm for expensive global optimization," Journal of Global Optimization, Springer, vol. 59(2), pages 545-567, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:72:y:2018:i:2:d:10.1007_s10898-018-0645-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.