Optimization techniques

SurrogateOptimizationAlgorithm

Abstract interface for surrogate optimization strategies used by surrogate_optimize!.

Concrete subtypes select how new candidate points are generated and evaluated against an existing surrogate. A subtype is used as a dispatch token:

surrogate_optimize!(objective, SRBF(), lb, ub, surrogate, sample_type)

Interface

A concrete alg <: SurrogateOptimizationAlgorithm is valid when surrogate_optimize!(objective, alg, lb, ub, surrogate, sample_type; kwargs...) is implemented for the surrogate and sampling types it supports. Implementations may mutate surrogate by calling update! with newly evaluated points.

Arguments

• objective::Function: expensive objective function to minimize.
• lb: lower bound of the search domain.
• ub: upper bound of the search domain.
• surrogate: fitted surrogate satisfying the AbstractSurrogate evaluation and update! interface.
• sample_type::SamplingAlgorithm: sampling strategy used to generate candidate points.

ParallelStrategy

Abstract interface for virtual-point strategies used by potential_optimal_points.

Concrete subtypes define how a temporary surrogate is updated while selecting a batch of parallel candidate points. A strategy is used only through potential_optimal_points(alg, strategy, lb, ub, surrogate, sample_type, n).

Interface

A subtype strategy <: ParallelStrategy must be supported by a calculate_liars(strategy, tmp_surrogate, surrogate, x_new) method. The method updates tmp_surrogate with a virtual objective value at x_new without evaluating the true objective.

SRBF()

Surrogate optimization marker for the stochastic radial-basis-function search strategy.

Usage

surrogate_optimize!(objective, SRBF(), lb, ub, surrogate, sample_type)

Interface

The surrogate must implement surrogate(x) and update!(surrogate, x, y), and must store existing samples in surrogate.x and surrogate.y.

LCBS()

Surrogate optimization marker for lower-confidence-bound search.

Usage

surrogate_optimize!(objective, LCBS(), lb, ub, kriging_surrogate, sample_type)

Interface

The surrogate must provide std_error_at_point(surrogate, x) in addition to the generic surrogate evaluation and update! interface.

EI()

Surrogate optimization marker for expected-improvement search.

Usage

surrogate_optimize!(objective, EI(), lb, ub, kriging_surrogate, sample_type)

Interface

The surrogate must provide std_error_at_point(surrogate, x) and the generic surrogate evaluation and update! interface.

DYCORS()

Surrogate optimization marker for dynamic coordinate search.

Usage

surrogate_optimize!(objective, DYCORS(), lb, ub, surrogate, sample_type)

Interface

The surrogate must implement surrogate(x), update!(surrogate, x, y), and sample storage through surrogate.x and surrogate.y.

SOP(p)

Surrogate optimization marker for the candidate-ranking strategy used by the second-order polynomial optimizer.

Fields

• p: number of search centers carried, and so the number of candidate points proposed per iteration.

Usage

surrogate_optimize!(objective, SOP(2), lb, ub, surrogate, sample_type)

SMB()

Surrogate optimization marker for the surrogate-model-based multi-objective optimizer.

Usage

surrogate_optimize!(objective, SMB(), lb, ub, surrogate, sample_type)

RTEA(k, z, p, n_c, sigma)

Surrogate optimization marker for the rolling tide evolutionary algorithm, a multi-objective method for noisy objectives.

Each iteration proposes one child by simulated binary crossover and Gaussian mutation of two members of the current Pareto approximation, then re-evaluates k of its least-visited members. The re-evaluation is what the method is for: under a noisy objective a member may only appear non-dominated, and repeated measurement is what removes it.

Fields

• k: number of Pareto members re-evaluated per iteration.
• z: fraction of the iteration budget reserved for re-evaluation alone. New children are proposed while iter < (1 - z) * maxiters; the remaining z of the run only re-measures what the front already holds.
• p: probability that a pair of parents is crossed. With probability 1 - p the child is a copy of one parent, mutated.
• n_c: distribution index of the simulated binary crossover. Larger values concentrate children nearer their parents.
• sigma: standard deviation of the Gaussian mutation.

Usage

surrogate_optimize!(objective, RTEA(k, z, p, n_c, sigma), lb, ub, surrogate, sample_type)

References

Fieldsend, J. E., & Everson, R. M. (2015). The rolling tide evolutionary algorithm: a multiobjective optimizer for noisy optimization problems. IEEE Transactions on Evolutionary Computation, 19(1), 103-117.

