PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Linas Stripinis, Remigijus Paulavičius

arXiv:2609.09796v1cs.LGmath.NA

TL;DR

DIRECT-type algorithms can be slow as dimensionality increases, motivating a more effective approach for complex black-box optimization. The paper introduces X-DTC-GL, which combines surrogate-guided dynamic partitioning with selective hill-climbing, and reports improved performance across four benchmark suites. Its benefits are strongest within the evaluated benchmark scope, while effectiveness depends on objective-function properties and the quality of the minimum estimate.

  • Problem

    DIRECT-type algorithms are effective mainly for lower-dimensional problems but suffer slow convergence as dimensionality increases, limiting their use on more complex black-box optimization tasks.

  • Method

    X-DTC-GL combines local one-dimensional surrogate models for dynamic partitioning with selective hill-climbing in promising hyper-rectangles.

  • Results

    X-DTC-GL outperforms relevant DIRECT-type baselines across four benchmark suites in solution quality, evaluation efficiency, and execution time.

  • Takeaways & Limitations

    The results strengthen the competitiveness of partition-based DIRECT-type methods for box-constrained black-box optimization.

  • Takeaways & Limitations

    The benefits of hybridization and dynamic partitioning depend on objective-function properties, and local solvers can add overhead without improving solution quality.

Abstract

from arXiv · show

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.

1. Introduction

X-DTC-GL addresses the slow convergence of DIRECT-type algorithms as dimensionality increases by combining dynamic partitioning with selective hill-climbing. The paper evaluates this approach across diverse black-box optimization settings and presents it as an efficient, reproducible extension of the DIRECT framework.

  • Motivation: Black-box optimization is relevant to engineering design, machine learning, finance, and drug discovery, where objectives may be accessed only through costly evaluations.The objective may be nonlinear, non-convex, multi-modal, and non-differentiable, with no available gradient or Hessian information.
  • Motivation: DIRECT-type algorithms can converge slowly in higher dimensions because repeated trisection and global exploration increase computational cost.The convergence rate worsens linearly with dimensionality, while exploration of other hyper-rectangles adds further evaluations.
  • Contributions: X-DTC-GL introduces dynamic partitioning that uses local one-dimensional surrogate models to rapidly refine promising hyper-rectangles.The surrogate models identify promising directions and potential within hyper-rectangles.
  • Contributions: X-DTC-GL selectively applies hill-climbing to exploit promising regions identified by the surrogate models.The hybridization is intended to improve convergence while avoiding indiscriminate local search.
  • Contributions: The paper contributes a review of higher-dimensional DIRECT techniques, the X-DTC-GL algorithm, and an open-source implementation for reproducibility.The algorithm is designed to mitigate the curse of dimensionality in DIRECT-type optimization.

2. Literature review

DIRECT is a deterministic global optimization framework organized around initialization, selection, sampling, and subdivision. Its basic procedure normalizes the search region, evaluates center points, selects potentially optimal hyper-rectangles, and iteratively samples and subdivides them.

  • DIRECT framework: DIRECT repeatedly initializes, selects potentially optimal hyper-rectangles, samples them, evaluates the objective, and subdivides them.These four stages define the common framework followed by most DIRECT-type extensions.
  • Outputs: DIRECT-type methods return the best objective value and corresponding point while tracking time, iterations, and function evaluations.These quantities form the principal output and performance measures in the algorithm outline.
  • DIRECT framework: Figure 1 visualizes the selection, sampling, and subdivision process during the first iterations on a two-dimensional problem.The figure illustrates the algorithmic process rather than reporting benchmark performance.
  • Initialization: The algorithm normalizes the feasible region to a unit hyper-cube before evaluating the objective at the center point.The original decision space is retained when evaluating the objective function.

Initialization.

DIRECT maintains a partition of the normalized search space and selects potentially optimal hyper-rectangles using lower-bound estimates. Selected regions are then subdivided, while safeguards limit refinement when expected improvement or region size becomes negligible.

  • Partition representation: At iteration k, the current partition P_k contains the hyper-rectangles defining the normalized search space, and P_k+1 follows by subdividing selected regions.The index set identifies the hyper-rectangles currently belonging to the partition.
  • Selection: Potentially optimal hyper-rectangles are selected by comparing lower-bound estimates of the objective across the current partition.The definition uses center samples, hyper-rectangle measures, and the best objective value obtained so far.
  • Refinement control: The ε_DIR condition prevents excessive refinement near already identified local minima, while ε_size prevents subdivision below a minimum side length.An improvement threshold ε_imp also controls whether estimated minima justify further subdivision.
  • Selection: The selection procedure uses global and local Pareto strategies to identify promising regions for subsequent sampling and subdivision.The two-step global-local Pareto scheme is described as an effective selection strategy for complex problems.

Partitioning procedure.

