13. Expensive Optimization — Optimization when Evaluations Are Costly

// CORE 7/7 — DOE, Latin Hypercube Sampling, surrogate modeling, surrogate-based optimization

When objective evaluations are cheap, many iterations are possible. But when evaluation is expensive—such as simulation, experimentation, or inference with a large model—"where to evaluate" becomes the core of the optimization itself.

Why expensive optimization?

Gradient descent is difficult to use directly in the following situations:

• Objective evaluation takes a long time.
• A gradient is difficult or impossible to obtain.
• Experiments are costly.
• Noise is present.
• Constraint violations are dangerous or expensive.

The objective is then to find a good solution with few evaluations.

DOE

DOE means Design of Experiments. Before building a model or beginning exploration, it selects experimental points systematically.

A poor DOE concentrates samples in one region and biases the surrogate. A good DOE covers the design space evenly and avoids missing important interactions.

Latin Hypercube Sampling

Latin Hypercube Sampling divides the axis of each variable into several intervals and places samples so that every interval is used once.

Intuitively, it satisfies the following requirements:

1. Inspect the range of every variable evenly.
2. Use far fewer points than a full grid.
3. Create data for training the initial surrogate.

The number of samples in a full factorial design explodes as dimensionality grows. LHS is a compromise that surveys the space broadly with fewer points.

Surrogate modeling

A surrogate model replaces the expensive original function $f(x)$ with a cheap approximate function $\hat{f}(x)$:

$$f(x)\approx \hat{f}(x).$$

Commonly used surrogates include:

Surrogate	Characteristic
Polynomial response surface	Easy to interpret and fast
Radial basis function	Useful for smooth interpolation
Gaussian process	Can estimate uncertainty
Random forest	Handles nonlinearity and interactions
Neural network	Highly expressive with abundant data

A surrogate is fast but can be wrong. Balancing exploitation and exploration is therefore important.

Surrogate-based optimization

Surrogate-based optimization is a loop that trains a surrogate, chooses the next evaluation point on it, evaluates the real function, and updates the surrogate.

Typical flow:

1. Create initial samples with DOE.
2. Evaluate the real expensive function.
3. Train a surrogate model.
4. Choose the next point with an acquisition or infill criterion.
5. Evaluate the real function and add the result to the data.
6. Repeat until the budget is exhausted.

Bayesian optimization is a representative form of surrogate-based optimization using a Gaussian-process surrogate and an acquisition function.

Key questions while reading

• How many evaluations are in the budget?
• Is there noise?
• Are constraints also expensive?
• Can surrogate uncertainty be used?
• Is global search more important, or local refinement?

Summary of the entire series

Optimization can be condensed into the following sequence:

1. Formulate the problem with variables, an objective function, and constraints.
2. Read local structure with derivatives and linear algebra.
3. Establish stopping criteria through optimality conditions.
4. Choose an algorithm suited to the cost and structure.
5. When evaluation is expensive, optimize the evaluation strategy itself with DOE and a surrogate.

Back to the beginning: Optimization index