PaperlayerView exact revision on arXiv

Source-linked AI summary

Derivative-free optimization methods

Jeffrey Larson, Matt Menickelly, Stefan M. Wild

arXiv:1904.11585v2math.OC

TL;DR

Derivative-free optimization addresses problems where black-box or simulation oracles provide no derivative information. This survey reviews methods for local continuous-valued, single-objective optimization; for strongly convex objectives with one-point bandit feedback, the best known WCC is O(ϵ^-2), rather than the O(ϵ^-1) rate attainable by gradient-based methods.

  • Problem

    Objective and constraint functions may be available only through black-box or simulation oracles without derivatives, motivating derivative-free optimization.

    Source: §1 · p. 3

  • Method

    The paper surveys derivative-free methods and analysis results, focusing on local optimization of continuous-valued, single-objective problems.

    Source: §1 · p. 3

  • Results

    For strongly convex objectives with one-point bandit feedback, the best known WCC is O(ϵ^-2), while gradient-based smooth strongly convex stochastic optimization attains O(ϵ^-1).

    Source: §4.2.1 · p. 34

  • Takeaways & Limitations

    The one-point bandit-feedback rate gap motivates study of two-point or multi-point bandit feedback.

    Source: §4.2.1 · p. 34

    The survey focuses on methods and cannot do justice to the application problems that drove their development and benefited from their implementations.

    Source: §1 · p. 3

Abstract

from arXiv · show

In many optimization problems arising from scientific, engineering and artificial intelligence applications, objective and constraint functions are available only as the output of a black-box or simulation oracle that does not provide derivative information. Such settings necessitate the use of methods for derivative-free, or zeroth-order, optimization. We provide a review and perspectives on developments in these methods, with an emphasis on highlighting recent developments and on unifying treatment of such problems in the non-linear optimization and machine learning literature. We categorize methods based on assumed properties of the black-box functions, as well as features of the methods. We first overview the primary setting of deterministic methods applied to unconstrained, non-convex optimization problems where the objective function is defined by a deterministic black-box oracle. We then discuss developments in randomized methods, methods that assume some additional structure about the objective (including convexity, separability and general non-smooth compositions), methods for problems where the output of the black-box oracle is stochastic, and methods for handling different types of constraints.

1 Introduction

Derivative-free optimization addresses problems where derivatives are unavailable, and this survey reviews local optimization methods for continuous-valued, single-objective problems. It emphasizes recent developments while acknowledging important scope omissions.

1 Introduction

  • Derivative-free methods are used from early scientific computing to modern AI tuning, and this survey emphasizes recent developments, with over half its references from the past ten years.Source: §1 · p. 3
  • The survey focuses on local minimization of continuous-valued, single-objective problems, omitting global optimization, multi-objective and discrete-variable tasks, and comprehensive application coverage.Source: §1 · p. 3

1.1 Alternatives to derivative-free optimization methods

  • Derivative-free methods may be chosen for convenience, but can limit performance in accuracy, expense, or problem size relative to gradient-based methods.Source: §1.1 · p. 4

1.1.1 Algorithmic differentiation

  • Algorithmic differentiation generates derivatives from mathematical functions expressed in code, exploiting structure and sparsity; its tools and applications have advanced, including for piecewise-smooth functions.Source: §1.1.1 · p. 5

1.1.2 Numerical differentiation

  • Numerical differentiation can supply derivative estimates from function values, but optimization methods must tolerate inexactness, and acceptable accuracy and evaluation expense determine practical use.Source: §1.1.2 · p. 5

1.2 Organization of the paper

  • The survey organizes methods by problem class: unconstrained deterministic, randomized, convex, structured-objective, stochastic, and constrained optimization.Source: §1.2 · pp. 5–6
  • It also briefly highlights related areas, including global and multi-objective optimization, and implementation considerations.Source: §1.2 · p. 6

2 Deterministic methods for deterministic objectives

The survey distinguishes deterministic methods for unconstrained optimization by how they choose candidate points. Direct-search methods use function-value comparisons, while model-based methods use a surrogate; some hybrids combine both.

2 Deterministic methods for deterministic objectives

  • Direct-search methods use function-value comparisons to determine candidate points.Source: §2 · p. 6
  • Model-based methods use a surrogate of the objective to determine candidate points.Source: §2 · p. 6
  • Hybrid methods combine direct-search and model-based ideas, blurring the distinction between the categories.Source: §2 · p. 6

