Introduction

The SGOPT library contains a variety of global optimization algorithms, with an emphasis on stochastic methods. SGOPT currently includes the following global optimization methods: genetic algorithms (PGAreal,PGAint), evolutionary pattern search algorithms (EPSA), simulated annealing (SAreal), tabu search (TSreal), multistart local search (MSreal) and stratified Monte Carlo (sMCreal). Additionally, SGOPT includes several local search algorithms such as Solis-Wets (SWOpt) and pattern search (PatternSearch).

SGOPT stands for Stochastic Global OPTimization and for expensive optimization problems its global optimizers are best suited for identifying promising regions in the global design space. In multimodal design spaces, the combination of global identification (from SGOPT) with efficient local convergence (from a gradient-based algorithm) can be highly effective. The SGOPT methods are not gradient-based, which makes them appropriate for discrete problems as well as problems for which gradient information is unavailable or is of questionable accuracy due to numerical noise, etc. No SGOPT methods currently support general linear and nonlinear constraints directly, although penalty function formulations for nonlinear constraints have been employed with success [PonEld96].

This document describes the algorithms that are implemented within SGOPT at a high level. Presently SGOPT does not include software to provide a standardized interface for initializing the optimizers. Instead, the optimization library is linked into an executable defined by the user. Many of the optimizers defined by SGOPT are currently included in the interface to the DAKOTA Iterator Toolkit [EldHarBohRom96].

Historically, this software evolved as a library of algorithms used for research purposes. Consequently, there are many places in this library where the software could be further polished, and some of the libraries are more stable than others. Indications are made at the end of the sections describing each of the optimizers in SGOPT concerning the stability of each optimizer.

Generic Optimizers

The majority of optimizers in SGOPT are designed to perform optimization over . However, some optimizers like genetic algorithms can be readily adapted to perform optimization over a wide variety of search domains. Two approaches are taken in SGOPT to accomodate the optimization of a generic search domain.

Generic Point Optimization A facility for optimizating a user-defined search domain has been constructed for Monte Carlo search and genetic algorithms. This facility uses the class GenericPointBase to define the basic operations that are needed to define these optimizers. The user simply defines a subclass of GenericPointBase and instantiates one of the generic optimizers to perform optimization. Examples of the use of this facility are included in the subdirectory examples/generics. This facility is easy to use, but the user's ability to customize the optimizer to a particular search domain is limited to the user's choice of the methods used to generate new trial points in the search domain. {Note: I expect to templatize much of this code in the near future, which may remove the needed for this capability.}

Object-Oriented Design When possible, an object oriented design has been adopted which allows a user to easily define a new C++ class to perform optimization over a novel search domain. The simplest example of this design is the class structure for Monte Carlo search. This algorithm simply generates random samples from a search domain. The current class heirarchy for Monte Carlo search is

                              sMC
                              / \
                             /   \
                        sMCreal  sMCgen

The class sMC defines the main loop of a Monte Carlo search algorithm. This loop utilizes a variety of abstract functions that are defined by the descendents of sMC. These functions define how randomization is performed as well as some IO. This type of object oriented design allows for significant code reuse when designing a Monte Carlo search algorithm for a new search domain. The other example of this type of object oriented design is the class heirarchy used for genetic algorithms (see Section Evolutionary Algorithms). Instantiating a new optimizer is considerably more complex than using the generic-point facility, but this option does allow the user to make algorithmic modifications that tailor the optimizers in SGOPT for a particular search domain.

Overview

It will often be convenient to describe the methods and information in optimization classes in five categories:

• General Information: definitions of generic methods and data

• Configuration Controls: definitions of methods and data that are used to parameterize the operation of an optimizer

• Termination Controls: definitions of methods and data that are used to determine when an optimizer terminates

• Debugging Controls: definitions of methods and data that are used to print debugging information

• Iteration Controls: defintions of methods and data that are used to define the optimizers main operations in each iteration