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