CS Paper Radar

A practical DIRECT-type algorithm for medium-scale black-box global optimization

Linas Stripinis, Remigijus Paulavičius

cs.LG math.NA ·submitted 2026-09-09 06:48 UTC · v1
publishedbenchmarkunusual

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.

Comment
46pages, 13 figures, 4 tables
Journal ref
Applied Soft Computing, 2026, 116392
DOI
10.1016/j.asoc.2026.116392

Closest papers

Nearest neighbours by meaning across the whole index.

KT-EGO: A Knowledge Transfer Assisted Efficient Global Optimization Algorithm for Solving High-Dimensional Expensive Black-Box Problems

cs.CE cs.LG ·2026-09-28 ·Qineng Wang, Liming Song, Yun Chen, Guangjian Ma, Zhendong Guo +1 more
publishedbenchmarkhighly cited similarity 0.60
Abstract · 25 pages, 12 figures; abridged author manuscript

Many engineering problems involve optimizing a high-dimensional expensive black-box (HEB) design space. To solve such problems efficiently, we propose a knowledge transfer assisted efficient global optimization (EGO) algorithm, labeled as KT-EGO, which extends the EGO algorithm for solving problems over higher dimensions (i.e., $d>20$). Specifically, the original design space is divided into several low-dimensional subset design spaces. More importantly, in order to extract information from the subset design spaces to accelerate the progress of full optimization, we propose a surrogate-based data fusion strategy in KT-EGO. And further, a searching strategy with an adaptive variable range is devised to enhance the exploitation of promising areas. To show the effectiveness of our proposed algorithm, it is compared against the state-of-the-art algorithms over 12 benchmark functions and a 28-dimensional engineering optimization for the design of compressor blade, which fully validates the effectiveness of the KT-EGO for solving HEB problems.

0.49

EMG-Hybrid: A Dual-Engine Elite Memory--Guided Adaptive Optimization Framework for High-Dimensional Feature Selection

cs.AI ·2026-10-31 ·Saba Zare, Mohammad Taheri
similarity 0.60
Abstract

Feature selection in ultra-high-dimensional, noisy datasets remains a critical challenge due to exponential search space growth, where conventional binary metaheuristics often suffer from premature convergence. To address this, EMG-Hybrid is introduced as a novel three-level hierarchical optimization architecture designed around decoupled operational planes, feedback-driven scheduling, and isolated state refinement. At Level 1, a Dual-Engine Controller monitors population Shannon entropy and empirical fitness velocity, functioning as an architectural master-switch that dynamically routes execution between global exploration and local intensification. This control loop conditions the Level 2 active optimization plane, where an Adaptive Black Hole Gravity (ABHG) execution layer performs aggressive feature manifold pruning via a distance-decoupled penalty kernel driven by fitness similarities and Hamming metrics. To structurally isolate macro-exploration from micro-exploitation, Level 3 encapsulates an autonomous Elite Memory Archive that preserves high-fidelity sub-schemas and hosts a discrete bitwise Differential Evolution (DE) micro-refinement sandbox for resolving complex parameter epistasis. Theoretically, uniform combinatorial bounds derived via Vapnik--Chervonenkis (VC) dimension criteria demonstrate that this multi-level restriction mitigates high-dimensional overfitting. Empirical results across manifolds scaling up to $d > 100{,}000$ features, complemented by high-performance computing (HPC) profiling under lock-free atomic Compare-and-Swap (CAS) primitives, indicate strong performance gains over state-of-the-art baselines. The framework exhibits near-linear parallel speedups, sub-quadratic runtime scaling, and substantial dimensionality reduction, offering a scalable and structurally innovative paradigm for large-scale data mining.

0.21

A Dynamic Aggregation Strategy Enhanced Efficient Global Optimization Algorithm for Solving High-Dimensional Turbomachinery Design Problems

cs.LG cs.CE ·2026-09-13 ·Qineng Wang, Zhendong Guo, Yun Chen, Guangjian Ma, Liming Song +1 more
publishedbenchmark similarity 0.59
Abstract · Author manuscript updated to align core methods and results with the published article; 37 pages, 14 figures, 11 tables