DIRECT partitions selected hyper-rectangles by sampling along their longest sides and trisecting them, balancing local improvement with global exploration. Existing variants modify this procedure to reduce evaluations, but insufficient exploration can delay global discovery.

  • DIRECT samples selected POHs along their longest sides, then divides them into three equal parts while retaining the original center in the middle hyper-rectangle.
  • Partitioning schemes increasingly restrict subdivision to one longest side, but the best composition remains use-case dependent.
  • 613 function evaluations were required by original DIRECT to solve the two-dimensional linear problem within an absolute error of 10^-4.
  • 105 function evaluations reduced the original DIRECT requirement of 613 on the two-dimensional linear test problem.
  • Reducing exploration can mitigate dimensionality effects, but insufficient global search risks spending evaluations refining suboptimal solutions.

3. Description of the Proposed Approach

X-DTC-GL extends I-DTC-GL with dynamic partitioning that uses local one-dimensional surrogate models to repeatedly refine promising hyper-rectangles. Its straightforward test cases show reduced global drag and improved convergence relative to DIRECT-type counterparts, while local models may initially be inaccurate on complex multimodal problems.

  • Dynamic partitioning: Dynamic partitioning adaptively refines promising hyper-rectangles using local one-dimensional surrogate models along their least-partitioned longest sides.The predicted minimizer identifies a sub-hyper-rectangle for further subdivision.
  • Surrogate models: Quadratic and linear approximations use sampled interpolation points within a hyper-rectangle, with the linear approximation predicting greater solution improvement in the illustrated case.
  • Dynamic partitioning: Dynamic subdivision continues only when the surrogate predicts sufficient improvement and the candidate region remains above the minimum side-length threshold.
  • Examples: X-DTC-GL isolates straightforward test solutions with minimal partitions, whereas DIRECT generates approximately 99.8% more hyper-rectangles than X-DTC-GL at dimension five.
  • Limitations: Local models can be highly imprecise initially on complex multimodal problems because few samples span broad intervals.

Incorporating the hill-climber.

X-DTC-GL combines dynamic partitioning with selective hill-climbing to exploit promising regions without searching unattractive ones. The workflow initializes a solution, selects POHs, builds surrogates, partitions conditionally, and records evaluation, iteration, and runtime measures.

  • Algorithm workflow: The algorithm initializes at the center, runs a hill-climber, selects POHs, dynamically partitions them, and repeats until stopping criteria are met.
  • Algorithm workflow: Dynamic partitioning constructs a surrogate along the least-partitioned maximum side, evaluates new points, and updates the selected POH before local search.
  • Outputs: All hill-climber evaluations count toward the global evaluation counter, and the algorithm returns the best value, point, time, iterations, and evaluations.
  • Selective hill-climbing: Hill-climbing is initiated proactively in promising regions without waiting for objective improvement, while unattractive regions are excluded.

Comments on the convergence.

X-DTC-GL retains the everywhere-dense convergence reasoning of DIRECT-type methods through its POH selection scheme. Its point-wise evaluation framework assumes every queried feasible point returns a finite scalar value.

  • X-DTC-GL convergence can be proven using the same reasoning as other DIRECT-type algorithms because its selection includes at least one POH from the relevant set.
  • The framework does not require an analytic objective representation, but assumes each queried point returns a finite scalar value for comparison.

Comments on the implementation.

The evaluation used BBOB benchmarks across five dimensions and compared nine algorithmic variants, assessing performance, robustness, runtime, and limitations. X-DTC-GLQ generally performed best, while gains were not universal across problem types.

  • Component analysis: Dynamic partitioning alone could degrade baseline performance, whereas adding an initialization local search substantially improved most problem classes.The local search improves the estimate of f_min, helping dynamic partitioning guide the search more effectively.
  • Performance across problem types: X-DTC-GLQ achieved the best performance in most cases, solving the largest proportion of instances across the considered problem classes.
  • Performance across problem types: For weakly structured multi-modal problems, all variants solved approximately 65.6%–70.4% of instances, while the baseline achieved about 68% and X-DTC-GLQ about 67.2%.
  • Robustness assessment: The modified algorithms had median cross-instance variability of approximately 50×n evaluations, compared with about 550×n for I-DTC-GL.Higher quartiles and outliers were comparable across algorithms, and extreme outliers likely reflected instance difficulty.
  • Runtime assessment: Both modified variants had lower minimum, first-quartile, and median runtimes than I-DTC-GL, without noticeably increasing upper-tail wall-clock time.The added computations did not produce a noticeable runtime increase when full evaluation budgets were exhausted.
  • Limitations: The proposed extensions improved many problem classes but did not consistently outperform the baseline, and local solvers could add overhead without improving solution quality.This limitation was associated especially with non-smooth or flat functions.

Hybridization and dynamic partitioning overhead.