2.1 Direct-search methods

Direct-search methods use function values without developing an approximate gradient; this section surveys simplex and directional variants and their convergence properties.

2.1.1 Simplex methods

  • Nelder and Mead [1965] add expansion and contraction to reflection and shrink, allowing the simplex to distort to account for possible objective curvature.Figure 2.1 depicts the original simplex and these four operations.Source: §2.1.1 · pp. 6–7, Figure 2.1 · p. 7
  • Nelder–Mead has counterexamples to convergence to stationary points, including strictly convex, thrice-continuously differentiable functions in R2 where it fails to reach the lone stationary point.In McKinnon’s example, the method repeatedly performs inner contraction.Source: §2.1.1 · p. 7
  • Nelder–Mead convergence results cover restricted settings, including one-dimensional strictly convex functions and twice-continuously differentiable functions with positive-definite Hessians under a restricted variant.Gao and Han [2012] also show contraction and expansion satisfy descent on uniformly convex functions.Source: §2.1.1 · p. 7

2.1.2 Directional direct-search methods

  • Directional direct-search evaluates poll points x_k + α_k d; pattern search derives directions from simplex edges and has a stationary-point subsequence under compact continuous level sets.The result allows the limit point to be stationary, nondifferentiable, or not continuously differentiable.Source: §2.1.2 · pp. 8, 10
  • GPS convergence results distinguish smooth objectives, which can yield zero-gradient limit points, from Lipschitz nonsmooth objectives, which yield nonnegative directional derivatives along recurring poll directions.For second-order results, GPS variants require recurring signed orthonormal-basis directions and, in one approach, suitable Hessian approximations.Source: §2.1.2 · p. 10
  • MADS can establish nonnegative Clarke directional derivatives in all directions at limit points when its poll directions become asymptotically dense.The cited result also extends to constrained problems over feasible directions.Source: §2.1.2 · p. 11
  • Under specified conditions, Vicente [2013] obtains an O(ϵ^-2) first-order WCC, while Gratton et al. [2016] obtain an O(ϵ^-3) second-order WCC; the survey reports no known MADS WCC.The first result assumes an empty search step and sufficient decrease; the second augments DDS with an approximate Hessian.Source: §2.1.2 · p. 12

2.2 Model-based methods

This section reviews model-based derivative-free methods, focusing on smooth surrogate models and trust-region approaches. It covers model quality and construction, convergence guarantees and evaluation bounds, model-decrease conditions, and specialized variants.

2.2.1 Quality of smooth model approximation

  • Fully linear models bound function and gradient errors by O(∆²) and O(∆), while fully quadratic models bound function, gradient, and Hessian errors by O(∆³), O(∆²), and O(∆), respectively.These bounds support using predicted model reduction to obtain attainable reduction in the objective as ∆ becomes smaller.Source: §2.2.1 · p. 13

2.2.2 Polynomial models

  • When evaluations are expensive, underdetermined quadratic models reduce the required interpolation points by choosing the interpolating model whose Hessian is closest in Frobenius norm to a specified matrix; NEWUOA implements this strategy.Fully quadratic models can require (n + 1)(n + 2)/2 points, which may be burdensome to obtain repeatedly.Source: §2.2.2 · pp. 15–16
  • Polynomial interpolation and regression models depend on sample-point geometry: Λ-poisedness measures how well points support local approximation, and Λ-poised linear regression models can be fully linear under Lipschitz-gradient assumptions.Having enough points alone may not ensure a nonsingular interpolation system when n > 1.Source: §2.2.2 · pp. 14–16
  • Low-degree polynomial models are favored because they must be minimized efficiently over a trust region, yet quadratic subproblems remain difficult non-convex problems, making solver implementation important when evaluations are scarce.Source: §2.2.2 · p. 18

2.2.3 Radial basis function interpolation models

  • Radial basis function models can represent varied nonlinear behavior with less restrictive geometric requirements on interpolation points, and a linear polynomial component can yield fully linear local approximations of smooth functions.The required polynomial degree depends on the RBF: cubic functions require a linear polynomial, while multiquadrics require a constant polynomial.Source: §2.2.3 · p. 18

