PaperlayerView exact revision on arXiv

Source-linked AI summary

Improving the Flexibility and Robustness of Model-Based Derivative-Free Optimization Solvers

Coralia Cartis, Jan Fiala, Benjamin Marteau, Lindon Roberts

arXiv:1804.00154v2math.OC

TL;DR

Derivative-free optimization is needed when derivatives are unavailable, evaluations are expensive, or objective values are noisy, but sampling and regression approaches can delay early progress. The paper presents DFO-LS and Py-BOBYQA with noise-robustness strategies, finding that multiple restarts improve performance without early deterioration and that DFO-LS can begin progress from two evaluations.

  • Problem

    Derivative-free optimization software is needed for expensive or noisy evaluations, while sampling and regression approaches can be slow to produce substantial early objective improvement.

  • Method

    The paper introduces DFO-LS for bound-constrained nonlinear least-squares problems using linear local residual models, and Py-BOBYQA for general objectives using interpolation-based trust-region models.

  • Results

    Multiple restarts improve noisy-problem performance without early loss associated with averaging or regression, while DFO-LS can make reasonable progress from as few as 2 objective evaluations.

  • Takeaways & Limitations

    Multiple restarts are a cheap robustness mechanism for noisy DFO that does not deteriorate early performance, and DFO-LS offers flexible low-cost initialization for expensive evaluations.

  • Takeaways & Limitations

    The regression construction can produce rank-deficient, non-full-dimensional models, and fixing this by updating the interpolation set may require two objective evaluations per iteration.

Abstract

from arXiv · show

We present DFO-LS, a software package for derivative-free optimization (DFO) for nonlinear Least-Squares (LS) problems, with optional bound constraints. Inspired by the Gauss-Newton method, DFO-LS constructs simplified linear regression models for the residuals. DFO-LS allows flexible initialization for expensive problems, whereby it can begin making progress from as few as two objective evaluations. Numerical results show DFO-LS can gain reasonable progress on some medium-scale problems with fewer objective evaluations than is needed for one gradient evaluation. DFO-LS has improved robustness to noise, allowing sample averaging, the construction of regression-based models, and multiple restart strategies together with an auto-detection mechanism. Our extensive numerical experimentation shows that restarting the solver when stagnation is detected is a cheap and effective mechanism for achieving robustness, with superior performance over both sampling and regression techniques. We also present our package Py-BOBYQA, a Python implementation of BOBYQA (Powell, 2009), which also implements robustness to noise strategies. Our numerical experiments show that Py-BOBYQA is comparable to or better than existing general DFO solvers for noisy problems. In our comparisons, we introduce a new adaptive measure of accuracy for the data profiles of noisy functions that strikes a balance between measuring the true and the noisy objective improvement.

1 Introduction

The paper develops flexible model-based DFO software for expensive and noisy optimization, focusing on nonlinear least-squares and general objectives. Its key strategies reduce initialization costs and improve noise robustness, with multiple restarts performing particularly well.

  • Motivation: DFO-LS targets expensive or noisy problems where finite differences are costly or derivatives cannot be accurately evaluated.It focuses on unconstrained or bound-constrained nonlinear least-squares problems, while also considering general nonlinear objectives.
  • Motivation: Model-based DFO methods construct trust-region models by interpolation, but typically require at least n + 1 evaluations before their first iteration.This startup cost can be prohibitive when objective evaluations are expensive.
  • Motivation: Noisy objectives can cause model-based solvers to stagnate at incorrect solutions, while sampling and regression improve robustness only after accumulating substantial problem information.These approaches therefore trade early-phase performance for robustness.
  • Contributions: DFO-LS introduces reduced initialization, noise-specific defaults, optional sample averaging and regression, and multiple restarts for nonlinear least-squares problems with optional bounds.It uses linear local models for residuals to reduce interpolation cost and can begin its main iteration after as few as 2 evaluations.
  • Results: Multiple restarts substantially improve DFO-LS performance on noisy problems, outperforming high sample averaging while avoiding early losses, extra user input, and expensive implementation.The approach can also improve performance on some noiseless problems, including by escaping local minima.
  • Contributions: Py-BOBYQA extends these robustness features to general objectives, while the paper proposes an adaptive noisy-function accuracy measure balancing true and noisy objective improvement.DFO-LS shows improved noise robustness over DFO-GN and DFBOLS, and Py-BOBYQA is comparable to or better than existing general DFO solvers on noisy problems.

