APPSPACK 4.0 : asynchronous parallel pattern search for derivative-free optimization.

Genetha A. Gray, Tamara G. Kolda2004 · DOI

TL;DR

This paper introduces APPSPACK 4.0, a software package for derivative-free optimization designed for problems where function evaluations are computationally expensive, such as simulations. It implements an asynchronous parallel pattern search algorithm that efficiently utilizes parallel computing resources without requiring gradient information, making it suitable for a wide range of complex optimization tasks.

What Problem Does This Paper Address?

Many real-world optimization problems, particularly those involving simulations (e.g., parameter estimation, thermal design, microfluidics), are characterized by objective functions that are extremely time-consuming to evaluate. Traditional optimization methods that rely on gradient information are often impractical or impossible to apply in these scenarios. Furthermore, these problems can involve a moderate number of variables, making brute-force or exhaustive search infeasible. The challenge is to develop efficient optimization algorithms that can handle these expensive, non-differentiable, or complex objective functions, especially when leveraging parallel computing resources.

Methods

APPSPACK 4.0 implements an Asynchronous Parallel Pattern Search (APPS) algorithm. This method is a type of direct search, meaning it doesn't require derivative information. The core idea is to generate a set of "trial points" around the current best-known solution, evaluate their objective function values, and then update the best solution if a better point is found.

Key aspects of the APPS algorithm and APPSPACK implementation include:

  • Asynchronous Parallelism: Unlike synchronous methods where all processors must wait for each other, APPS allows workers to evaluate points and return results independently. This is managed by an "evaluation conveyor" that handles the flow of points to and from workers.
  • Expensive Function Evaluations: The design specifically targets scenarios where function evaluations are costly. The asynchronous nature helps keep processors busy even if some evaluations take longer than others.
  • Derivative-Free: The algorithm relies solely on function values, making it applicable to non-differentiable or noisy objective functions.
  • Parallel Execution: APPSPACK can run in serial or parallel using MPI (Message Passing Interface). The parallel version is designed to distribute function evaluations across multiple processors.
  • Customizable Evaluators: Users can provide their own executables or scripts to evaluate the objective function, allowing integration with complex simulation codes. This can be done via file I/O or by creating custom evaluator classes for more direct integration.
  • Caching: To avoid redundant computations, APPSPACK includes a cache to store previously computed function values.

Datasets

Not discussed in the paper. The paper focuses on the software and algorithm itself, with examples provided for demonstration rather than as formal datasets.

Key Insights and Ideas

  • Asynchronous Parallelism for Expensive Functions: The paper highlights that asynchronous execution is particularly beneficial when function evaluations have variable costs. This prevents idle processors and maximizes computational throughput.
  • Derivative-Free Optimization's Broad Applicability: The emphasis on derivative-free methods underscores their importance for a wide range of real-world problems where gradients are unavailable, unreliable, or computationally prohibitive to obtain.
  • Flexibility through Customization: The ability to customize function evaluators and parallelization strategies makes APPSPACK adaptable to diverse problem structures and computational environments.
  • Simulation-Based Optimization is a Prime Target: The software is explicitly designed for problems where the objective function is a simulation, a common scenario in engineering and scientific research.

Key Results

The paper describes the features and usage of APPSPACK 4.0, demonstrating its capabilities through examples. While specific quantitative results are not presented as a benchmark study, the paper implies successful application in various domains:

  • Successful Applications: The authors cite applications in thermal design, parameter estimation, microfluidics, forging processes, and groundwater modeling, indicating the software's practical utility.
  • Efficiency: The asynchronous parallel approach is presented as a way to achieve efficient optimization for problems with expensive function evaluations.
  • Robustness: The derivative-free nature and handling of constraints (including through error strings) suggest robustness in challenging optimization landscapes.

Limitations and Future Work

  • Constraint Handling: While APPSPACK 4.0 supports bound constraints and can handle general linear/nonlinear constraints through customized evaluators and error strings, the authors mention that more robust methods for general constraints are under development.
  • Scalability: The paper focuses on the algorithm and its implementation. While it supports parallel execution, the ultimate scalability for extremely large numbers of processors or variables is not deeply explored in this document.
  • Theoretical Convergence: The paper mentions that APPS is provably convergent if the objective function is suitably smooth, but the practical implications of this for non-smooth or noisy functions are not extensively detailed.
  • Future Work: The authors indicate ongoing work on more robust general constraint handling and suggest that the software is designed to be easily extensible and customizable for future developments.

Summary updated

Abstract

APPSPACK is software for solving unconstrained and bound constrained optimization problems. It implements an asynchronous parallel pattern search method that has been specifically designed for problems characterized by expensive function evaluations. Using APPSPACK to solve optimization problems has several advantages: No derivative information is needed; the procedure for evaluating the objective function can be executed via a separate program or script; the code can be run in serial or parallel, regardless of whether or not the function evaluation itself is parallel; and the software is freely available. We describe the underlying algorithm, data structures, and features of APPSPACK version 4.0 as well as how to use and customize the software.
BibTeX
@misc{gray2004appspack,
  author = {Genetha A. Gray and Tamara G. Kolda},
  title = {{APPSPACK 4.0 : asynchronous parallel pattern search for derivative-free optimization.}},
  year = {2004},
  doi = {10.2172/974891},
}
Figure