Asynchronous Parallel Pattern Search

Version 5.0.1
Released February 16, 2007

Introduction

APPSPACK is serial or parallel, derivative-free optimization software for solving nonlinear unconstrained, bound-constrained, and linearly-constrained optimization problems, with possibly noisy and expensive objective functions. The basic optimization problem is of the form

$\begin{array}{ll} \min & f(x) \\ \mbox{subject to} & c_L \leq A_I x \leq c_U \\ & A_E x = b \\ & \ell \leq x \leq u \end{array}$

Here $f: \mathbb{R}^n \rightarrow \mathbb{R} \cup \{+\infty\}$ is the objective function. The inequality constraints are denoted by the matrix $A_I$ and the upper and lower bounds $c_L,c_U$ . Each constraint can be bounded on both sides or just one. The equality constraints are denoted by the matrix $A_E$ and the right hand side $b$ . Finally, $\ell$ and $u$ denote the lower and upper bounds, respectively, which are optional on a parameter-by-parameter basis. To find a solution of this problem, APPSPACK implements asynchronous parallel generating set search, which handles bound and linear constraints by choosing search directions that conform to the nearby boundary. APPSPACK is written in C++ and uses MPI for parallelism. Constraint degeneracy is handled using the software package cddlib (relevant files included with distribution). Using APPSPACK to solve optimization problems has the following advantages:

Only function values are required for the optimization, so it can be applied to a wide variety of problems. The user need simply provide a program (written in any language such as Fortran, C, C++, Perl, etc.) that can evaluate the objective function at a given point.
The target applications are simulation-based optimization problems characterized by a small number of variables (i.e., n < 100) and by expensive objective function evaluations (typically complex simulations that take minutes or hours to run). The procedure for evaluating the objective function does not need to be encapsulated in a subroutine and can, in fact, be an entirely separate program.
The code can be run in parallel on a cluster of computers, greatly reducing the total solution time. Parallelism is achieved by assigning the individual function evaluations to different processors. The (optional) asynchronism enables better load balancing.
The software is freely available under the terms of the GNU Lesser General Public License.

Key words: optimization, derivative-free, parallel, direct search, pattern search, engineering design

Getting Started

Using the Code

Publications about APPSPACK
Using the APPSPACK Executables
Solver Parameters
Linear Constraint Parameters
Customizing APPSPACK (for advanced users only)

Tamara G. Kolda, Sandia National Labs, tgkolda@sandia.gov
Patricia D. Hough, Sandia National Labs, pdhough@sandia.gov
Genetha Gray, Sandia National Labs, gagray@sandia.gov
Josh Griffin, Sandia National Labs, jgriffi@sandia.gov
R. Michael Lewis, College of William & Mary (cddlib interface)
Robert Darwin (Sandia Summer Intern, 2004)
Daniel Dunlavy (Sandia Summer Intern, 2001)
H. Alton Patrick (Sandia Summer Intern, 2000)
Sarah Brown (Sandia Summer Intern, 2000)

We also gratefully acknowledge Komei Fukuda for providing the cddlib, parts of which are distributed with APPSPACK.

For All Other Questions and Comments...

Please contact Tamara G. Kolda.

Asynchronous Parallel Pattern Search

Introduction

Getting Started

Using the Code

Results with APPSPACK

More Information

Contributors

For All Other Questions and Comments...