Skip to main content
SpringerLink
Log in

Robust optimization of noisy blackbox problems using the Mesh Adaptive Direct Search algorithm

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Blackbox optimization problems are often contaminated with numerical noise, and direct search methods such as the Mesh Adaptive Direct Search (MADS) algorithm may get stuck at solutions artificially created by the noise. We propose a way to smooth out the objective function of an unconstrained problem using previously evaluated function evaluations, rather than resampling points. The new algorithm, called Robust-MADS is applied to a collection of noisy analytical problems from the literature and on an optimization problem to tune the parameters of a trust-region method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Abramson, M.A., Audet, C., Dennis Jr., J.E., Le Digabel, S.: OrthoMADS: a deterministic MADS instance with orthogonal directions. SIAM J. Optim. 20(2), 948–966 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. Audet, C., Dennis Jr., J.E.: Analysis of generalized pattern searches. SIAM J. Optim. 13(3), 889–903 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  3. Audet, C., Dennis Jr., J.E.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(1), 188–217 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Audet, C., Dennis Jr., J.E.: A progressive barrier for derivative-free nonlinear programming. SIAM J. Optim. 20(1), 445–472 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Audet, C., Dennis Jr., J.E., Le Digabel, S.: Parallel space decomposition of the mesh adaptive direct search algorithm. SIAM J. Optim. 19(3), 1150–1170 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Audet, C., Ianni, A., Le Digabel, S., Tribes, C.: Reducing the number of function evaluations in Mesh Adaptive Direct Search algorithms. SIAM J. Optim. 24(2), 621–642 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  7. Audet, C., Orban, D.: Finding optimal algorithmic parameters using derivative-free optimization. SIAM J. Optim. 17(3), 642–664 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  8. Billups, S.C., Larson, J., Graf, P.: Derivative-free optimization of expensive functions with computational error using weighted regression. SIAM J. Optim. 23(1), 27–53 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  9. Huyer, W., Neumaier, A.: SNOBFIT—stable noisy optimization by branch and fit. ACM Trans. Math. Softw. 35(2), 9:1–9:25 (2008)

    Article  MathSciNet  Google Scholar 

  10. Chen, R., Menickelly, M., Scheinberg, K.: Stochastic optimization using a trust-region method and random models. Math. Program, 1–41 (2016)

  11. Choi, T.D., Kelley, C.T.: Superlinear convergence and implicit filtering. SIAM J. Optim. 10(4), 1149–1162 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  12. Deng, G., Ferris, M.C.: Adaptation of the UOBYQA algorithm for noisy functions. In: Proceedings of the 38th Conference on Winter Simulation, WSC ’06, pp. 312–319. Winter Simulation Conference (2006)

  13. Yang, D., Flockton, S.J.: Evolutionary algorithms with a coarse-to-fine function smoothing. IEEE Int. Conf. Evol. Comput. 2, 657–662 (1995)

    Google Scholar 

  14. Elster, C., Neumaier, A.: A grid algorithm for bound constrained optimization of noisy functions. IMA J. Numer. Anal. 15(4), 585–608 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  15. Epanechnikov, V.A.: Non-parametric estimation of a multivariate probability density. Theory Probab. Appl. 14(1), 153–158 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gould, N.I.M., Orban, D., Toint, Ph.L.: CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl. 60(3), 545–557 (2015). https://ccpforge.cse.rl.ac.uk/gf/project/cutest/wiki

  17. Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79(1), 157–181 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  18. Kostrowicki, J., Piela, L., Cherayil, B.J., Scheraga, H.A.: Performance of the diffusion equation method in searches for optimum structures of clusters of Lennard–Jones atoms. J. Phys. Chem. 95(10), 4113–4119 (1991)

    Article  Google Scholar 

  19. Larson, J., Billups, S.C.: Stochastic derivative-free optimization using a trust region framework. Comput. Optim. Appl. 64(3), 619–645 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  20. Le Digabel, S.: Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm. ACM Trans. Math. Softw. 37(4), 44:1–44:15 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  21. Le Digabel, S., Wild, S.M.: A Taxonomy of Constraints in Simulation-Based Optimization. Technical Report G-2015-57, Les cahiers du GERAD (2015)

  22. Li, J., Wu, C., Wu, Z., Long, Q.: Gradient-free method for nonsmooth distributed optimization. J. Global Optim. 61(2), 325–340 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  23. Liu, Q., Zeng, J., Yang, G.: MrDIRECT: a multilevel robust DIRECT algorithm for global optimization problems. J. Global Optim. 62(2), 205–227 (2015)

    MathSciNet  MATH  Google Scholar 

  24. Moré, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20(1), 172–191 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  25. Powell, M.J.D.: UOBYQA: unconstrained optimization by quadratic approximation. Math. Program. 92(3), 555–582 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  26. Selvan, S.E., Borckmans, P.B., Chattopadhyay, A., Absil, P.-A.: Spherical mesh adaptive direct search for separating quasi-uncorrelated sources by range-based independent component analysis. Neural Comput. 25(9), 2486–2522 (2013)

    Article  MathSciNet  Google Scholar 

  27. Shao, C.-S., Byrd, R.H., Eskow, E., Schnabel, R.B.: Global optimization for molecular clusters using a new smoothing approach. In: Biegler, L., Lorenz, T., Conn, A.R., Coleman, T.F., Santosa, F.N. (eds.) Large-Scale Optimization with Applications, Volume 94 of The IMA Volumes in Mathematics and its Applications, pp. 163–199. Springer, New York (1997)

    Chapter  Google Scholar 

  28. Sriver, T.A., Chrissis, J.W., Abramson, M.A.: Pattern search ranking and selection algorithms for mixed variable simulation-based optimization. Eur. J. Oper. Res. 198(3), 878–890 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  29. Van Dyke, B., Asaki, T.J.: Using QR decomposition to obtain a new instance of Mesh Adaptive Direct Search with uniformly distributed polling directions. J. Optim. Theory Appl. 159(3), 805–821 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  30. Wei, F., Wang, Y., Meng, Z.: A smoothing function method with uniform design for global optimization. Pac. J. Optim. 10(2), 385–399 (2014)

    MathSciNet  MATH  Google Scholar 

  31. Wu, Z.: The effective energy transformation scheme as a special continuation approach to global optimization with application to molecular conformation. SIAM J. Optim. 6(3), 748–768 (1996)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work was supported in part by FRQNT Grant 2015-PR-182098 and NSERC Grant RDCPJ 490744-15 in collaboration with Rio Tinto and Hydro-Québec.

Author information

Authors and Affiliations

  1. Département de mathématiques et génie industriel, École Polytechnique de Montréal, GERAD, C.P. 6079, Succ. Centre-ville, Montreal, QC, H3C 3A7, Canada

    Charles Audet, Amina Ihaddadene, Sébastien Le Digabel & Christophe Tribes

Authors
  1. Charles Audet
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Amina Ihaddadene
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sébastien Le Digabel
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Christophe Tribes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sébastien Le Digabel.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Audet, C., Ihaddadene, A., Le Digabel, S. et al. Robust optimization of noisy blackbox problems using the Mesh Adaptive Direct Search algorithm. Optim Lett 12, 675–689 (2018). https://doi.org/10.1007/s11590-017-1226-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-017-1226-6

Keywords

Search

Navigation