surrogate_optimize!(objective, algorithm, lb, ub, surrogate, sample_type;
    maxiters = 100, num_new_samples = 100, needs_gradient = false)

Minimize objective with a surrogate-assisted optimization algorithm.

The algorithm generates candidate points with sample, scores them using the surrogate, evaluates the selected point with objective, and updates the surrogate with the new observation. The available methods differ in their algorithm token and in the surrogate capabilities they require; the common call/update contract is described under AbstractSurrogate.

Arguments

• objective::Function: objective function to minimize. It must accept one point in the representation used by surrogate and return a scalar or objective vector supported by algorithm.
• algorithm::SurrogateOptimizationAlgorithm: optimization strategy, such as SRBF, LCBS, EI, or DYCORS.
• lb: lower bound of the search domain.
• ub: upper bound of the search domain, with the same dimensionality as lb.
• surrogate::AbstractSurrogate: fitted surrogate whose call overload predicts an objective value and whose update! method accepts new data.
• sample_type::SamplingAlgorithm: sampling strategy used to generate candidate points.

Keywords

• maxiters::Integer = 100: maximum number of optimization iterations. One iteration costs one objective evaluation, so this also caps how many times objective is called – except for SOP, which proposes one candidate per search center and so costs SOP.p evaluations per iteration.
• num_new_samples::Integer = 100: number of candidate points considered at each iteration.
• needs_gradient::Bool = false: whether the selected method should evaluate an objective gradient and pass it to a gradient-aware update! method. Set it for the gradient-enhanced surrogates, GEK and GEKPLS, which refuse a response without one. Every single-objective method accepts it.

Returns

(point, value): the best observation the surrogate holds when the search stops. The value is always a measured objective value, never an acquisition score. Multi-objective methods (SMB, RTEA) return a Pareto set and its front instead.

A search can stop before maxiters is reached: when every remaining candidate falls within the minimum separation of an already-evaluated point ("Out of sampling points"), or when the trust region grows past the domain or shrinks below a usable width.

Example

using Surrogates

objective(x) = (x - 0.25)^2
x = [0.0, 0.5, 1.0]
y = objective.(x)
surrogate = Kriging(x, y, 0.0, 1.0)
best_point, best_value = surrogate_optimize!(
    objective, SRBF(), 0.0, 1.0, surrogate, RandomSample();
    maxiters = 2, num_new_samples = 8)

surrogate_optimize!(obj, ::LCBS, lb, ub, krig, sample_type;
    maxiters = 100, num_new_samples = 100, k = 2.0, needs_gradient = false)

Minimize obj with the lower confidence bound acquisition function.

Under a Gaussian process prior the acquisition is

$LCB(x) = E[x] - k\sqrt{V[x]}$

which is minimized over a fresh candidate pool at each iteration. Larger k weights the predictive standard deviation more heavily and so explores more. The search stops once no candidate's bound improves on the best observation, meaning none of them can plausibly beat the incumbent.

krig must provide std_error_at_point: Kriging, GEK, KPLS, KPLSK, GEKPLS or AbstractGPSurrogate. Given a surrogate without a predictive variance, this method raises an ArgumentError before the search starts rather than failing partway through it.

References

Cox, D.D. and John, S. (1992). A statistical method for global optimization. IEEE International Conference on Systems, Man, and Cybernetics, 1241-1246.

Srinivas, N., Krause, A., Kakade, S.M. and Seeger, M. (2010). Gaussian process optimization in the bandit setting: no regret and experimental design. ICML, 1015-1022.

surrogate_optimize!(obj, ::EI, lb, ub, krig, sample_type;
    maxiters = 100, num_new_samples = 100, needs_gradient = false)

Minimize obj with the expected improvement acquisition function.

At each iteration a fresh candidate pool is scored by

$EI(x) = (f_{min} - \mu(x) - \xi)\Phi(z) + \sigma(x)\phi(z), \qquad z = \frac{f_{min} - \mu(x) - \xi}{\sigma(x)}$

the candidate maximizing it is evaluated, and the surrogate is refitted. The offset $\xi$ biases the search towards exploration. The search stops once the best expected improvement is negligible against the spread of the observations.

krig must provide std_error_at_point: Kriging, GEK, KPLS, KPLSK, GEKPLS or AbstractGPSurrogate. Given a surrogate without a predictive variance, this method raises an ArgumentError before the search starts rather than failing partway through it.

References

Jones, D.R., Schonlau, M. and Welch, W.J. (1998). Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13, 455-492.

