Svoboda | Graniru | BBC Russia | Golosameriki | Facebook

Algorithm 909: NOMAD: Nonlinear Optimization with the MADS Algorithm

Author:

Sébastien Le DigabelAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 37, Issue 4

Article No.: 44, Pages 1 - 15

https://doi.org/10.1145/1916461.1916468

Published: 01 February 2011 Publication History

Abstract

NOMAD is software that implements the Mesh Adaptive Direct Search (MADS) algorithm for blackbox optimization under general nonlinear constraints. Blackbox optimization is about optimizing functions that are usually given as costly programs with no derivative information and no function values returned for a significant number of calls attempted. NOMAD is designed for such problems and aims for the best possible solution with a small number of evaluations. The objective of this article is to describe the underlying algorithm, the software’s functionalities, and its implementation.

Supplementary Material

ZIP File (909.zip)

Software for NOMAD: Nonlinear Optimization with the MADS Algorithm

Download
2.35 MB

References

[1]

Abramson, M. 2004. Mixed variable optimization of a load-bearing thermal insulation system using a filter pattern search algorithm. Opt. Eng. 5, 2, 157--177.

[2]

Abramson, M. and Audet, C. 2006. Convergence of mesh adaptive direct search to second-order stationary points. SIAM J. Opt. 17, 2, 606--619.

Digital Library

[3]

Abramson, M., Audet, C., Chrissis, J., and Walston, J. 2009a. Mesh adaptive direct search algorithms for mixed variable optimization. Opt. Lett. 3, 1, 35--47.

[4]

Abramson, M., Audet, C., and Dennis, J. 2007. Filter pattern search algorithms for mixed variable constrained optimization problems. Pac. J. Opt. 3, 3, 477--500.

[5]

Abramson, M., Audet, C., Dennis, J., and Le Digabel, S. 2009b. OrthoMADS: A deterministic MADS instance with orthogonal directions. SIAM J. Opt. 20, 2, 948--966.

Digital Library

[6]

Aoudjit, H. 2010. Planification de la maintenance d’un parc de turbines-alternateurs par programmation mathématique. Ph.D. dissertation. École Polytechnique de Montréal, Montréal, P.Q., Canada.

[7]

Audet, C. 2004. Convergence results for pattern search algorithms are tight. Opt. Eng. 5, 2, 101--122.

[8]

Audet, C. and Dennis, J. 2001. Pattern search algorithms for mixed variable programming. SIAM J. Opt. 11, 3, 573--594.

Digital Library

[9]

Audet, C. and Dennis, J. 2003. Analysis of generalized pattern searches. SIAM J. Opt. 13, 3, 889--903.

Digital Library

[10]

Audet, C. and Dennis, J. 2004. A pattern search filter method for nonlinear programming without derivatives. SIAM J. Opt. 14, 4, 980--1010.

Digital Library

[11]

Audet, C. and Dennis, J. 2006. Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Opt. 17, 1, 188--217.

Digital Library

[12]

Audet, C. and Dennis, J. 2009. A progressive barrier for derivative-free nonlinear programming. SIAM J. Opt. 20, 4, 445--472.

Digital Library

[13]

Audet, C. and Le Digabel, S. 2009. The mesh adaptive direct search algorithm for periodic variables. Tech. rep. G-2009-23. Les cahiers du GERAD. (To appear in Pacific Journal Optimization).

[14]

Audet, C., Alarie, S., Le Digabel, S., Lequy, Q., Sylla, M., and Marcotte, O. 2008a. Localisation de stations de mesure automatisée du couvert nival. Tech. rep. CRM-3277. Centre de Recherches Mathématiques, Montréal, P.Q., Canada.

[15]

Audet, C., Béchard, V., and Le Digabel, S. 2008b. Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search. J. Glob. Opt. 41, 2, 299--318.

Digital Library

[16]

Audet, C., Custódio, A., and Dennis, J. 2008c. Erratum: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Opt. 18, 4, 1501--1503.

Digital Library

[17]

Audet, C., Dennis, J., and Le Digabel, S. 2008d. Parallel space decomposition of the mesh adaptive direct search algorithm. SIAM J. Opt. 19, 3, 1150--1170.