2.2.4 Trust-region methods

  • Derivative-free trust-region methods compare actual and predicted reduction with a ρ-test, explicitly test model quality, and shrink ∆k when quality fails; unlike traditional methods, ∆k → 0 as they converge.Methods differ in how they build and manage the interpolation set, and may add points to improve model quality.Source: §2.2.4 · pp. 18, 20
  • Convergence analyses typically require each trust-region step to achieve at least a fixed fraction of the Cauchy-step model decrease, ensuring square-summable decreases when ∆k → 0.For quadratic models, subproblem solvers often guarantee this condition; its satisfaction has also been demonstrated for radial basis function models [Wild et al., 2008].Source: §2.2.4 · p. 20
  • Algorithm 3 has a WCC bound in O(ϵ−2) [Garmanjani et al., 2016], matching DDS methods [Vicente, 2013], and a second-order WCC bound in O(ϵ−3) with fully quadratic models [Gratton et al., 2019a].Under f ∈ LC1, algorithms in this framework have first- and second-order convergence guarantees [Conn et al., 2009a].Source: §2.2.4 · pp. 20–21
  • Powell’s UOBYQA can converge superlinearly near strict convexity with minor modifications, and dynamically adapts separate neighborhoods for model quality and trust-region steps [Han and Liu, 2004; Powell, 2010, 2012].Source: §2.2.4 · p. 21
  • Wedge methods enforce Λ-poisedness; hierarchical models can incorporate gradients [Alexandrov et al., 1998]; deterministic-noise variants use grid projection or Gaussian convolution [Elster and Neumaier, 1995; Maggiar et al., 2018].Source: §2.2.4 · p. 21

2.3 Hybrid methods and miscellanea

The section surveys hybrid and finite-difference approaches, implicit filtering, adaptive regularization, line-search methods, and methods for non-smooth objectives. It describes their mechanisms, convergence results, and scope.

2.3 Hybrid methods and miscellanea

  • Hybrid methods blur the direct-search/model-based distinction; SID-PSM uses a quadratic model minimized over a trust region for its search step.The model may be obtained by minimum-Frobenius-norm interpolation or regression.Source: §2.3 · p. 21

2.3.1 Finite differences

  • Finite-difference approaches estimate derivatives along directions, and some methods dynamically change the difference parameter or direction; under roundoff error, the familiar scale h ∈ O(√ϵ∞) arises when Lg is of order one.The cited discussion also considers choosing the difference parameter by minimizing a mean-squared-error bound when function error is modeled as a stationary stochastic process.Source: §2.3.1 · pp. 21–22

2.3.2 Implicit filtering

  • Implicit filtering uses central finite differences in a Newton-like local method, evaluating all polling points each iteration; noisy-objective convergence results require specific smooth-plus-small-noise conditions.Gilmore and Kelley [1995] show convergence to local minima when the high-frequency, low-amplitude component vanishes quickly near minimizers of the smooth component; Choi and Kelley [2000] show superlinear convergence under a specified step-size rule.Source: §2.3.2 · p. 22

2.3.3 Adaptive regularized methods

  • ARC-DFO achieves a WCC bound of O(ϵ^-3/2), improving on DDS and trust-region bounds in ϵ-dependence under the stronger assumption f ∈ LC2.Its subproblem regularizes third-order model behavior, and it shrinks the finite-difference parameter when it is too large relative to the trial step or model gradient.Source: §2.3.3 · pp. 22–23

2.3.4 Line-search-based methods

  • Line-search methods include pattern-search hybrids and directions computed from previously evaluated points; non-monotone strategies can accommodate directions that are not guaranteed to descend.The VXQR method applies a QR-factorization-based direction to problems with n = 1000.Source: §2.3.4 · p. 23

2.3.5 Methods for non-smooth optimization

  • Methods for non-smooth objectives include gradient sampling with finite-difference estimates and smoothing, discrete-gradient subgradient descent, and methods for composites f = h ◦ F.Composite methods exploit known nonsmooth h and smooth F, making them less general than the other non-smooth methods discussed.Source: §2.3.5 · p. 24

3 Randomized methods for deterministic objectives

Randomized methods for deterministic objectives trade deterministic behavior for potentially promising theoretical properties. The survey covers random search, randomized direct search, and randomized trust-region methods, with analyses that provide convergence guarantees under stated assumptions.

3.1 Random search

  • The survey distinguishes random search approaches, including pure random search and Nesterov random search, for minimizing deterministic objectives.Pure random search is easy to implement and can scale well for simultaneous function evaluations.Source: §3.1 · p. 24, §3.1.1 · p. 24

3.1.1 Pure random search

  • Pure random search samples points from the domain and retains the best observed point; when the sampling procedure is independent of observed function values, the points can be generated beforehand and evaluated in parallel.Under a condition on the sampling procedure, its best observed value converges in probability to the global minimum value.Source: §3.1.1 · pp. 24–25

3.1.2 Nesterov random search

  • O(ϵ^-3) evaluations suffice for Nesterov random search’s approximate optimality condition when f is non-smooth and non-convex; for non-convex f with Lipschitz-continuous gradients, the bound is O(ϵ^-2).These are worst-case complexity results; the analysis also relies on step sizes chosen using parameters that may not be available to the method.Source: §3.1.2 · pp. 26–27

3.2 Randomized direct-search methods

  • Randomization in direct search aims to reduce per-iteration function evaluations from O(n) to O(1) while retaining a global convergence guarantee.This discussion focuses on unconstrained problems with sufficiently smooth objectives; random polling in MADS serves a different purpose.Source: §3.2 · p. 27
  • When randomized polling directions include a descent direction with probability p > 1/2, the direct-search method reaches ||∇f(xk)|| ≤ ϵ within O(ϵ^-2) evaluations with probability increasing exponentially to 1 as ϵ → 0.This result assumes f has Lipschitz-continuous gradients and the stated probabilistic descent conditions hold.Source: §3.2 · p. 27

3.3 Randomized trust-region methods

  • With probability p > 1/2 of obtaining probabilistically fully linear models, randomized trust-region methods converge almost surely; a later analysis gives the same high-probability worst-case complexity bound as randomized direct search, up to constants.The almost-sure result requires additional standard assumptions on the trust-region algorithm.Source: §3.3 · p. 28

4 Methods for convex objectives

This section surveys how convexity shapes deterministic complexity bounds and motivates stochastic derivative-free methods framed as convex bandit learning. It covers one- and two-point feedback guarantees and limitations, including lower-bound tightness, norm choice, and convergence bounds under strong convexity or bounded-variance oracle assumptions.

4.1 Methods for deterministic convex optimization

  • For smooth convex DDS, Dodangeh and Vicente [2016] obtain O(n^2L_g^2ϵ^-1), while Konečný and Richtárik [2014] obtain O(n^2L_gϵ^-1) assuming known L_g.With strong convexity, both works provide logarithmic dependence on ϵ^-1; Dodangeh and Vicente also establish R-linear convergence under additional assumptions.Source: §4.1 · p. 29
  • Nesterov and Spokoiny [2017] give randomized convex bounds of O(ϵ^-1) for smooth objectives, O(log(ϵ^-1)) with strong convexity, and O(ϵ^-1/2) for an accelerated variant.Their O(ϵ^-2) result for nonsmooth convex objectives requires exact directional derivatives, so it is not derivative-free.Source: §4.1 · p. 30

4.2 Methods for convex stochastic optimization

  • Expected regret bounds imply stochastic convex optimization error bounds, but the converse generally fails; Shamir [2013] and Hazan et al. [2014] establish gaps for strongly convex quadratics and logistic regression.The survey groups derivative-free convex bandit methods by one-point versus two-point or multi-point feedback and focuses on optimization error.Source: §4.2 · p. 32

4.2.1 One-point bandit feedback

  • One-point methods have best known bounds of O(nϵ^-3) for smooth convex and O(n^2ϵ^-2) for smooth strongly convex problems, short of the O(ϵ^-1) rate attainable by gradient methods.The survey identifies this gap as motivation for two-point feedback.Source: §4.2.1 · pp. 33–34
  • Under derivative sparsity, Wang et al. [2018] reduce polynomial dimension dependence to logarithmic dependence, obtaining O(log(d)^(3/2)n_z^2ϵ^-3) when ∥∇f(x)∥_0 ≤ n_z ≪ n.For strongly convex β-smooth objectives, Bach and Perchet [2016] obtain O(n^2ϵ^-1/c) asymptotically as β→∞, reaching Shamir [2013]’s lower bound.Source: §4.2.1 · pp. 33–34

