Charles Audet, John Dennis and Doug Moore, Rice University

Numerical optimization has a rich history, and many useful applications, but the utility of many classical algorithms is limited in the real world. Many methods are designed to exploit information about objective and constraint derivatives that may not be available for real applications. Many algorithms assume that function evaluation is relatively inexpensive, and so throw away function values shortly after they are computed. Few algorithms deal with the real-life possibility of inaccuracy in the evaluation of functions. These kinds of limitations on the classical algorithms got Rice University Computational and Applied Mathematics Professor John Dennis thinking.

"[Paul Frank of Boeing] asked me how I would design an optimization algorithm that had access to cheap surrogates of the function but that could only compute 'true' function values at huge expense," says Dennis. His attempt to answer that question has defined the last several years of his research, and of his collaborators, former students Virginia Torczon and David Serafini, and colleagues Charles Audet and Doug Moore. The latest developments in that research program include a C++ software library called FOCUS (Framework for Optimization with Constraints Using Surrogates) developed by Moore to allow the group to explore a variety of surrogate optimization techniques. FOCUS has also begun to solve a few small problems from industry.

What are surrogate-based optimization methods, exactly? "They are unlike Newton techniques in that they do not use derivatives or even try to approximate them," says Dennis. Instead, they only evaluate parameters that lie on a series of finer and finer grids, and use surrogates to help guide the choice of which grid points are worth the considerable trouble that evaluating the true functions can require. Surrogates incorporate knowledge about the function values seen so far, and predict whether a particular design will improve on the best ones seen so far. Says Dennis, "They are likely to be slower than Newton methods, [but] easier to parallelize than Newton techniques." They are also robust, in the sense that even in the presence of faulty surrogates, they eventually produce a locally good solution.

Multiobjective problems naturally arise when there are several conflicting goals, and designers need to understand the tradeoffs. Thus, these problems require surrogate algorithms that maintain a collection of designs, each best under a particular weighting of objectives. Indraneel Das of Mobil Oil developed important techniques for multiobjective problems as a student of Dennis.

FOCUS is a C++ framework for working with these ideas. It is very flexible, allowing designers to pick their favorite surrogates, search strategies, termination criteria, and so on. "I've designed the package in an object-oriented way, so that users can plug in their own class definitions to introduce new ideas without rewriting or understanding much code," says Moore. The framework also introduces a novel scheme for storing the results of expensive function evaluations, by using space-filling curves.

Government and industry have problems well-suited for surrogate-based techniques. Says Dennis, "Our colleagues at Boeing have used this approach on jet engine inlet design and on wing planform design. The proposed new small passenger Boeing 717 has a planform designed using an experimental version of this approach that handles nonlinear inequality constraints. Greg Shubin, the manager of the group involved at Boeing once said that he thought 90% of Boeing's optimization problems could be attacked this way." He adds, "Based on common sense and some results from a sample problem in helicopter rotor design, they seem more likely to find a better optimum than derivative-based methods."

Mobil Oil has also recently expressed interest in applying these techniques to oilfield planning. "They have a wonderfully complex problem," says Moore. "They've got problems that involve ground permeability, gas pressure, inflation, and capital costs. Over time we expect to solve problems that will save them real money. Once we've defined the black box that takes in an oilfield management strategy, and puts out a profitablity figure, we plan to apply our techniques to their problem."

Reflecting on the genesis of this research, Dennis says, "I was on the flight up for my next visit to Boeing. I remember thinking that I would be embarrassed if I hadn't spent some time thinking about Paul's question about optimization algorithm design before I got to his office the next day, and when I finished that thought the skeleton of the answer was there in my mind. Of course, every researcher knows that our subconscious is our best research tool, but it still thrills me when this happens." That moment, plus several years of work by several people, have produced tools and theory that we expect to solve serious industrial problems in the coming years.