Digital Library

[18]

Audet, C., Savard, G., and Zghal, W. 2008e. Multiobjective optimization through a series of single-objective formulations. SIAM J. Opt. 19, 1, 188--210.

Digital Library

[19]

Audet, C., Dang, C.-K., and Orban, D. 2010a. Algorithmic parameter optimization of the DFO method with the OPAL framework. In Software Automatic Tuning: From Concepts to State-of-the-Art Results. K. Naono, K. Teranishi, J. Cavazos, and R. Suda Eds., Springer, Berlin, Germany, Chapter 15, 255--274.

[20]

Audet, C., Dennis, J., and Le Digabel, S. 2010b. Globalization strategies for mesh adaptive direct search. Comp. Opt. Appl. 46, 2, 193--215.

[21]

Audet, C., Fournier, X., Hansen, P., and Messine, F. 2010c. A note on diameters of point sets. Opt. Lett. 4, 4, 585--595.

[22]

Audet, C., Savard, G., and Zghal, W. 2010d. A mesh adaptive direct search algorithm for multiobjective optimization. Eur. J. Oper. Res. 204, 3, 545--556.

[23]

Booker, A., Dennis, J., Frank, P., Serafini, D., Torczon, V., and Trosset, M. 1999. A rigorous framework for optimization of expensive functions by surrogates. Struct. Opt. 17, 1, 1--13.

[24]

Brooke, A., Kendrick, D., and Meeraus, A. 1988. GAMS: A Users’ Guide. The Scientific Press, Danvers, MA.

[25]

Choi, T. and Kelley, C. 2000. Superlinear convergence and implicit filtering. SIAM J. Opt. 10, 4, 1149--1162.

Digital Library

[26]

Clarke, F. 1983. Optimization and Nonsmooth Analysis. Wiley, New York, NY. Reissued in 1990 by SIAM Publications, Philadelphia, PA, as Vol. 5 in the series Classics in Applied Mathematics.

[27]

Conn, A., Scheinberg, K., and Vicente, L. 2009. Introduction to Derivative-Free Optimization. MPS/SIAM Book Series on Optimization. SIAM, Philadelphia, PA.

Digital Library

[28]

Custódio, A., Dennis, J., and Vicente, L. 2008. Using simplex gradients of nonsmooth functions in direct search methods. IMA J. Numer. Anal. 28, 4, 770--784.

[29]

Custódio, A., Madeira, J., Vaz, A., and Vicente, L. 2010. Direct multisearch for multiobjective optimization. Tech. rep. Preprint 10-18. Department of Mathematics, University of Coimbra, Coimbra, Portugal. http://www.mat.uc.pt/~lnv/papers/dms.pdf.

[30]

Custódio, A. and Vicente, L. 2007. Using sampling and simplex derivatives in pattern search methods. SIAM J. Opt. 18, 2, 537--555.

Digital Library

[31]

Davidon, W. 1991. Variable metric method for minimization. SIAM J. Opt. 1, 1, 1--17.

[32]

Fourer, R., Gay, D., and Kernighan, B. 2003. AMPL: A Modeling Language for Mathematical Programming 2nd ed. Thomson/Brooks/Cole, Pacific Grove, CA.

[33]

Fowler, K., Reese, J., Kees, C., Dennis, J., Kelley, C., Miller, C., Audet, C., Booker, A., Couture, G., Darwin, R., Farthing, M., Finkel, D., Gablonsky, J., Gray, G., and Kolda, T. 2008. Comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems. Adv. Water Resourc. 31, 5, 743--757.

[34]

Gould, N., Orban, D., and Toint, P. 2003. CUTEr (and SifDec): A constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29, 4, 373--394.

Digital Library

[35]

Gray, G. and Kolda, T. 2006. Algorithm 856: APPSPACK 4.0: Asynchronous parallel pattern search for derivative-free optimization. ACM Trans. Math. Softw. 32, 3, 485--507.

Digital Library

[36]

Hedar, A. and Fukushima, M. 2006. Derivative-free filter simulated annealing method for constrained continuous global optimization. J. Glob. Opt. 35, 4, 521--549.

