Algorithm Development for Black-Box Global Optimization



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 black-box 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 black-box 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, mixed-integer, integer, binary

  • Challenge

  • Goal: find a near-optimal 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 gradient-based methods require too many expensive function evaluations to find near-optimal 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.

  • Optimization

    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
  • Optimization

    The figure shows the difference between the climate model's CH4 predictions with default (out-of-the-box) 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
  • Optimization

    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 pump-and-treat 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 mixed-integer (pump-and-treat 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: Mixed-Integer 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:141-207, 2015 [pdf].