surrogate_optimize!(obj, ::DYCORS, lb::Number, ub::Number, surr1, sample_type;
    maxiters = 100, num_new_samples = 100, needs_gradient = false)

One-dimensional DYCORS. With a single coordinate there is nothing to choose between, so this reduces to perturbing the incumbent by a Gaussian step whose width follows the same success/failure schedule as the multidimensional method. See the multidimensional method for the algorithm and its reference.

surrogate_optimize!(obj, ::DYCORS, lb, ub, surrn, sample_type;
    maxiters = 100, num_new_samples = 100, needs_gradient = false)

Minimize obj with dynamic coordinate search.

DYCORS extends SRBF by changing how candidates are generated, not how they are ranked: candidates are Gaussian perturbations of the incumbent in a random subset of the coordinates rather than a design over a trust region. Each coordinate is perturbed with probability

$p_{select}(k) = \min(20/d, 1)\left(1 - \frac{\ln k}{\ln k_{max}}\right)$

which falls to zero over the run, so late iterations move along very few directions – the useful behaviour when the objective depends on only a handful of them. At least one coordinate is always perturbed. The perturbation width doubles after three consecutive improvements and halves after max(d, 5) consecutive failures. Candidates are ranked by the same weighted score as SRBF, so the two methods differ only in how candidates are generated.

References

Regis, R.G. and Shoemaker, C.A. (2013). Combining radial basis function surrogates and dynamic coordinate search in high-dimensional expensive black-box optimization. Engineering Optimization, 45(5), 529-555.

surrogate_optimize!(obj, sop::SOP, lb, ub, surr, sample_type;
    maxiters = 100, num_new_samples = min(500d, 5000), needs_gradient = false)

Minimize obj with surrogate optimization using Pareto center selection.

SOP maintains several search centers at once and picks them by non-dominated sorting on two criteria: the observed objective value, and the distance to the nearest evaluated point. Ranking centers this way spreads them between the promising and the unexplored parts of the domain, which is what makes the method parallel-friendly – sop.p centers are carried, and one candidate is proposed from each per iteration. A center whose proposal fails to improve the dominated hypervolume has its radius halved, and after enough failures it is placed on a tabu list.

num_new_samples is best set to min(500d, 5000) for a d-dimensional problem.

References

Krityakierne, T., Akhtar, T. and Shoemaker, C.A. (2016). SOP: parallel surrogate global optimization with Pareto center selection for computationally expensive single objective problems. Journal of Global Optimization, 64, 421-445.

Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley.

surrogate_optimize!(objective, algorithm, lb, ub, surrogate, sample_type;
    maxiters = 100, num_new_samples = 100, needs_gradient = false)

Minimize objective with a surrogate-assisted optimization algorithm.

The algorithm generates candidate points with sample, scores them using the surrogate, evaluates the selected point with objective, and updates the surrogate with the new observation. The available methods differ in their algorithm token and in the surrogate capabilities they require; the common call/update contract is described under AbstractSurrogate.

Arguments

• objective::Function: objective function to minimize. It must accept one point in the representation used by surrogate and return a scalar or objective vector supported by algorithm.
• algorithm::SurrogateOptimizationAlgorithm: optimization strategy, such as SRBF, LCBS, EI, or DYCORS.
• lb: lower bound of the search domain.
• ub: upper bound of the search domain, with the same dimensionality as lb.
• surrogate::AbstractSurrogate: fitted surrogate whose call overload predicts an objective value and whose update! method accepts new data.
• sample_type::SamplingAlgorithm: sampling strategy used to generate candidate points.

Keywords

• maxiters::Integer = 100: maximum number of optimization iterations. One iteration costs one objective evaluation, so this also caps how many times objective is called – except for SOP, which proposes one candidate per search center and so costs SOP.p evaluations per iteration.
• num_new_samples::Integer = 100: number of candidate points considered at each iteration.
• needs_gradient::Bool = false: whether the selected method should evaluate an objective gradient and pass it to a gradient-aware update! method. Set it for the gradient-enhanced surrogates, GEK and GEKPLS, which refuse a response without one. Every single-objective method accepts it.

Returns

(point, value): the best observation the surrogate holds when the search stops. The value is always a measured objective value, never an acquisition score. Multi-objective methods (SMB, RTEA) return a Pareto set and its front instead.

A search can stop before maxiters is reached: when every remaining candidate falls within the minimum separation of an already-evaluated point ("Out of sampling points"), or when the trust region grows past the domain or shrinks below a usable width.

Example

using Surrogates