Digital Library

[37]

Kokkolaras, M., Audet, C., and Dennis, J. 2001. Mixed variable optimization of the number and composition of heat intercepts in a thermal insulation system. Opt. Eng. 2, 1, 5--29.

[38]

Le Digabel, S. 2009. NOMAD user guide. Tech. rep. G-2009-37. Les cahiers du GERAD.

[39]

Le Digabel, S., Abramson, M., Audet, C., and Dennis, J. 2010. Parallel versions of the MADS algorithm for black-box optimization. In Optimization Days, GERAD, Montreal. P.Q., Canada. www.gerad.ca/Sebastien.Le.Digabel/talks/2010_JOPT_25mins.pdf.

[40]

MathWorks, I. 2005. MATLAB GADS toolbox. http://www.mathworks.com/products/gads/.

[41]

Mittelmann, H. 2007. Decision tree for optimization software. http://plato.asu.edu/guide.html.

[42]

Mladenović, N. and Hansen, P. 1997. Variable neighborhood search. Comp. Oper. Res. 24, 11, 1097--1100.

Digital Library

[43]

Rios, L. and Sahinidis, N. 2010. Derivative-free optimization: A review of algorithms and comparison of software implementations. Tech. rep. Carnegie Mellon University, Pittsburg, PA. http://thales.cheme.cmu.edu/dfo.

[44]

Snir, M., Otto, S., Huss-Lederman, S., Walker, D. W., and Dongarra, J. 1995. MPI: The Complete Reference. MIT Press, Cambridge, MA.

Digital Library

[45]

Tang, B. 1993. Orthogonal array-based Latin hypercubes. J. Amer. Stat. Assoc. 88, 424, 1392--1397.

[46]

Torczon, V. 1997. On the convergence of pattern search algorithms. SIAM J. Opt. 7, 1, 1--25.

Digital Library

[47]

van Heesch, D. 1997. Doxygen manual. http://www.doxygen.org/manual.html.

[48]

Vicente, L. and Custódio, A. 2010. Analysis of direct searches for discontinuous functions. Tech. rep. Department of Mathematics, University of Coimbra, Coimbra, Portugal. To appear in Mathematical Programming.

Cited By

Mehrgan KThomas JSaglia RParikh TNeureiter BErwin PBender R(2024)Dynamical Stellar Mass-to-light Ratio Gradients: Evidence for Very Centrally Concentrated IMF Variations in ETGs?The Astrophysical Journal10.3847/1538-4357/acfe09961:1(127)Online publication date: 18-Jan-2024
https://doi.org/10.3847/1538-4357/acfe09
Hibberd AMarshall Eubanks T(2024)Initial Analysis of Near-Term Spacecraft Missions to Comet C/2014 UN271Journal of Spacecraft and Rockets10.2514/1.A35880(1-7)Online publication date: 25-Jun-2024
https://doi.org/10.2514/1.A35880
Esposito MMancini TTronci E(2024)Optimizing Fault-Tolerant Quality-Guaranteed Sensor Deployments for UAV Localization in Critical Areas via Computational GeometryIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2023.332743254:3(1515-1526)Online publication date: Mar-2024
https://doi.org/10.1109/TSMC.2023.3327432
Show More Cited By

Index Terms

Algorithm 909: NOMAD: Nonlinear Optimization with the MADS Algorithm
1. Applied computing
  1. Physical sciences and engineering

Recommendations

Algorithm 1027: NOMAD Version 4: Nonlinear Optimization with the MADS Algorithm
NOMADis a state-of-the-art software package for optimizing blackbox problems. In continuous development since 2001, it constantly evolved with the integration of new algorithmic features published in scientific publications. These features are motivated ...
Mesh-based Nelder---Mead algorithm for inequality constrained optimization

Despite the lack of theoretical and practical convergence support, the Nelder---Mead (NM) algorithm is widely used to solve unconstrained optimization problems. It is a derivative-free algorithm, that attempts iteratively to replace the worst point of a ...
An upgraded artificial bee colony (ABC) algorithm for constrained optimization problems