4.2.2 Two-point (multi-point) bandit feedback

  • Two-point feedback with a shared oracle realization achieves O(ϵ^-1), matching the optimal ϵ-dependence and avoiding the gap seen with one-point feedback.Mirror-descent methods also use two-point gradient estimates with Bregman-divergence proximal steps.Source: §4.2.2 · pp. 34–35
  • For typically sparse machine-learning solutions, an ℓ1-strongly-convex ψ (e.g., ψ=||·||1) may be preferable to p=2 in theory and practice.Such WCCs for methods like Algorithm 7 help explain the popularity of mirror-descent methods in machine learning.Source: §4.2.2 · p. 35
  • Duchi et al. [2015] show the convex Lipschitz two-point lower bound matches best-known WCCs up to constants, is of order ε^-2, and is only √n worse than Agarwal et al. [2009] derivative bounds.The ε-dependence matches Agarwal et al. [2009]’s result for f∈LC0.Source: §4.2.2 · p. 35
  • Under strong convexity with f∈LC0, Agarwal et al. [2010] give O(n^2 ε^-1), while Gasnikov et al. [2017] improve its n-dependence using a method like Algorithm 7.Source: §4.2.2 · p. 35
  • For convex f∈LC1, Agarwal et al. [2010] obtain O(n^2 ε^-1) with uniformly bounded oracle norms, while bounded variance supports a different WCC.Ghadimi and Lan [2013] give O(max{n L_g ||x0−x*|| ε^-1, n σ^2 L_g ||x0−x*|| ε^-2}) when Eξ[||gμ(x;u;ξ)−∇f(x)||^2]≤σ^2; Nesterov and Spokoiny [2017] hinted at a similar bound with worse n-dependence and different ξ assumptions.Source: §4.2.2 · p. 35

5 Methods for structured objectives

This section surveys methods that exploit known structure in black-box objectives, including least-squares form, sparsity, non-smooth compositions, and bilevel or minimax structure. Its methods use that structure to design models, search directions, or subproblems and establish convergence or complexity results under stated assumptions.

5 Methods for structured objectives

  • The section reviews methods designed to exploit known objective structure, which may offer practical gains over general-purpose methods.The structures considered include non-linear least squares, sparsity, composite forms, and minimax-based forms.Source: §5 · pp. 35–36

5.1 Non-linear least squares

  • For non-linear least squares, residual models support trust-region methods resembling Levenberg–Marquardt; under zero-residual assumptions, they achieve the same local quadratic convergence rate.A Gauss–Newton-like method also converges to stationary points when the residual is positive, with slightly weaker theoretical rate guarantees.Source: §5.1 · pp. 36–37

5.2 Sparse objective derivatives

  • Sparsity assumptions can reduce dimension dependence from polynomial to logarithmic, while unknown sparse Hessians admit fully quadratic interpolation from O((nz + n) log(nz + n) log(n)) random points.For the unknown-sparsity result, the sample count replaces O(n^2) points under stated assumptions.Source: §5.2 · p. 38

5.3 Composite non-smooth optimization

  • Methods for composite non-smooth objectives exploit known structure in h, while treating F as differentiable or approximating its derivatives without requiring derivative access.The survey also considers objectives for which no structural information is used, and methods that exploit particular forms of non-smoothness.Source: §5.3 · p. 38

5.3.1 Convex h

  • For convex known-form h, trust-region methods model the black-box F and use Ψ as a stationarity measure; convexity is required for that interpretation.The form of h also affects the difficulty of solving the trust-region subproblem.Source: §5.3.1 · p. 39

5.3.2 Non-convex h

  • For non-convex h, smoothing methods have an O(ϵ^-3) evaluation bound under stated conditions, but Clarke-stationary convergence additionally requires gradient consistency.The survey notes that non-convex h makes composite minimization more challenging and that the local model may no longer underestimate h.Source: §5.3.2 · pp. 40–41

5.4 Bilevel and general minimax problems

  • For bilevel problems, derivative-free methods approximate the upper-level objective by solving the lower-level problem sufficiently accurately; outer-approximation methods can yield Clarke-stationary limit points.The cited analyses rely on particular assumptions, including strict convexity of the lower-level problem for some methods and convexity in x for others.Source: §5.4 · p. 41

6 Methods for stochastic optimization

This section surveys derivative-free methods for stochastic objectives, where function values are random and gradient-based stochastic approximation is not directly applicable, covering stochastic approximation and sample-average methods, direct search, model-based methods, and bandit feedback. It also reviews bandit-feedback methods with convergence guarantees for variance-reduced estimators and conditional-gradient updates.

6.1 Stochastic and sample-average approximation

  • Common random numbers yield a convergence-rate exponent γ = 1/2 for central differences, while SPSA uses two function evaluations per iteration and achieves rates matching those of Kiefer–Wolfowitz methods.For forward differences, the best rate for Kiefer–Wolfowitz remains γ = 1/3 even with common random numbers; forward differences in Algorithm 7 can attain γ = 1/2. SPSA’s convergence results hold under appropriate assumptions.Source: §6.1 · p. 44
  • Sample-average approximation replaces the stochastic problem with deterministic sample-path problems, with retrospective and adaptive sampling schemes supporting convergence analyses.Retrospective methods use predetermined sample-size and accuracy sequences; dynamically adjusted sampling can balance deterministic and stochastic errors, and convergence rates have been established for a variant using independent samples each iteration.Source: §6.1 · pp. 44–45

6.2 Direct-search methods for stochastic optimization

  • Stochastic direct-search methods modify simplex, GPS, DDS, and implicit-filtering approaches to address noisy evaluations, with convergence results under specified sampling or noise conditions.Results include almost-sure convergence for GPS under additive unbiased Gaussian noise, consistency for DDS with increasing sample sizes, and first-order stationarity for a smoothed implicit-filtering method on a bound-constrained nonsmooth composite problem.Source: §6.2 · pp. 45–46

6.3 Model-based methods for stochastic optimization

  • Model-based trust-region methods adapt derivative-free models to stochastic objectives, including probabilistically fully linear models that can replace stochastic gradient estimators.For a model-based method by Chen et al. [2018a], Blanchet et al. [2019] establish E[T_ϵ] ∈ O(ϵ^-2); related line-search bounds are O(ϵ^-2), O(ϵ^-1), and O(log(ϵ^-1)) for non-convex, convex, and strongly convex objectives, respectively. Variable evaluations per iteration mean these bounds do not directly reveal total function-evaluation work.Source: §6.3 · pp. 46–47

6.4 Bandit feedback methods

  • For non-convex stochastic bandit optimization, Ghadimi and Lan [2013] prove a weak complexity result under a bounded-variance assumption on the gradient estimator.The cited passage states that they bound the randomized number of iterations needed to attain a criterion, but does not provide that criterion or the bound’s expression.Source: §6.4 · pp. 47–48
  • For sufficiently large σ^2, Ghadimi and Lan [2013] obtain a WCC of type (53) in O(n^2ε^-4).Their stationarity condition uses the squared gradient norm, unlike conditions in (34) or (53); the passage also gives O(max{nLgRxε^-1, nLgRxσ^2ε^-2}).Source: §6.4 · p. 48
  • Balasubramanian and Ghadimi [2018, 2019] use two-point bandit feedback in a derivative-free conditional-gradient method, obtaining a WCC of type (53) that grows like ε^-4 for bounded Ω.Their gradient estimator defines a linear model minimized over Ω to produce a trial step.Source: §6.4 · p. 48
  • Liu et al. [2018] prove a WCC of type (72) in O(nε^-1 + b^-1); Gu et al. [2016] establish a similar result asynchronously.Here b is the size of a minibatch drawn with replacement; Gu et al. use minibatches for variance reduction in an asynchronous parallel computing environment.Source: §6.4 · p. 48

7 Methods for constrained optimization

This section surveys derivative-free methods for constrained optimization, organizing them by constraint type and whether feasibility may be relaxed. It covers algebraic and black-box simulation constraints, methods for managing feasibility and difficult constraints, and convergence results.

7 Methods for constrained optimization

  • A problem remains derivative-free if any constraint lacks an available (sub)gradient, even when the objective gradient is available; constraints may be algebraic, simulation-based, or hidden.Hidden constraints are unspecified and are detected when an evaluation fails or leaves a function undefined.Source: §7 · pp. 48–49

7.1 Algebraic constraints

  • Algebraically available constraints can be represented as a finite collection of inequalities; equality constraints can be encoded with both signs, but this may hamper theoretical and empirical performance.Source: §7.1 · p. 50

7.1.1 Relaxable algebraic constraints

  • For relaxable algebraic constraints, exact penalties preserve local minima for sufficiently large finite penalties, unlike quadratic penalties; augmented Lagrangians are smooth and convex when the constraints are, with nonnegative multipliers and penalty parameter.Penalty parameters are dynamically updated, typically to promote feasibility.Source: §7.1.1 · pp. 50–51
  • Lewis and Torczon [2002] prove global convergence of an augmented-Lagrangian derivative-free method to first-order KKT points; Audet et al. [2015] extend MADS convergence to linear equalities by reformulating them away.The [2002] method approximately minimizes the augmented Lagrangian using pattern search; the [2015] reformulation may reduce the number of variables.Source: §7.1.1 · p. 51
  • Filter methods manage objective value and constraint violation as competing objectives, while model-based methods solve subproblems using local models of the objective and constraints, often with a trust region.Filters adapt their nondominated-point sets to identify feasible points; model-based methods may impose trust regions to monitor model quality.Source: §7.1.1 · pp. 51–52

7.1.2 Unrelaxable algebraic constraints

  • Unrelaxable constraints must remain feasible so objective evaluations are meaningful, but model-based methods may be unable to build κ-fully linear models using only feasible points in thin regions.This difficulty arises when constraints are so narrowly angled that feasible interpolation points cannot provide the required model quality.Source: §7.1.2 · pp. 53–54
  • Unrelaxable discrete constraints require evaluations at valid discrete inputs; derivative-free methods adapt pattern search, MADS, and mixed-variable polling to keep candidate points feasible.BFO aligns poll points with discrete constraints and recursively fixes subsets of discrete variables.Source: §7.1.2 · p. 54

7.2 Simulation-based constraints

  • Filter methods trade off objective improvement and constraint violation; examples use probabilistic acceptability with Gaussian processes or fully linear models with first-order KKT limit points.Audet and Dennis, Jr. [2004] accept steps improving either the objective or violation, although examples in Audet [2004] show nonconvergence to stationary points.Source: §7.2 · p. 55
  • Extreme barriers exclude infeasible points, while progressive barriers combine penalties for relaxable constraints with barriers for unrelaxable constraints and can converge to Clarke stationary points.The progressive-barrier method maintains a non-increasing violation threshold; NOMAD [Le Digabel, 2011] lets users choose filter, progressive-barrier, or extreme-barrier approaches.Source: §7.2 · pp. 55–56
  • Other approaches include penalty line searches, trust-funnel methods for equality constraints, augmented Lagrangians, and SQP using a violation-reduction step followed by a null-space subproblem.The line-search methods use exact or quadratic penalties; trust-funnel methods avoid merit functions and filters, while Tröltzsch [2016] uses modeled gradients and an exact-penalty acceptance rule.Source: §7.2 · pp. 56–57
  • Modeled constraints drive subproblem methods including COBYLA [Powell, 1994], which uses linear interpolation models and constrained subproblems, and MADS variants using quadratic or treed Gaussian process models.COBYLA handles equality and inequality constraints; the cited MADS approaches accept feasible steps or use models to order poll points with a filter.Source: §7.2 · p. 56
  • Restricted domains promote feasibility before convergence by enforcing algebraic constraints and tightening modeled simulation-based constraints; Regis [2013] adjusts restrictions based on recent feasibility.The motivation is to avoid feasibility being established only asymptotically; Regis [2013] uses radial basis function surrogates and a constraint-restoration phase for infeasible points.Source: §7.2 · p. 57
  • Trust-region methods restrict modeled constraints through local convexification or envelopes; Augustin and Marzouk [2014] prove asymptotic first-order criticality from feasible starts.Regis and Wild [2017] choose restrictions that keep trust-region subproblems nonempty and stop restricting near the constraint level set.Source: §7.2 · p. 57
  • Two-phase methods separate feasibility from objective reduction: Müller and Woodbury [2017] use cubic RBF constraints, while Bajaj et al. [2018] bound modeled violations by feasibility-phase results.Müller and Woodbury first minimize constraint violations simultaneously; Bajaj et al. use a quadratic-penalty feasibility phase followed by objective optimization under algebraic constraints and modeled-violation bounds.Source: §7.2 · pp. 57–58
  • Approximate normal and tangent cones can test approximate stationarity, including for non-quantifiable black-box constraints [Hare and Lewis, 2005].Davis and Hare [2013] approximate normal cones with simplex gradients when black-box constraints are quantifiable.Source: §7.2 · p. 58

