Project Proposal : Numerical Optimization of Expensive Computer Simulations

Computer simulations are increasingly used as decision making tools in engineering design and other related disciplines. They are often used to replace costly physical experiments, and do so with a reasonable degree of accuracy. However, this accuracy makes the experiment computationally expensive to evaluate, and may indeed cause the simulation to take hours to execute on the fastest of computers. This computationally expensive computer simulation, known as an ``expensive'' computer simulation, is thus infeasible to optimize by traditional numerical methods. This is due to that fact that these methods require numerous evaluations of the simulation. This situation has lead to the development of the ``computer experiments'' discipline, which is discussed in both statistics and engineering design literatures.

Booker et al. (1998) outlined a general algorithm known as the Surrogate Management Framework (SMF) to deal with this problem. However, this algorithm is very broad, and has yet to be fully implemented and tested. Professors Torczon and Trosset, who would be serving as advisors for this project, are both very active researchers in the field, and have developed a more specific algorithm known as the Model Assisted Grid Search (MAGS) . The project proposed herein is not ``watered down for an undergraduate'' by any means. It would fill gaps in existing research, and would serve to advance this discipline.

The first ``phase'' of this project, namely the background research and preparation, is being completed this semester in my Spatial Statistics and Computer Experiments seminar (MATH 490). This class takes the format of an undergraduate research seminar. As the general ideas behind the project were developed last semester, I enrolled in the seminar in preparation for the Honors project. Topics that I will be discussing, and later lecturing on this semester include balancing experimental design considerations and optimization accuracy by use of merit functions, and use of techniques to find global as opposed to local minima. These papers are mostly theoretical, which gives the proposed Honors project the opportunity to implement and follow through on the ideas Trosset and Torczon have advanced.

The second phase of this project, which would be completed over the summer, would involve the implementation in C++ of the improved MAGS algorithm outlined by Trosset (1998) shown below :

1.

Specify an initial grid, $\Gamma_0$, on [a,b].

2.

Perform an initial computer experiment :

(a)

Select initial design sites $x_1,\ldots,x_N\in \Gamma_0$.

(b)

Compute $f(x_1),\ldots,f(x_N)$.

(c)

Construct $\hat{f_0}$ by kriging.

3.

Let $\Gamma_c = \Gamma_0$. Let $x_c=\mbox{argmin}\left(f(x_1),\ldots,f(x_N)\right)$.
Let $\hat{f_c}=\hat{f_0}$ and $\mbox{Eval}_c=\{x_1,\ldots,x_N\}$.

4.

Do until convergence:

(a)

Do until $\mbox{Core}(x_c) \subset \mbox{Eval}_c$:

i.

Apply an optimization algorithm to S_c (the search criterion) to obtain $x_t\in\Gamma_c \backslash \mbox{Eval}_c$.

ii.

Compute f(x_t). Let $\mbox{Eval}_c = \mbox{Eval}_c \cup \{x_t\}$. Update S_c.

iii.

If f(x_t)<f(x_c), then let x_c=x_t.

(b)

Refine $\Gamma_c$.

The function f described above is the expensive simulation, and $\hat{f}$, is its approximation, generated by a statistical process known as kriging. $\mbox{Eval}_c$ is the set of input values at which f has been evaluated, and $\mbox{Core}(x_c)$ is specified by the convergence theory for pattern search, on which this algorithm is based.

At the current time, Trosset has written a prototype of this program in Splus, a high-level but inefficient programming language. This prototype is inadequate for all but the simplest of tests, as it only allows for two input parameters. After all, real engineering design problems have can have an arbitrarily large number of input parameters. The C++ implementation to be constructed during the summer, unlike the current prototype, would actually be useful for both theoretical testing and actual engineering design. The goal of this summer phase would be to have a completely realized C++ implementation.

The problem of the program's implementation is a highly non-trivial one. The program would have to be able to interface with a variety of objective functions. These functions may be actual simulations or test functions generated by Trosset's ``krigifier'' (a program that generates random functions by kriging). The program would also have to accommodate different experimental designs like Latin hypercube sampling and orthogonal arrays, as well as various choices of the families of approximating functions including various types of correlation functions. The ability to interface with a variety of search strategies, including pattern searches developed and tested in Elizabeth Dolan's senior Honors project, would also be necessary. Most importantly, the program would be expected to work with any variety of search criterion, including those based on merit functions. It is precisely the selection of these search criterion that a large portion of my senior Honors project will be based upon. Early test experiments would also be conducted over the summer period.

It is difficult to estimate the time needed to complete this project, but based upon my own experience, this project promises to be a great deal of work. Not only does a large quantity of code need to be produced to implement this algorithm, but a great deal of time needs to be spent on conceptual data structure and algorithm design, as well as testing and debugging. Therefore, in order to cover the costs of my research for a feasible amount of time, I am requesting five weeks of funding.

The third phase of this project, namely the senior Honors project itself, would occur during the next academic year. The focus of this project would be on comprehensive testing of the MAGS, and would allow the exploration of a variety of issues such as: ideal search criteria and the effects of the number of input variables on this balance, types of approximating families that are appropriate, and the effectiveness of various search strategies, such as pattern search, derivative-based methods, and both global and local optimizations.

The work in this discipline to date has produced an elegant conceptual framework and a few promising but preliminary results. The need for comprehensive and thoughtfully designed tests of the framework is great, and that it precisely what this project would provide. The proposed project has the potential to make a serious contribution to the computer experiments discipline, and funding for summer work would truly make this contribution possible.