Artificial bee colony (ABC) algorithm developed by Karaboga is a nature inspired metaheuristic based on honey bee foraging behavior. It was successfully applied to continuous unconstrained optimization problems and later it was extended to constrained ...

Comments

Information & Contributors

Information

Published In

ACM Transactions on Mathematical Software Volume 37, Issue 4

February 2011

212 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1916461

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 2011

Accepted: 01 August 2010

Revised: 01 June 2010

Received: 01 July 2009

Published in TOMS Volume 37, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

479
Total Citations
View Citations
2,108
Total Downloads

Downloads (Last 12 months)106
Downloads (Last 6 weeks)5

Reflects downloads up to 18 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mehrgan KThomas JSaglia RParikh TNeureiter BErwin PBender R(2024)Dynamical Stellar Mass-to-light Ratio Gradients: Evidence for Very Centrally Concentrated IMF Variations in ETGs?The Astrophysical Journal10.3847/1538-4357/acfe09961:1(127)Online publication date: 18-Jan-2024
https://doi.org/10.3847/1538-4357/acfe09
Hibberd AMarshall Eubanks T(2024)Initial Analysis of Near-Term Spacecraft Missions to Comet C/2014 UN271Journal of Spacecraft and Rockets10.2514/1.A35880(1-7)Online publication date: 25-Jun-2024
https://doi.org/10.2514/1.A35880
Esposito MMancini TTronci E(2024)Optimizing Fault-Tolerant Quality-Guaranteed Sensor Deployments for UAV Localization in Critical Areas via Computational GeometryIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2023.332743254:3(1515-1526)Online publication date: Mar-2024
https://doi.org/10.1109/TSMC.2023.3327432
Youssef ELabeau FKassouf M(2024)Adversarial Dynamic Load-Altering Cyberattacks Against Peak Shaving Using Residential Electric Water HeatersIEEE Transactions on Smart Grid10.1109/TSG.2023.330023915:2(2073-2088)Online publication date: Mar-2024
https://doi.org/10.1109/TSG.2023.3300239
Shen MDollar RMolnar THe CVahidi AOrosz G(2024)Energy-Efficient Reactive and Predictive Connected Cruise ControlIEEE Transactions on Intelligent Vehicles10.1109/TIV.2023.32817639:1(944-957)Online publication date: Jan-2024
https://doi.org/10.1109/TIV.2023.3281763
de Nicola SThomas JSaglia RSnigula JKluge MBender R(2024)Triaxial Schwarzschild models of NGC 708: a 10-billion solar mass black hole in a low-dispersion galaxy with a Kroupa IMFMonthly Notices of the Royal Astronomical Society10.1093/mnras/stae806530:1(1035-1053)Online publication date: 19-Mar-2024
https://doi.org/10.1093/mnras/stae806
Arrieta-Prieto MSchell K(2024)Data-driven optimization for wind farm sitingInternational Journal of Electrical Power & Energy Systems10.1016/j.ijepes.2023.109552155(109552)Online publication date: Jan-2024
https://doi.org/10.1016/j.ijepes.2023.109552
Nikkhah ANikkhah HShahbazi AZarin MBeykal Iz DEbadi MFakhroleslam MBeykal B(2024)Cumin and eucalyptus essential oil standardization using fractional distillation: Data-driven optimization and techno-economic analysisFood and Bioproducts Processing10.1016/j.fbp.2023.10.005143(90-101)Online publication date: Jan-2024
https://doi.org/10.1016/j.fbp.2023.10.005
Ramzan MNaeem MChughtai OEjaz WAltaf M(2024)Radio resource management in energy harvesting cooperative cognitive UAV assisted IoT networks: A multi-objective approachDigital Communications and Networks10.1016/j.dcan.2023.01.00610:4(1088-1102)Online publication date: Aug-2024
https://doi.org/10.1016/j.dcan.2023.01.006
Srinivas SKarimi I(2024)Zonewise surrogate-based optimization of box-constrained systemsComputers & Chemical Engineering10.1016/j.compchemeng.2024.108821189(108821)Online publication date: Oct-2024
https://doi.org/10.1016/j.compchemeng.2024.108821
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents