HOPSPACK: Hybrid Optimization Parallel Search Package

Genetha A. Gray, Joshua Griffin, Matt Taddy, Monica Martinez-Canales, Tamara G. Kolda2008 · DOI

Abstract

HOPSPACK (Hybrid Optimization Parallel Search Package) is a software framework designed to solve complex nonlinear optimization problems by integrating multiple solvers into a single, parallelized hybrid. Utilizing an asynchronous "Mediator/Citizen" architecture, HOPSPACK prevents slow algorithms from bottlenecking the search process, allowing for the simultaneous exploitation of diverse optimization strategies. This paper details the technical framework, the integration of various derivative-free solvers, and the mechanisms for efficient parallel execution and function value caching.

Introduction

In engineering and scientific simulation, researchers frequently encounter "black-box" optimization problems where objective function derivatives are unavailable. These simulations are often computationally expensive, prone to noise, or subject to unexpected failures. No single optimization algorithm is universally optimal; global searchers excel at exploration but lack local precision, while local refiners converge quickly but are susceptible to local minima.

HOPSPACK addresses this by providing a unified platform that enables different algorithms to collaborate in parallel. By maintaining the integrity of individual solvers, the framework leverages existing, sophisticated optimization code with minimal modification, creating a "best of both worlds" approach to complex design space exploration.

Methodology: The Mediator/Citizen/Conveyor Paradigm

HOPSPACK employs a modular architecture to manage hybrid searches through three primary components:

Citizens (The Solvers)

Citizens represent individual optimization routines. The framework currently supports several distinct strategies:

  • APPSPACK (Generating Set Search): A robust, derivative-free local solver designed to handle noisy objective functions.
  • DIRECT (Dividing Rectangles): A deterministic global search algorithm that systematically partitions the search space.
  • TGP (Treed Gaussian Process): A statistical surrogate model that predicts optimal points based on historical data.
  • LHS (Latin Hypercube Sampling): A technique for generating well-distributed initial sampling points.

The Mediator

The Mediator serves as the central coordination unit. It receives trial points proposed by the various Citizens, prioritizes them according to user-defined criteria, and manages the distribution of these points for evaluation.

The Conveyor

The Conveyor facilitates parallel execution by managing a pool of processors. A critical feature of the Conveyor is the function value cache, implemented as a splay tree. This cache identifies redundant points suggested by different solvers, ensuring that expensive simulations are only performed once.

Key Technical Insights

Asynchronous Parallelism

Unlike traditional serial hybrid schemes—where one algorithm must complete before another begins—HOPSPACK operates asynchronously. Solvers run concurrently, and any improvement found by a local solver is immediately shared with the global solver, and vice versa. This real-time information exchange significantly accelerates the discovery of optimal solutions.

Handling "Orphaned" Points

A unique challenge in hybrid optimization is how a specific solver handles points generated by an external routine. HOPSPACK treats these as "orphans." Because the underlying APPSPACK solver is mathematically structured to incorporate external points without compromising its convergence guarantees, the overall hybrid remains theoretically robust.

Load Balancing

In parallel environments, load imbalance often leads to idle processors. HOPSPACK’s Mediator mitigates this by filling idle gaps with trial points from any available Citizen in the hybrid pool, maximizing CPU utilization across the high-performance computing (HPC) environment.

Applications and Results

While HOPSPACK is a general-purpose framework, its efficacy has been demonstrated across several domains, including groundwater remediation, electrical device modeling, and weapon electronics qualification.

The framework's caching mechanism has proven essential for problems where individual function evaluations take hours. Qualitatively, the hybrid approach allows the system to navigate noisy regions using robust solvers like APPSPACK until a smoother region is identified, at which point more aggressive solvers can take over to accelerate convergence.

Conclusion and Future Work

HOPSPACK represents a significant advancement in parallel optimization, offering a flexible and efficient platform for hybridizing diverse solvers. Its integration into major toolkits like Sandia’s DAKOTA underscores its utility. Future development aims to further simplify the integration of proprietary solvers and refine the Mediator's priority logic to dynamically balance global exploration and local refinement as the search progresses.

Summary updated

Abstract

In this paper, we describe the technical details of HOPSPACK (Hybrid Optimization Parallel SearchPackage), a new software platform which facilitates combining multiple optimization routines into asingle, tightly-coupled, hybrid algorithm that supports parallel function evaluations. The frameworkis designed such that existing optimization source code can be easily incorporated with minimalcode modification. By maintaining the integrity of each individual solver, the strengths and codesophistication of the original optimization package are retained and exploited.4
BibTeX
@misc{gray2008hopspack,
  author = {Genetha A. Gray and Joshua Griffin and Matt Taddy and Monica Martinez-Canales and Tamara G. Kolda},
  title = {{HOPSPACK: Hybrid Optimization Parallel Search Package}},
  year = {2008},
  doi = {10.2172/1130394},
}
Figure