objective(x) = (x - 0.25)^2
x = [0.0, 0.5, 1.0]
y = objective.(x)
surrogate = Kriging(x, y, 0.0, 1.0)
best_point, best_value = surrogate_optimize!(
    objective, SRBF(), 0.0, 1.0, surrogate, RandomSample();
    maxiters = 2, num_new_samples = 8)

surrogate_optimize!(obj, ::LCBS, lb, ub, krig, sample_type;
    maxiters = 100, num_new_samples = 100, k = 2.0, needs_gradient = false)

Minimize obj with the lower confidence bound acquisition function.

Under a Gaussian process prior the acquisition is

$LCB(x) = E[x] - k\sqrt{V[x]}$

which is minimized over a fresh candidate pool at each iteration. Larger k weights the predictive standard deviation more heavily and so explores more. The search stops once no candidate's bound improves on the best observation, meaning none of them can plausibly beat the incumbent.

krig must provide std_error_at_point: Kriging, GEK, KPLS, KPLSK, GEKPLS or AbstractGPSurrogate. Given a surrogate without a predictive variance, this method raises an ArgumentError before the search starts rather than failing partway through it.

References

Cox, D.D. and John, S. (1992). A statistical method for global optimization. IEEE International Conference on Systems, Man, and Cybernetics, 1241-1246.

Srinivas, N., Krause, A., Kakade, S.M. and Seeger, M. (2010). Gaussian process optimization in the bandit setting: no regret and experimental design. ICML, 1015-1022.

surrogate_optimize!(obj, ::EI, lb, ub, krig, sample_type;
    maxiters = 100, num_new_samples = 100, needs_gradient = false)

Minimize obj with the expected improvement acquisition function.

At each iteration a fresh candidate pool is scored by

$EI(x) = (f_{min} - \mu(x) - \xi)\Phi(z) + \sigma(x)\phi(z), \qquad z = \frac{f_{min} - \mu(x) - \xi}{\sigma(x)}$

the candidate maximizing it is evaluated, and the surrogate is refitted. The offset $\xi$ biases the search towards exploration. The search stops once the best expected improvement is negligible against the spread of the observations.

krig must provide std_error_at_point: Kriging, GEK, KPLS, KPLSK, GEKPLS or AbstractGPSurrogate. Given a surrogate without a predictive variance, this method raises an ArgumentError before the search starts rather than failing partway through it.

References

Jones, D.R., Schonlau, M. and Welch, W.J. (1998). Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13, 455-492.

surrogate_optimize!(obj, ::DYCORS, lb, ub, surrn, sample_type;
    maxiters = 100, num_new_samples = 100, needs_gradient = false)

Minimize obj with dynamic coordinate search.

DYCORS extends SRBF by changing how candidates are generated, not how they are ranked: candidates are Gaussian perturbations of the incumbent in a random subset of the coordinates rather than a design over a trust region. Each coordinate is perturbed with probability

$p_{select}(k) = \min(20/d, 1)\left(1 - \frac{\ln k}{\ln k_{max}}\right)$

which falls to zero over the run, so late iterations move along very few directions – the useful behaviour when the objective depends on only a handful of them. At least one coordinate is always perturbed. The perturbation width doubles after three consecutive improvements and halves after max(d, 5) consecutive failures. Candidates are ranked by the same weighted score as SRBF, so the two methods differ only in how candidates are generated.

References

Regis, R.G. and Shoemaker, C.A. (2013). Combining radial basis function surrogates and dynamic coordinate search in high-dimensional expensive black-box optimization. Engineering Optimization, 45(5), 529-555.

surrogate_optimize!(obj, sop::SOP, lb, ub, surr, sample_type;
    maxiters = 100, num_new_samples = min(500d, 5000), needs_gradient = false)

Minimize obj with surrogate optimization using Pareto center selection.

SOP maintains several search centers at once and picks them by non-dominated sorting on two criteria: the observed objective value, and the distance to the nearest evaluated point. Ranking centers this way spreads them between the promising and the unexplored parts of the domain, which is what makes the method parallel-friendly – sop.p centers are carried, and one candidate is proposed from each per iteration. A center whose proposal fails to improve the dominated hypervolume has its radius halved, and after enough failures it is placed on a tabu list.

num_new_samples is best set to min(500d, 5000) for a d-dimensional problem.

References

Krityakierne, T., Akhtar, T. and Shoemaker, C.A. (2016). SOP: parallel surrogate global optimization with Pareto center selection for computationally expensive single objective problems. Journal of Global Optimization, 64, 421-445.

Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley.