Algorithm Development for BlackBox Global Optimization

Motivation
Optimization problems arise in many engineering applications, e.g.
Environment: clean up contaminated groundwater at minimal cost
Alternative energies: maximize the power generated
Simulation: minimize the error between the simulation model and observations
Transportation network design: minimize total travel time

Optimization problem characteristics
Objective function values are computed by a time consuming blackbox simulation model
Derivative information is not available
Problems are multimodal, i.e., there are several local optima
Constraints may be computationally cheap, computed by an expensive blackbox simulation model, or simple box constraints
The simulation model may not return a function value (not a bug in the simulation model, e.g., may be some exception case in the simulation model)
Variables can be continuous, mixedinteger, integer, binary
Challenge
Goal: find a nearoptimal solution by doing only very few expensive simulation model evaluations in order to keep the optimization time acceptable
Traditional algorithms such as evolutionary algorithms or gradientbased methods require too many expensive function evaluations
to find nearoptimal solutions
Function evaluations are becoming even more expensive as simulation models become more complex and of higher fidelity, requiring
more computational resources
More sophisticated optimization algorithms are needed to efficiently and effectively tune the simulation model parameters
Approach
We use a computationally cheap approximation s(x) (the surrogate model) of the expensive
function f(x) in order to predict function values at unsampled points and guide the search for
improved solutions:
A general surrogate model works as follows:
Step 1: Create an initial experimental design. Evaluate f(x) at the selected points. Fit the
surrogate s(x) to the data.
Step 2: Use s(x) to select a new evaluation point xnew and compute f(xnew).
Step 3: If the stopping criterion is not satisfied, update s(x) with the new data and go to Step 2.
Otherwise, stop.
Selected application areas
Climate models:
Tune the parameters of the CH4 model such that the error between the model's predictions and the observations are minimized
Problem characteristics: parameters are continuous, the objective function is computationally expensive, box constraints

The figure shows the difference between the climate model's CH4 predictions with default (outofthebox) and optimized parameters. The error between the simulation model predictions and observations was significantly reduced by tuning the model's parameters. The predictions of CH4 emissions with optimized parameters are larger in northern latitudes and lower in the tropics than when using default parameters.

Transportation network design:
Add links to an existing network to minimize the total travel time subject to budget constraints
Problem characteristics: binary variables, computationally expensive objective function, computationally cheap budget constraint


Environmental applications:
Cannonsville watershed management: reduce the phosphorus loading in the reservoir to a given threshold by retiring high nutrient runoff lands in the watershed at minimal cost
Groundwater remediation by pumpandtreat system design: clean and prevent further contamination of an aquifer at minimal cost such that contamination constraint is satisfied
Problem characteristics: parameters are integer (management problem) or mixedinteger (pumpandtreat system design), objective function value is computationally inexpensive to compute, constraint function values are computed by computationally expensive simulation models

Ongoing work
Development of new algorithms for problems with ''hidden'' constraints (simulation model does not return a function value for certain parameter combinations)
Applications in Combustion (tune model parameters to minimize the error between simulation model output and observations); ALS lattice optimization (tune model parameters in order to maximize the brightness of the light source)
Future collaboration on DEDUCE data analytics project: as new data becomes available, use surrogate models to determine whether or not it is useful to redo the computationally expensive data product
Contact
For more information, contact
Juliane Mueller
Related publications
J. Mueller, J. Woodbury
"GOSAC: Global Optimization with Surrogate Approximation of Constraints",
under review at INFORMS Operations Research
J. Mueller,
"MISO: MixedInteger Surrogate Optimization Framework",
Optimization and Engineering, to appear, 2015
[link].
J. Mueller, R. Paudel, N. Mahowald, C. Shoemaker,
"CH4 Parameter Estimation in CLM4.5bgc Using Surrogate Global Optimization",
Geoscientific Model Development, 8:141207, 2015
[pdf].