Lipschitz-inspired \texttt{HALRECT} algorithm for derivative-free global optimization

DOI10.1007/S10898-023-01296-7arXiv2205.03015OpenAlexW4381281764MaRDI QIDQ6183089FDOQ6183089

Authors: Linas Stripinis, Remigijus Paulavičius 

Publication date: 26 January 2024

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: This article considers a box-constrained global optimization problem for Lipschitz-continuous functions with an unknown Lipschitz constant. Motivated by the famous DIRECT (DIviding RECTangles), a new HALRECT (HALving RECTangles) algorithm is introduced. A new deterministic approach combines halving (bisection) with a new multi-point sampling scheme in contrast to trisection and midpoint sampling used in the most existing DIRECT-type algorithms. A new partitioning and sampling scheme utilizes more comprehensive information about the objective function. Four different strategies of selecting potentially optimal hyper-rectangles are introduced to exploit the information about the objective function effectively. The original HALRECT algorithm and other introduced HALRECT variations (twelve in total) are tested and compared with the other twelve recently introduced DIRECT-type algorithms on $96$ box-constrained benchmark functions from DIRECTGOLib v1.1, and 96 perturbed their versions. The extensive experimental results show a very promising performance compared to state-of-the-art DIRECT-type global optimization. New HALRECT approaches offers high robustness across problems of different degrees of complexity, varying from simple - uni-modal and low dimensional to complex - multi-modal and higher dimensionality.

Full work available at URL: https://arxiv.org/abs/2205.03015

Recommendations

• Improved scheme for selection of potentially optimal hyper-rectangles in \texttt{DIRECT}
• Global optimization based on bisection of rectangles, function values at diagonals, and a set of Lipschitz constants
• Simplicial Lipschitz optimization without the Lipschitz constant
• Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants
• An empirical study of various candidate selection and partitioning techniques in the \texttt{DIRECT} framework

zbMATH Keywords

global optimizationderivative-free optimizationLipschitz optimizationsampling-based algorithm\texttt{DIRECT}-type algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Mathematical programming (90C99) Optimization problems in solid mechanics (74P99) Optimization problems in optics and electromagnetic theory (78M50)

Cites Work

• Algorithm 829
• Design and implementation of a massively parallel version of DIRECT
• A DIRECT-type approach for derivative-free constrained global optimization
• Exploiting derivative-free local searches in DIRECT-type algorithms for global optimization
• Pattern recognition and machine learning.
• A locally-biased form of the DIRECT algorithm.
• Lipschitzian optimization without the Lipschitz constant
• Global optimization with non-convex constraints. Sequential and parallel algorithms
• Global optimization in action. Continuous and Lipschitz optimization: algorithms, implementations and applications
• Introduction to global optimization
• Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants
• An approach to constrained global optimization based on exact penalty functions
• Derivative-free optimization: a review of algorithms and comparison of software implementations
• Encyclopedia of optimization. In 6 vols.
• Globally-biased disimpl algorithm for expensive global optimization
• Introduction to global optimization exploiting space-filling curves
• Title not available (Why is that?)
• An algorithm for finding the absolute extremum of a function
• A Sequential Method Seeking the Global Maximum of a Function
• Title not available (Why is that?)
• A DIRECT-based approach exploiting local minimizations for the solution of large-scale global optimization problems
• Additive scaling and the \texttt{DIRECT} algorithm
• Lipschitz and Hölder global optimization using space-filling curves
• Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives
• Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints
• Simplicial Lipschitz optimization without the Lipschitz constant
• Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Hölder constants
• Deterministic global optimization. An introduction to the diagonal approach
• Filter-based DIRECT method for constrained global optimization
• GOSH: derivative-free global optimization using multi-dimensional space-filling curves
• Comparison of deterministic and stochastic approaches to global optimization
• Global optimization based on bisection of rectangles, function values at diagonals, and a set of Lipschitz constants
• Improved scheme for selection of potentially optimal hyper-rectangles in \texttt{DIRECT}
• The DIRECT algorithm: 25 years later
• Novel local tuning techniques for speeding up one-dimensional algorithms in expensive global optimization using Lipschitz derivatives
• A new \texttt{DIRECT-GLh} algorithm for global optimization with hidden constraints
• On \texttt{MATLAB} experience in accelerating \texttt{DIRECT-GLce} algorithm for constrained global optimization through dynamic data structures and parallelization
• Numerical methods using two different approximations of space-filling curves for black-box global optimization
• An empirical study of various candidate selection and partitioning techniques in the \texttt{DIRECT} framework

This page was built for publication: Lipschitz-inspired \texttt{HALRECT} algorithm for derivative-free global optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183089)