Model-Assisted Pattern Search

Christopher Siefert, Virginia Torczon, and Michael W. Trosset

Computer simulations of complex physical phenomena are used in many contexts, including that of engineering design. Increasingly scientists and engineers have also been trying to optimize problems defined by such simulations (e.g. to determine design parameters for a physical product). However, these problems often have several features that hinder the use of standard optimization techniques. The lack of derivative information and numerical error induced by the simulation can cause problems for derivative-based optimization methods. Likewise, extreme computational expense can make the use of direct search methods problematic.

The Model-Assisted Pattern Search (MAPS) algorithm, which is the subject of this research, attempts to address the issue. While maintaining a pattern search framework, MAPS makes use of easily constructed surrogates to the objective function in order to speed the optimization process.

The software posted here is part of an ongoing project to develop a complete, self-contained, C++ class-based implementation of the model management framework. This software was written by Christopher Siefert as part of a 2000 Honors Thesis in Computer Science under the direction of Virginia Torczon and Michael W. Trosset. Numerical results for MAPS and several other algorithms applied to a variety of different objective functions are presented in the thesis.

This implementation is the latest effort in the following series of work:

Model-Assisted Pattern Search 2000
Optimization on a limited budget 1998
Using approximations to accelerate engineering design optimization 1998
A rigorous framework for optimization of expensive functions by surrogates 1999
Optimization using surrogate objectives on a helicopter test example 1998
A trust region framework for managing the use of approximation models in optimization 1998
Numerical optimization using computer experiments 1997 (revised 1999)
Managing approximations models in optimization 1997


We thank the National Science Foundation for support received under Grant No. CCR-9734044. In addition, Christopher Siefert received support from the National Science Foundation under grant No. EIA-9712718, as well as from the College of William & Mary under a Batten Scholarship during the summer of 1999, when the development of this software was first undertaken.

Model-Assisted Pattern Search (MAPS) Source Code


The bracketed links below are links to the C++ source for MAPS. If you wish to save the files below rather than view them, click on the link with the SHIFT key depressed. With a Netscape browser, this will bring up a "Save As" dialog box.

Gzipped Tarballs with Everything!

A patient user would be well-advised to start by reading The Basics section of the MAPS Manual, which is conveniently on-line, as well as available in gzipped PostScript format.

The impatient user can skip immediately to the manual section Quick Install and Test Run.

The truly impatient user can install MAPS by downloading the two gzipped tarballs below. To install them, type: gtar zxvf maps.tgz and gtar zxvf netlibfiles.tgz at the prompt. Then make install and (finally) make.
MAPS Manual (HTML) [maps.tgz]
MAPS Manual (GZIPPED PS) [netlibfiles.tgz]

If you already have the netlibfiles.tgz from the Krigifier, then you don't have to download it here.

If you are having difficulties, consult the Troubleshooting section of the MAPS Manual.


Fortran Wrappers for MAPS

For functions written in FORTRAN, wrappers have been constructed to allow the user to access MAPS.  Ignore the tarballs above, and follow these instructions.


STANDARD DISCLAIMER:
Permission to use, copy, modify, and distribute this software for any purpose without fee is hereby granted, provided that this entire notice is included in all copies of any software which is or includes a copy or modification of this software and in all copies of the supporting documentation for such software. THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED WARRANTY. IN PARTICULAR, THE AUTHOR OFFERS NO REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.