Asynchronous parallel generating set search for linearly-constrained optimization.

Tamara G. Kolda, Joshua Griffin, Robert M. Lewis2007 · DOI

TL;DR

This paper introduces an asynchronous parallel algorithm for derivative-free optimization problems with linear constraints, building upon the Generating Set Search (GSS) framework. By allowing parallel processors to work independently and share results as they become available, this method significantly improves efficiency and reduces runtime, especially for computationally expensive objective functions. The authors demonstrate its effectiveness on a broad range of challenging benchmark problems, achieving state-of-the-art results for derivative-free methods.

What Problem Does This Paper Address?

Many real-world optimization problems involve finding the minimum of an objective function subject to linear constraints. Derivative-free optimization methods are crucial when the gradient of the objective function is unavailable or difficult to compute. While parallel versions of these methods exist, they often suffer from load balancing issues, where processors wait for others to complete tasks, leading to underutilization. Asynchronous approaches aim to mitigate this by allowing computations to proceed as soon as results are ready. However, extending asynchronous methods to handle linear constraints introduces complexities, particularly in maintaining appropriate search directions as the algorithm progresses and the feasible region is explored. This paper specifically addresses the challenge of adapting asynchronous GSS to linearly-constrained optimization while ensuring theoretical convergence guarantees.

Methods

The core of the paper is the development and analysis of an asynchronous parallel Generating Set Search (GSS) algorithm for linearly-constrained optimization. GSS works by evaluating a set of "trial points" generated from the current best point and selecting the one that yields the greatest improvement.

Key methodological contributions include:

  • Asynchronous Execution: Unlike synchronous methods, this algorithm allows processors to continue generating and evaluating new trial points as soon as any evaluation completes, rather than waiting for all points in an iteration to be finished. This is crucial for improving parallel efficiency.
  • Handling Linear Constraints: The primary novelty lies in how the algorithm maintains a set of "conforming search directions" that are appropriate for the local feasible region, even as the algorithm explores different parts of the boundary defined by linear constraints. This involves dynamically updating these directions based on the current iterate and the active constraints.
  • Implementation Enhancements: The authors detail several practical techniques to boost performance:
  • Scaling: Variables are scaled to improve the sensitivity of the GSS method.
  • Function Value Caching: Previously computed function values are stored and reused to avoid redundant evaluations.
  • Snapping to the Boundary: Trial points are adjusted to lie exactly on the boundary when they are close, which can be important for real-world problems where constraint activation is critical.
  • Direction Caching and Augmentation: Search directions are cached to avoid recomputation, and additional directions (like constraint normals) are added to accelerate progress towards boundary points.
  • Theoretical Analysis: The paper provides a rigorous theoretical framework, proving global convergence to a first-order stationary point under mild assumptions. This analysis accounts for the asynchronous nature of the algorithm and the complexities introduced by linear constraints.

Datasets

The authors evaluated their algorithm on the CUTEr test collection, a widely used benchmark suite for optimization problems. They specifically selected all problems with general linear constraints and up to 1000 variables, totaling 119 problems. These problems were categorized into three groups based on the number of variables:

  • Small (1-10 variables): 72 problems
  • Medium (11-100 variables): 24 problems
  • Large (101-1000 variables): 23 problems

To simulate expensive objective function evaluations, artificial time delays were introduced for the CUTEr problems, making the experiments more representative of real-world scenarios.

Key Insights and Ideas

  • Asynchronous GSS is effective for linearly-constrained problems: The core insight is that the challenges of handling linear constraints in an asynchronous setting can be overcome by dynamically adapting search directions. This allows for significant performance gains over synchronous methods.
  • The "nearby boundary" is dynamic: For linearly-constrained optimization, the set of relevant constraints (and thus the search directions) can change frequently. The asynchronous nature requires managing multiple "e-tangent cones" simultaneously, which is a key theoretical and implementation challenge.
  • Practical enhancements are critical: Techniques like function value caching, variable scaling, and direction caching are not just optimizations; they are essential for achieving competitive performance on challenging problems.
  • Derivative-free methods can be competitive: The results demonstrate that derivative-free methods, when implemented efficiently and in parallel, can solve a substantial number of problems that are typically tackled by gradient-based methods.

Key Results

The asynchronous GSS algorithm, implemented in APPSPACK, demonstrated strong performance on the CUTEr test set:

  • High Success Rate: The algorithm solved:
  • 95% of problems with 10 or fewer variables.
  • 75% of problems with 11-100 variables.
  • Nearly half (48%) of problems with 101-1000 variables.
  • State-of-the-Art Performance: The authors claim these are the best results ever achieved with a derivative-free method on this benchmark set.
  • Speedup: In experiments with artificial time delays, the asynchronous approach was often faster than its synchronous counterpart, reducing overall execution time by up to 25% or more in many cases. This highlights the benefit of improved processor utilization.
  • Solution Quality: The objective values obtained by APPSPACK were comparable to those from SNOPT, a sophisticated derivative-based solver, indicating that the derivative-free method can find high-quality solutions.

Limitations and Future Work

  • Scaling Sensitivity: The authors note that GSS methods are sensitive to variable scaling. While they implemented a general scaling strategy, they acknowledge that problem-specific scaling information could further improve performance, especially for problems with widely varying variable ranges.
  • Inadequate Scaling Issues: For some larger problems where scaling information was not readily available, the algorithm struggled with feasibility checks, leading to failures. This suggests a need for more robust handling of scaling in such cases.
  • Comparison to Derivative-Based Methods: While the paper compares results to SNOPT, it's acknowledged that for problems where derivatives are available, gradient-based methods are generally preferred. The value of this work lies in its applicability where derivatives are not accessible.
  • Future Work: The authors suggest that their implementation could be beneficial for problems involving sequences of related optimization problems with the same linear constraints, such as those arising in nonlinear constraint handling. They also mention that the caching strategies could be useful in such scenarios.

Summary updated

Abstract

We describe an asynchronous parallel derivative-free algorithm for linearly-constrained optimization. Generating set search (GSS) is the basis of ourmethod. At each iteration, a GSS algorithm computes a set of search directionsand corresponding trial points and then evaluates the objective function valueat each trial point. Asynchronous versions of the algorithm have been developedin the unconstrained and bound-constrained cases which allow the iterations tocontinue (and new trial points to be generated and evaluated) as soon as anyother trial point completes. This enables better utilization of parallel resourcesand a reduction in overall runtime, especially for problems where the objec-tive function takes minutes or hours to compute. For linearly-constrained GSS,the convergence theory requires that the set of search directions conform to the3 nearby boundary. The complexity of developing the asynchronous algorithm forthe linearly-constrained case has to do with maintaining a suitable set of searchdirections as the search progresses and is the focus of this research. We describeour implementation in detail, including how to avoid function evaluations bycaching function values and using approximate look-ups. We test our imple-mentation on every CUTEr test problem with general linear constraints and upto 1000 variables. Without tuning to individual problems, our implementationwas able to solve 95% of the test problems with 10 or fewer variables, 75%of the problems with 11-100 variables, and nearly half of the problems with100-1000 variables. To the best of our knowledge, these are the best resultsthat have ever been achieved with a derivative-free method. Our asynchronousparallel implementation is freely available as part of the APPSPACK software.4
BibTeX
@misc{kolda2007asynchronous,
  author = {Tamara G. Kolda and Joshua Griffin and Robert M. Lewis},
  title = {{Asynchronous parallel generating set search for linearly-constrained optimization.}},
  year = {2007},
  doi = {10.2172/1139970},
}
Figure