8 Other extensions and practical considerations

The survey extends derivative-free optimization to parallel evaluation, multistart and global search, multi-objective problems, and multifidelity settings. These extensions offer varied strategies, while the authors identify several of these areas as open avenues for research.

8.1 Methods allowing for concurrent function evaluations

  • Concurrent evaluations can shorten wall-clock time, but the amount of useful concurrency depends on the method.Examples include parallel poll directions, finite-difference evaluations, stochastic gradient estimates, and component functions of separable objectives.Source: §8.1 · pp. 58–59

8.2 Multistart methods

  • Multistart tackles uncertain local-minimum structure by launching local optimization from different points, including selected uniform samples in MLSL.Under assumptions on minimizer separation and the local method, MLSL almost surely identifies all local minima using only finitely many local starts; variable evaluation times can make batched work inefficient.Source: §8.2 · p. 59

8.3 Other global optimization methods

  • Global methods can guarantee minimizer identification by dense sampling; DIRECT achieves dense centres through rectangle partitioning without requiring a known Lipschitz constant.DIRECT's score combines rectangle side length and centre value, and its performance can be significantly affected by adding a constant to the objective.Source: §8.3 · p. 60

8.4 Methods for multi-objective optimization

  • Multi-objective extensions of direct search and MADS establish Pareto-stationarity results, while other methods provide such guarantees under stated conditions.Direct-multisearch limits stationarity to directions appearing infinitely often; MADS-based methods show it for refining points, and other results require objectives in LC1 or asymptotically dense search directions.Source: §8.4 · pp. 61–62
  • Implicit filtering has also been extended to multiple objectives, with every accumulation point shown to be Pareto stationary.The method separately approximates objective gradients and combines them to generate search directions; most methods aim to establish stationarity, and comparisons of approximate Pareto sets are not straightforward.Source: §8.4 · pp. 61–62

8.5 Methods for multifidelity optimization

  • Multifidelity methods seek to reduce costly high-fidelity evaluations by using cheaper lower-fidelity objectives.Approaches include refining fidelity after unsuccessful iterations, multilevel coordinate-search, trust-region models of inter-fidelity error, and co-kriging surrogates.Source: §8.5 · p. 62
  • Derivative-free methods for multifidelity, multi-objective, and concurrent or parallel optimization remain open areas of future research.Source: §8.5 · p. 62

Appendix: Collection of WCC results

The appendix collects selected worst-case complexity bounds as upper bounds on function evaluations needed to meet specified conditions. It omits algorithm-parameter dependence to make method comparisons easier.

Appendix: Collection of WCC results

  • Table 8.1 reports upper bounds N_ϵ on function evaluations needed to meet specified stationarity conditions.The appendix presents these bounds in evaluation-complexity form because that measure is often of greater interest than iteration complexity.Source: Appendix: Collection of WCC results · p. 63, Table 8.1 · p. 64
  • The table omits dependence on algorithmic parameters, while including additional constants when particularly informative.Most listed methods do not require knowledge of the relevant Lipschitz constants; the stated exceptions are Nesterov and Spokoiny [2017] and Konečný and Richtárik [2014].Source: Appendix: Collection of WCC results · p. 63
  • Constructing probabilistically fully quadratic or fully linear models with m much smaller than the full quadratic sample count remains an open question.For p = 1, fully quadratic models can be guaranteed using O(n^2) points, while fully linear models can be guaranteed using O(n) points.Source: Appendix: Collection of WCC results · p. 66
  • For p = 1, Gratton et al. [2018] yields a rate weaker by a factor of Lg for fully quadratic models, but comparable to Garmanjani et al. [2016] for fully linear models.The quadratic comparison is against Gratton et al. [2016].Source: Appendix: Collection of WCC results · p. 66
Loading 1904.11585v2…