2 General Algorithmic Framework

DFO-LS builds derivative-free linear residual models within a trust-region framework, using interpolation or regression-style constructions that can reduce initialization cost. It then forms a Gauss–Newton-like quadratic objective model and updates points to maintain useful geometry.

  • Model construction: DFO-LS models residuals linearly around the current iterate using evaluated points, allowing fewer than n interpolation points during early iterations.The reduced initialization option uses p+1 points with 1 ≤ p < n and selects a minimum-norm model solution.
  • Model construction: The residual model induces a quadratic model of the full objective with g_k = 2J_k^T r_k and H_k = 2J_k^T J_k.This gives the method a Gauss–Newton-like trust-region structure while remaining derivative-free.
  • Reduced initialization: When p < n, the minimum-norm interpolation model has Jacobian column rank p, so it is rank-deficient and not full-dimensional.The resulting model is constant along some directions regardless of the objective.
  • Reduced initialization: DFO-LS restores a full-dimensional model by lifting the n−p smallest singular values to the smallest nonzero singular value.An alternative random-direction extension has similar small-budget performance, whereas the SVD variant performs better for longer budgets and is the default.
  • Trust-region framework: The trust-region method accepts steps with sufficient decrease and expands the radius, rejects insufficient steps and contracts it, then updates the interpolation set and its geometry.Geometry-improving procedures are used to prevent degeneracy in the maintained point set.
  • Algorithm scope: DFO-LS differs from DFO-GN by supporting regression models, reduced initialization, variable scaling, noisy-problem parameters, and additional termination criteria.Its interpolation formulation is designed to improve robustness to noisy problems while reducing initialization cost.

3 New Algorithmic Features

DFO-LS adds practical mechanisms for expensive and noisy objectives, especially restart strategies that detect stagnation and refresh the local model. Experiments motivate moving-point soft restarts and auto-detection as effective default choices.

  • General features: DFO-LS adds noisy-problem defaults, termination criteria, geometry procedures, model updating, bound constraints, and optional variable scaling.Variables may be internally shifted and scaled to [0, 1] to improve conditioning.
  • Multiple restarts: Small trust-region radii can cease to indicate convergence under noise because nearby interpolation values fall within the noise level, causing stagnation.The resulting Jacobian changes can signal that the interpolation is capturing noise rather than objective behavior.
  • Multiple restarts: Restarts enlarge the trust region and move or rebuild interpolation points, reducing Jacobian changes so models are more likely to capture genuine objective information.The solver can then resume progress and reach higher accuracy.
  • Auto-detection: Auto-detection triggers a restart after sustained radius contraction and exponentially increasing Jacobian changes over recent iterations.The trigger uses both trust-region history and a linear fit to log ||J_k − J_{k−1}||_F.
  • Auto-detection: Approximately 15(n + 1) evaluations reached accuracy τ = 10−6 with auto-detected restarts, versus approximately 80(n + 1) without auto-detection.The auto-detection mechanism triggered restarts earlier and avoided iterations without progress.
  • Restart variants: Moving-point soft restarts outperform fixed-point soft restarts, while soft restarts use fewer evaluations than hard restarts.The default soft restart uses N = min(3, p), and repeated unsuccessful restarts can terminate the solver.
  • Noisy objectives: Numerical comparisons find multiple restarts better than sample averaging and regression models, so those alternatives are not DFO-LS defaults.The restart mechanism avoids the early performance loss associated with accumulating samples or regression information.

4 Testing Framework