The Step Ellipsoidal example shows that frequent hill-climbing can impose substantial overhead on plateaued landscapes. Dynamic partitioning may initially accelerate convergence, but the baseline can eventually converge faster.

  • Hybridization overhead: On Step Ellipsoidal in dimension 10, X-DTC-GLQ was slowest because 1,902 hill-climber calls consumed 40,289 evaluations without improvement.The function has many plateaus and zero gradient almost everywhere except near the global optimum.
  • Overhead mechanism: The example indicates that hybridization and dynamic partitioning can negatively affect performance when local-search calls are repeatedly triggered on flat regions.
  • Convergence behavior: Dynamic partitioning alone initially approached the solution faster than X-DTC-GLQ, while baseline I-DTC-GL eventually achieved the fastest convergence.The surrogate captured the global quadratic trend initially but struggled after the search entered plateau regions.

Limitations of the surrogate approximation.

The study examines surrogate-guided partitioning variants and compares them with DIRECT-type methods across diverse benchmark functions. Reliable target information can substantially improve dynamic partitioning, but the true optimum is unavailable in practice.

  • Rosenbrock limitation analysis: In higher-dimensional Rosenbrock, DPQ and DPL solved the problem whereas baseline I-DTC-GL failed to reach the global solution, but both required many evaluations.The baseline was hindered by a local optimum with a large attraction basin.
  • Rosenbrock limitation analysis: Using the target value instead of f_min improved dynamic partitioning substantially on 10-dimensional Rosenbrock.DPQ(f_target) used approximately three times fewer evaluations, while DPL(f_target) required roughly twice fewer evaluations.
  • Experimental comparison: The experiments compared linear and quadratic X-DTC-GL variants with six DIRECT-type algorithms and NMSO using benchmark functions spanning differentiability, separability, multi-modality, and flatness.
  • Implementation: The local refinement stage used MATLAB fmincon with the SQP option and default configuration, subject to bound constraints and an evaluation budget.

Benchmark problems.

The study evaluates the algorithms on four benchmark suites using data and performance profiles, showing strong but budget- and suite-dependent performance for X-DTC-GL variants.

  • Solution discovery efficiency: The X-DTC-GL variants solve more instances than competing algorithms across all four data-profile subplots, although some instances remain solvable only by other methods.For BS3, six instances solved by competitors remain unsolved by X-DTC-GLQ; smaller gaps occur in BS1, BS2, and BS4.
  • Function-evaluation efficiency: The developed algorithm achieves superior performance in three of four benchmark suites, with the most wins and instances solved using the fewest function evaluations.tDIRECT outperforms both X-DTC-GL variants in BS2 and most efficiently solves one-third of its instances.
  • Overall comparisons: X-DTC-GLQ wins against X-DTC-GLL, I-DTC-GL, and DIRMIN on 29, 54, and 57 instances, respectively, despite losing on 19, 15, and 15 instances.These comparisons include all problems, including those not solved to the target accuracy.
  • Algorithm rankings: X-DTC-GL consistently achieves the highest ranking across benchmark suites, regardless of surrogate model, from approximately n×50 evaluations onward.At smaller budgets, rankings change substantially, particularly for pure DIRECT-type methods.
  • Execution time: The proposed algorithms have median execution times below one second, while I-DTC-GL, DIRMIN, and tDIRECT have medians of 7.44, 2.39, and 5.40 seconds, respectively.At least 25% of test functions are solved below one second by every algorithm; four algorithms can reach 10^4 seconds.
  • Execution-time profiles: X-DTC-GLQ and X-DTC-GLL solve approximately 17% and 16% of problems fastest, respectively, and outperform other algorithms on at least 60% within a performance ratio of six.At λ=2, both proposed algorithms achieve the highest performance levels among the methods considered.

5. Conclusions and Future Work

The paper concludes that X-DTC-GL improves DIRECT-type optimization through dynamic partitioning and hybridization, while identifying richer partitioning and adaptive local-search strategies as future directions.

  • Conclusions: X-DTC-GL enhances I-DTC-GL with dynamic partitioning and hybridization, using local surrogate models to allocate search effort toward promising hyper-rectangles.Experiments across four benchmark suites report improvements in solution quality, evaluation efficiency, and execution time over relevant alternatives.
  • Conclusions: The proposed approach strengthens the competitiveness of partition-based deterministic optimization against state-of-the-art black-box metaheuristics.This conclusion is based on the reported performance advancement over efficient DIRECT-type baselines.
  • Future work: The current method exploits local monotonicity trends but only partially addresses limited use of local trend information in DIRECT.Future refinement could target promising neighboring hyper-rectangles when surrogate indications suggest improvement beyond current boundaries.
  • Future work: Future work includes partitioning the longest side into more than three segments to provide richer samples for surrogate construction.Other suggested directions include lower-bound control and adaptive selection among local solvers for non-smooth or plateau-rich objectives.
Loading 2609.09796v1…