In order to solve the high-dimensional ($d \geq 30$) expensive black-box problems within budget, an efficient global optimization (EGO) algorithm with a dynamic aggregation strategy is proposed, labeled as DA-EGO. Specifically, the DA-EGO decomposes the original high-dimensional design space into a set of low-dimensional subspaces for efficient surrogate-based optimization search, and the optimal solutions of subspaces are combined as an elite point for the global search. Most importantly, the subspaces are not fixed. Instead, the subspace variables are updated in each iteration, according to the variable interaction analyses in the sub- and full-spaces. The perturbation method and the analysis of variance are used to detect variable interactions. To further accelerate the optimization progress, the searching ranges of subspaces are also adaptively adjusted according to the analyses of subspace optimization results of the previous iteration. Tests on 21 benchmark instances, comprising seven functions at 30, 60, and 90 dimensions, show that DA-EGO is effective on separable and partially separable problems under a budget of 1500 function evaluations. Its advantage is case-dependent: on the non-separable shifted Rosenbrock function, GSGA performs better at 60 and 90 dimensions, while the 30-dimensional results are statistically comparable to IKAEA and GSGA. Moreover, the advantage of DA-EGO is also seen in the aerodynamic optimization of a transonic rotor blade with 28 variables as well as the compressor stage optimization with 60 variables. With the above, the effectiveness of the proposed DA-EGO has been well demonstrated.

0.48

Adaptive Partitioning Schemes for Optimistic Optimization

cs.LG stat.ML ·2026-10-02 ·Raja Sunkara, Ardhendu Tripathy
top venue similarity 0.56
Abstract · Accepted at ICML 2025

Applications such as engineering design often require us to optimize a black-box function, i.e., a system whose inner processing is not analytically known and whose gradients are not available. Practitioners often have a fixed budget for the number of function evaluations and the performance of an optimization algorithm is measured by its simple regret. In this paper, we study the class of "Optimistic Optimization" algorithms for black-box optimization that use a partitioning scheme for the domain. We develop algorithms that learn a good partitioning scheme and use flexible surrogate models such as neural networks in the optimization procedure. For multi-index functions on an $m$-dimensional subspace within $d$ dimensions, our algorithm attains $\tilde{O}(n^{-β/ d})$ regret, where $β= 1 + \frac{d-m}{2m-1}$, as opposed to $\tilde{O}(n^{-1/d})$ for SequOOL, a state-of-the-art optimistic optimization algorithm. We use our approach to improve the quality of Activation-aware Weight Quantization (AWQ) of the OPT-1.3B model, achieving $\sim10\%$ improvement in performance relative to the best possible unquantized model.

0.41

Match the Geometry Before the Surrogate: Extreme Low-Budget Optimization in High Dimensions

cs.LG stat.ML ·2026-11-06 ·Michal Průšek, Adam Novozámský, Filip Šroubek
top venuebenchmarkcode/data similarity 0.56
Abstract · NeurIPS 2026 (camera-ready). 10 pages of main text plus appendices and the NeurIPS paper checklist, 38 pages in total. Code and result files…

Low-budget molecular optimization is often framed as Bayesian optimization in a learned latent space, but standard benchmarks typically allow hundreds or thousands of evaluations, whereas a realistic wet-lab round may allow only a few dozen. We revisit this regime using a SELFIES molecular variational autoencoder (VAE) with a Gaussian prior and GuacaMol objectives at N = 30 evaluations. The main finding is not a new surrogate model, but an interaction in candidate generation. The encoder means of a reference set of molecules concentrate near a narrow spherical shell, while many high-dimensional optimizers propose candidates from boxes or box-shaped trust regions. We study a simple constraint, the on-sphere scaffold, that restricts candidate generation to this shell. We then introduce two minimal optimizers to probe what remains useful once the support is fixed. GeoWalk performs geodesic local search on the shell without a surrogate. After 30 evaluations, it shows no detected difference from a Gaussian-process (GP) surrogate on the shell, which is ahead earlier in the budget. GeoCMA adds covariance learning in a random subspace. It does not improve on GeoWalk in the molecular benchmark. On LassoBench it has a lower mean loss than GeoWalk, but full-dimensional CMA-ES remains stronger on most tasks. A factorial experiment with a single GP crosses the candidate support (shell or box) with the acquisition maximizer (a finite candidate set or a continuous optimizer). In this benchmark, shell candidates outperformed box candidates when acquisition was maximized over a candidate set, but not with continuous maximization by L-BFGS-B. These results come from a controlled study of one Gaussian-prior VAE benchmark and do not recommend VAEs for molecular optimization. The practical lesson is to control the candidate support and the acquisition maximizer before attributing a gain to the surrogate.

0.37

Coarse-to-Fine Macro Placement via Evolutionary Search and Critical Macro Tuning