The testing framework compares solver evaluation efficiency across expensive and noisy regimes using data profiles and problem-adjusted accuracy levels. Its adaptive noisy metric is intended to align observable progress with genuine objective reduction.

  • Performance measurement: The framework compares solvers by evaluations required to achieve a specified objective reduction, with budgets measured in simplex gradients, α(n_p + 1).This normalizes evaluation budgets across problems with different dimensions.
  • Performance measurement: Data profiles report the proportion of test problems solved within a given evaluation budget, while N_p measures true progress and eN_p measures observable progress.The framework compares and combines these two previously separate performance measures.
  • Adaptive accuracy: Problem-specific accuracy τ_p is chosen according to the noise level so noisy progress is measured using genuine objective decreases rather than sampling errors.For noiseless problems, τ_crit(p) = 0 and τ_p equals the common target τ.
  • Adaptive accuracy: Using a fixed τ_p = 10−5 can make noisy and true data profiles differ substantially, whereas the per-problem threshold makes their shapes and magnitudes much more consistent.Relative solver conclusions from the noisy profile then agree with those from the true profile in low- and long-budget regimes.
  • Test collections: The experiments use Moré–Wild problems for the noisy regime and medium-sized CUTEst problems for the expensive regime.The Moré–Wild set has 53 problems with 2 ≤ n ≤ 12, while the CUTEst collection has 60 problems with 25 ≤ n ≤ 120.
  • Noise models: Noisy evaluations include multiplicative and additive Gaussian residual noise, with expectations that are affine transformations of the true objective under the stated models.Ten runs are averaged for each noisy solver evaluation.

5 Numerical Studies of New DFO-LS Features

DFO-LS experiments evaluate reduced initialization, sample averaging, regression, and restart strategies for improving early progress and robustness under expensive or noisy evaluations.

  • Reduced Initialization Cost: Reduced initialization lets DFO-LS make progress with fewer evaluations than a single gradient evaluation, while preserving long-budget robustness.The benefit is strongest for short budgets and low accuracy; small-budget performance can be lower than with full initialization.
  • Sample Averaging: Larger sample sets improve robustness to Gaussian noise but require proportionally more serial evaluations, reducing performance for small-to-medium budgets.Using N = O(∆^-1) offers a compromise between early progress and overall robustness.
  • Regression: Regression with larger sample sets improves robustness, but is generally comparable to or slightly worse than sample averaging.The paper attributes this difference to sample averaging providing a better objective-decrease estimate at fixed noise level.
  • Multiple Restarts: Soft restarts that move xk provide the strongest robustness, achieving similar or better robustness than extensive averaging with fewer objective evaluations.The improvement is especially clear for additive χ2 noise and remains beneficial at smaller budgets.
  • Multiple Restarts: Adding sample averaging improves hard and fixed-point soft restarts, but not the default moving-point soft restarts, so averaging is not enabled by default.Moving-point soft restarts remain preferable with or without sample averaging.

6 Benchmark Comparisons of DFO-LS

Benchmark studies compare DFO-LS with established derivative-free least-squares solvers on smooth, noisy, and combined expensive-noisy problems, including the effects of restarts.

  • Benchmark Comparisons: On smooth problems, DFO-LS performs similarly to DFO-GN and DFBOLS, while two-evaluation initialization is only slightly worse on the CR set.The reduced initialization provides earlier progress without losing comparable performance over longer budgets.
  • Benchmark Comparisons: On noisy problems, DFO-LS solves a larger proportion of problems than DFBOLS and DFO-GN, with multiple restarts significantly improving robustness.The comparison uses noisy MW problems and DFO-LS’s adjustable default parameters.
  • Expensive & Noisy Problems: For combined expensive and noisy problems, reduced initialization enables progress within n + 1 evaluations for some problems but lowers small-budget performance.Long-budget, high-accuracy robustness remains similar to the full-initialization approach.
  • Multiple Restarts for Noiseless Problems: Multiple restarts slightly improve noiseless performance overall and can benefit selected problems.The experiments omit automatic restart detection for noiseless problems.
  • Multiple Restarts for Noiseless Problems: Restarts can help escape local minima or accelerate convergence after slow-progress termination.Examples include reaching the global minimum after escaping a higher local minimum and finding better objective values after a triggered restart.

7 Py-BOBYQA: DFO for General Objective Problems

Py-BOBYQA extends BOBYQA-style derivative-free trust-region optimization to support flexible model sizes and noise-robustness features for general objectives.

  • Method: Py-BOBYQA constructs an interpolation-based model, minimizes it within a trust region, and selects algorithm phases based on the step outcome.Its model is typically quadratic and can use between n + 1 and (n + 1)(n + 2)/2 interpolation points.
  • Contributions: Py-BOBYQA adds flexible interpolation-set sizes, parameter choices, sample averaging, and soft or hard restarts to improve robustness to noise.It also modifies termination conditions and supports n + 1 points, unlike the original BOBYQA requirement of at least n + 2.
  • Smooth Problems: For smooth problems, Py-BOBYQA has comparable performance with BOBYQA and NOWPAC.The evaluation covers MW, CFMR, and CR test collections under specified budgets and trust-region settings.
  • Noisy Problems: For noisy problems, Py-BOBYQA substantially outperforms BOBYQA and achieves similar or better robustness than SNOWPAC and STORM.Multiple restarts provide this robustness through a mechanism that is cheap to implement and does not penalize early performance.
  • Noisy Problems: Surrogate-based robustness can reduce performance, as illustrated by SNOWPAC’s runtime growth before achieving high accuracy on some problems.On one example, Py-BOBYQA reached accuracy 10^-11 before terminating on budget, while SNOWPAC timed out before reaching 10^-4.
  • Multiple Restarts: Multiple restarts may help Py-BOBYQA escape local minima without performance loss from the initial run, although they consume more computational budget.In the reported example, two restarts moved from a local minimum near 48.98 to the global minimum 0.

8 Conclusion

The paper presents DFO-LS and Py-BOBYQA as flexible, robust model-based DFO routines, with multiple restarts improving noisy-problem performance without early performance loss. DFO-LS also reduces initialization cost, while noisy-problem benchmarking uses an adjusted accuracy measure.

  • Software contributions: DFO-LS and Py-BOBYQA perform comparably to or better than state-of-the-art solvers on noisy problems with large, inexpensive budgets.The reported advantage is attributed to noise-appropriate algorithm parameters and multiple restarts.
  • Robustness to noise: Multiple restarts are cheap, avoid early performance deterioration seen with sample averaging and regression, and do not require extra user input typical of surrogate models.Both routines also retain optional sample-averaging strategies, while DFO-LS additionally supports regression models.
  • Robustness beyond noise: Multiple restarts can improve performance on smooth problems and may help the algorithm escape local minima.
  • Initialization cost: DFO-LS can begin making progress after as few as 2 objective evaluations instead of at least n + 1, enabling progress below the cost of one gradient evaluation.This reduced initialization has a medium-budget tradeoff but reaches the same long-term performance as full initialization.
  • Evaluation methodology: The paper uses a problem- and noise-adjusted accuracy level so noisy-objective progress more closely corresponds to progress in the underlying smooth objective.The authors propose this as a useful benchmarking approach for noisy solvers.

A Convergence Guarantees for DFO-LS

This appendix section introduces the convergence theory for DFO-LS and states that its results largely follow earlier arguments for DFO-GN.

  • Convergence theory: The convergence theory for DFO-LS largely follows the arguments previously developed for DFO-GN.

A.1 Accuracy of Regression Models

The appendix connects Λ-poised interpolation geometry to fully linear regression models for residuals and objectives under smoothness and boundedness assumptions.

  • Accuracy of Regression Models: Λ-poisedness is used as the key measure of interpolation-set geometry and guarantees accuracy of the regression models.
  • Definitions: Fully linear scalar and vector models are defined through bounded function and gradient or Jacobian approximation errors throughout the trust region.The definitions introduce constants independent of xk and ∆k for these bounds.
  • Assumptions: The accuracy result requires a C1 residual function with Lipschitz-continuous Jacobian and uniformly bounded residuals and Jacobians over the relevant region.Under these assumptions, the objective gradient is also Lipschitz continuous.
  • Accuracy result: If Yk is Λ-poised in the regression sense, the residual and objective models are fully linear in B(xk, ∆k).The appendix states this as Lemma A.4, with constants depending on the problem and poisedness parameters.
  • Interpolation geometry: For regression with p > n, it suffices to make a subset of n + 1 points Λ-poised, whereas reduced initialization covers the p < n case separately.

A.2 Global Convergence and Complexity

Global convergence requires a criticality phase that shrinks the trust region and restores model geometry when the model gradient is small. Under stated assumptions, DFO-LS converges to first-order stationary points with explicit iteration and evaluation bounds.

  • Global convergence: The criticality phase is triggered when ∥gk∥≤ϵC, then shrinks ∆k to be proportional to ∥gk∥ and ensures the model is fully linear.The described convergence version applies to noiseless objectives without reduced initialization.
  • Algorithm and assumptions: The convergence algorithm uses an initial interpolation set of size p + 1, criticality parameters ϵC, µ, and Λ, and a Cauchy-decrease condition for the trust-region step.A bounded model Hessian is also assumed.
  • Global convergence: Under Assumptions A.5, A.3, and A.6, the trust-region radius tends to zero and ∥∇f(xk)∥ tends to zero.
  • Complexity: Theorem A.8 and Corollary A.9 provide bounds on iterations and objective evaluations needed to reach ∥∇f(xk)∥<ϵ.The leading-order iteration bound is stated as O(κHκ2...).
  • Reduced initialization: Appending reduced initialization preserves convergence and increases the stated complexity bounds by n iterations and function evaluations.The increase reflects generating directions until full dimensionality is reached.

B General Features of DFO-LS

DFO-LS combines model-quality safeguards, bound handling, flexible termination, and noise-specific defaults to support robust nonlinear least-squares optimization.

  • Geometry-Improving Steps: Geometry-improving steps seek a Λ-poised interpolation set so the local model is fully linear within the trust region.
  • Geometry-Improving Steps: In practice, DFO-LS simplifies geometry improvement by replacing the point furthest from xk once per phase, rather than repeating the exact procedure.
  • Inclusion of Bound Constraints and Variable Scaling: Bound-constrained problems modify trust-region and geometry-improving steps, using TRSBOX and DFO-GN procedures.
  • Inclusion of Bound Constraints and Variable Scaling: Optional bound-based scaling shifts and scales variables so the feasible region becomes x ∈ [0, 1]^n, reducing potential ill-conditioning.
  • Termination Criteria: DFO-LS can terminate on a small objective, small trust region, evaluation budget, slow successful progress, or noise-level agreement.
  • Default Parameters for Noisy Problems: For noisy problems, modified defaults address inaccurate reductions that can cause unnecessary trust-region shrinkage and slower progress.
  • Other Differences: DFO-LS initializes with random orthonormal directions by default, while allowing fewer than n + 1 points during early iterations to reduce evaluation cost.

C Comparison of Sample Averaging and Regression

The paper compares sample averaging and regression as ways to reduce noise effects in model construction and objective-decrease measurements. Under comparable geometry, both can achieve similar model error for a fixed evaluation count, while averaging may estimate objective decrease better.

  • Noise affects DFO-LS mainly through model construction and measurement of objective decrease.
  • Sample averaging and regression produce comparable model errors under equivalent noise, geometry, and evaluation resources.
  • For fixed noise, sample averaging is expected to estimate objective decrease better, although its extra evaluations can affect overall performance.
  • For a linear noisy objective, sample averaging gives an unbiased estimate with reduced variance at each interpolation point.
  • Under strong Λ-poisedness, Gauss-Markov theory makes the regression estimator optimally unbiased for the linear model parameters.
  • Regression model error decreases inversely with N(p + 1), the total number of noisy evaluations used.

D General Objective Test Problems

The test set comprises medium-scale general-objective CUTEst problems with documented dimensions, bound constraints, variable parameters, and reference objective values.

  • Table 1 lists medium-scale general-objective problems from the CUTEst test set with their relevant problem details.
  • The table reports f(x∗) values used in (4.2) and gives parameters for variable-dimensional problems yielding each displayed n.
  • Problems marked * have bound constraints, while the reported n excludes fixed variables.
Loading 1804.00154v2…