New optimization method speeds up medium-scale black-box searches
A practical DIRECT-type algorithm for medium-scale black-box global optimization
Machine Learning
Summary
Finding the best solution when you can’t see inside the system can be slow, especially when the problem involves many factors. The authors designed a method that smartly breaks down the search space and combines it with focused local improvements. Their approach finds better answers faster than older methods on a variety of test problems. This makes it more practical for complex optimization tasks where guessing and checking take too long.
What this means in practice
- •For machine learning engineers: Optimize hyperparameters of models where evaluation is costly and gradient information is unavailable, improving training efficiency and model performance.
- •For engineering design teams: Enhance design optimization tasks with complex simulations by reducing the time to find high-quality solutions.
Authors
Linas Stripinis, Remigijus Paulavičius
Abstract
The DIRECT algorithm is a deterministic global optimization method known for its versatility and balanced exploration-exploitation strategy. However, DIRECT-type algorithms are primarily effective for low-dimensional problems and often exhibit slow convergence as dimensionality increases, limiting their applicability to more complex optimization tasks. To address this limitation, this paper introduces X-DTC-GL, a novel DIRECT-type algorithm that incorporates dynamic partitioning and hybridization techniques. The dynamic partitioning approach adaptively refines the search space based on local one-dimensional surrogate models, enabling rapid subdivision of promising hyper-rectangles. The hybridization strategy selectively employs a hill-climbing method to exploit promising regions identified by the surrogate models. Extensive experiments on four diverse benchmark suites demonstrate that X-DTC-GL significantly outperforms existing DIRECT-type baselines, achieving improvements of ~12% in solvability and ~27% in solution quality. Performance-profile analyses indicate the fastest convergence on up to ~40% of instances, the best runtime performance on ~17% of problems, and competitive overall execution times. By improving performance within the partition-based framework, these advances strengthen the algorithm's competitiveness in state-of-the-art black-box optimization.