cs.AR ·2026-09-28 ·Biao Liu, Zhiping Jin, Kaixuan Sun, Zengrui Lu, Qingquan Zhang +1 more
benchmarkcode/data similarity 0.56
Abstract · 18 pages

Macro placement is a critical stage in chip physical design that substantially affects downstream implementation quality. Recent search-based methods improve existing layouts through partial reconstruction, but quality-biased or spatially restricted macro selection can limit the diversity of reconstruction proposals, potentially hindering escape from local optima. Moreover, coarse-grid representations restrict placement precision. To address these challenges, we propose C2FPlace, a \textbf{C}oarse-to-\textbf{F}ine macro \textbf{Place}ment framework that integrates population-based evolutionary search with fine-grained refinement. During coarse-grained optimization, tournament selection chooses promising parents from randomly sampled groups of layouts, and stochastic partial rip-up and re-place generates offspring by sampling macro subsets across the entire layout. A two-phase schedule samples reconstruction ratios from a higher range early in the search and a lower range later, supporting broad exploration followed by more conservative refinement. During fine-grained optimization, critical macro tuning enables positional adjustments beyond the coarse grid to obtain additional half-perimeter wirelength (HPWL) reduction. Experiments on the ISPD2005 benchmark show that C2FPlace reduces HPWL by 17.82\% over EGPlace and 17.86\% over RollPlace on average. On the ICCAD2025 benchmark, C2FPlace achieves the best average ranking among the compared methods under the evaluated power, performance, and area (PPA) metrics. Our codes are available in \href{https://github.com/lxxxxb/C2FPlace}{https://github.com/lxxxxb/C2FPlace}.

0.40

Benchmarking Tabular Foundation Models as Surrogates in Expensive Evolutionary Optimization

cs.NE cs.LG ·2026-09-16 ·Lu Han, Jin Wang, Yuchen Li, Haoran Gu, Shulei Liu +3 more
similarity 0.56
Abstract

Surrogate-assisted evolutionary algorithms (SAEAs) are effective methods for solving expensive optimization problems (EOPs), where surrogate models replace most expensive evaluations and critically influence the final optimization results. In recent years, tabular foundation models have advanced rapidly, and the Tabular Prior-data Fitted Network (TabPFN) has been adopted as a surrogate model for EOPs due to its strong predictive capability, demonstrating promising performance. Motivated by its potential as a surrogate model in SAEAs, this work conducts a comprehensive study that combines extensive experiments with in-depth theoretical analysis to investigate the effectiveness of TabPFN. Specifically, we perform experiments across both offline and online SAEA settings, covering diverse problem scenarios such as single-objective, multi-objective, constrained, combinatorial, mixed-variable, and engineering optimization problems. In addition, we further analyze the advantages and limitations of TabPFN within SAEAs and provide practical guidelines for its application in different optimization settings. Results show that the effectiveness of TabPFN is highly problem dependent, and it cannot replace conventional surrogates universally. Overall, TabPFN should be adopted selectively according to data availability, landscape complexity, search space characteristics, and its role within the algorithm. Customized model management strategies and role-specific algorithm design are necessary to fully exploit its advantages and avoid its pitfalls.

0.25

The Modular CMA-ES: A Framework for Modern Evolution Strategies

cs.NE ·2026-10-07 ·Jacob de Nobel, Diederick Vermetten, Anna V. Kononova, Carola Doerr, Thomas Bäck
benchmark similarity 0.56
Abstract

Since their introduction, modern evolution strategies, such as the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), have become established as powerful methods for continuous black-box optimization. This success has led to a wide range of proposed modifications, each designed to improve performance or behavior in specific optimization scenarios. However, because these developments have largely been introduced and studied in isolation, their interactions remain comparatively underexplored. In this paper, we present the Modular CMA-ES (ModCMA), a configurable framework that integrates a wide range of mechanisms from modern evolution strategies within a single implementation. By decomposing CMA-ES into modules with interchangeable options for sampling, selection and recombination, step-size adaptation, matrix adaptation, and restarting, ModCMA enables systematic exploration of a large design space of modern evolution strategies and facilitates the construction, comparison, and automated configuration of new algorithm variants. We illustrate the benefits of this modular approach through two example studies. First, we compare several matrix-adaptation mechanisms in terms of their computational cost and optimization performance. Second, we use automated algorithm configuration to specialize ModCMA to individual benchmark problems and analyze the resulting configurations. Together, these examples demonstrate how the framework can be used both to study individual algorithmic design choices and to explore their combinations in a systematic and reproducible manner.

0.43