Asynchronous parallel generating set search for linearly constrained optimization

Joshua Griffin

doi:10.1137/060664161

Asynchronous parallel generating set search for linearly constrained optimization

2008-01-01

34

OA

AI

DOI：10.1137/060664161

原文链接

原文求助

摘要

En 中文

We describe an asynchronous parallel derivative-free algorithm for linearly constrained optimization. Generating set search (GSS) is the basis of our method. At each iteration, a GSS algorithm computes a set of search directions and corresponding trial points and then evaluates the objective function value at each trial point. Asynchronous versions of the algorithm have been developed in the unconstrained and bound-constrained cases which allow the iterations to continue (and new trial points to be generated and evaluated) as soon as any other trial point completes. This enables better utilization of parallel resources and a reduction in overall run time, especially for problems where the objective function takes minutes or hours to compute. For linearly constrained GSS, the convergence theory requires that the set of search directions conforms to the nearby boundary. This creates an immediate obstacle for asynchronous methods where the definition of nearby is not well defined. In this paper, we develop an asynchronous linearly constrained GSS method that overcomes this difficulty and maintains the original convergence theory. We describe our implementation in detail, including how to avoid function evaluations by caching function values and using approximate lookups. We test our implementation on every CUTEr test problem with general linear constraints and up to 1000 variables. Without tuning to individual problems, our implementation was able to solve 95% of the test problems with 10 or fewer variables, 73% of the problems with 11-100 variables, and nearly half of the problems with 100-1000 variables. To the best of our knowledge, these are the best results that have ever been achieved with a derivative-free method for linearly constrained optimization. Our asynchronous parallel implementation is freely available as part of the APPSPACK software.

Keyword:

nonlinear programming

constrained optimization

linear constraints

direct search

derivative-free optimization

generalized pattern search

generating set search

asynchronous parallel optimization

asynchronous parallel pattern search

Asynchronous parallel generating set search for linearly constrained optimization

摘要

期刊

机构

引用论文