NOMADm Optimization Software
NOMADm is a MATLAB® implementation of the class of Mesh-Adaptive Direct Search (MADS) algorithms for solving nonlinear and mixed variable optimization problems with general nonlinear constraints. MADS is a generalization of the class of Generalized Pattern Search (GPS) algorithms that evaluates points in a set of directions that becomes dense in the limit, thereby achieving superior convergence properties. The algorithms used by NOMADm are detailed in several papers listed below and others in-progress. NOMADm is the research version of the production C++ code,
NOMAD.
As a testament to its quality, The MathWorks folks have incorporated many of the ideas in this code into the direct search portion of their own
Genetic Algorithm and Direct Search (GADS) Toolbox
(see GADS Toolbox User's Guide, p. 3).
People Involved in the NOMAD/NOMADm Project
Some Relevant Papers
This is a list of papers that are relevant to the NOMADm software. Those that are algorithmic in nature either have something in them that has been incorporated into NOMADm, or else adds something significant to the theory of the class of GPS or MADS algorithms that are employed in NOMADm. The applications are typically those that used our software in their research. This list does not include the many papers dealing with ideas for surrogate optimization (e.g., radial basis functions, DACE, etc.), unless they are specifically applied in some way to GPS/MADS algorithms or the NOMADm software.
Mesh Adaptive Direct Search
- C. Audet and J. E. Dennis, Jr. (2006),
Mesh Adaptive Direct Search Algorithms for Constrained Optimization,
SIAM J. Optim. 17 (2), 188-217.
- M. A. Abramson and C. Audet (2006),
Convergence of Mesh Adaptive Direct Search to Second-Order Stationary Points,
SIAM J. Optim. 17 (2), 606-619.
- M. A. Abramson, C. Audet, and J. E. Dennis, Jr. (2006),
Nonlinear Programing with Mesh Adaptive Direct Searches,
SIAG/Optimization Views-and-News 17 (1), 2-11.
- C. Audet, G. Savard, and W. Zghal (2007),
A Mesh Adaptive Direct Search Algorithm for Biobjective Optimization,
SIAM J. Optim., to appear.
- M. A. Abramson, C. Audet, J. W. Chrissis, and J. G. Walston (2007),
Mesh Adaptive Direct Search Algorithms for Mixed Variable Optimization,
GERAD Technical Report #2007-47, submitted.
Generalized Pattern Search
- V. Torczon (1997),
On the Convergence of Pattern Search Algorithms,
SIAM J. Optim. 7 (1), 1-25.
- R. M. Lewis and V. Torczon (2000),
Pattern Search Methods for Linearly Constrained Minimization,
SIAM J. Optim. 10 (3), 917-941.
- T. G. Kolda, R. M. Lewis, and V. Torczon (2003),
Optimization by Direct Search:
New Perspectives on Some Classical and Modern Methods,
SIAM Rev. 45 (3), 385-482.
- T. G. Kolda, R. M. Lewis, V. Torczon (2007),
Implementing Generating Set Search Algorithms for Linearly Constrained Optimization,
SIAM J. Sci. Comput., to appear.
- C. Audet and J. E. Dennis, Jr. (1999),
Pattern Search Algorithms for Mixed Variable Programming,
SIAM J. Optim. 11 (3), 573-594.
- C. Audet and J. E. Dennis, Jr. (2003),
Analysis of Generalized Pattern Searches,
SIAM J. Optim. 13 (3), 889-903.
- C. Audet and J. E. Dennis, Jr. (2004),
A Pattern Search Filter Method for Nonlinear Programming without Derivatives,
SIAM J. Optim. 14 (4), 980-1010.
- M. A. Abramson, C. Audet, and J. E. Dennis, Jr. (2002),
Generalized Pattern Searches with Derivative Information,
Math. Program. 100 (1), 3-25.
- M. A. Abramson (2002),
Pattern Search Filter Algorithms for Mixed Variable General Constrained Optimization Problems,
Ph.D. thesis, Rice University.
- M. A. Abramson (2004),
Second-Order Behavior of Pattern Search,
SIAM J. Optim. 16 (2), 515-530.
- T. A. Sriver, J. W. Chrissis, and M. A. Abramson (2004),
Pattern Search Ranking and Selection Algorithms for Mixed Variable Simulation-Based Optimization,
submitted.
- M. A. Abramson, O. A. Brezhneva, J. E. Dennis, Jr., and R. L. Pingel (2007),
Pattern Search in the Presence of Degenerate Linear Constraints, Optim. Meth. Softw., to appear.
- M. A. Abramson, C. Audet, and J. E. Dennis, Jr. (2007),
Filter Pattern Search Methods for Mixed Variable Constrained Optimization Problems,
Pacific J. Optim. 3 (3), 477-500.
- A. L. Custodio and L. N. Vicente (2007),
Using Sampling and Simplex Derivatives in Pattern Search Methods,
SIAM J. Optim. 18 (2), 537–555.
- A. Ismael F. Vaz and L. N. Vicente (2007),
A Particle Swarm Pattern Search Method for Bound Constrained Nonlinear Optimization,
J. Global Optim., to appear.
Surrogates
- A. J. Booker, J. E. Dennis, Jr., P. D. Frank, D. B. Serafini, V. Torczon, and M. W. Trosset (1999),
A Rigorous Framework for Optimization of Expensive Functions by Surrogates,
Struct. Optim. 17 (1), 1-13.
- T. A. Sriver and J. W. Chrissis (2004),
A Framework for Mixed-Variable Optimization Under
Uncertainty Using Surrogates and Statistical Selection, 10th AIAA/ISSMO Multidisciplinary
Analysis and Optimization Conference, August 30 - September 1, 2004, Albany, NY
- J. E. Dunlap (2005),
On the Use of Surrogate Functions for Mixed Variable Optimization of Stochastic Systems,
MS thesis, AFIT
- R. Magallanez (2007),
Surrogate Strategies for Computationally Expensive Optimization Problems with CPU Time-Correlated Functions,
MS thesis, AFIT.
Applications
- M. Kokkolaras, C. Audet, and J. E. Dennis, Jr. (2000),
Mixed Variable Optimization of the Number and Composition
of Heat Intercepts in a Thermal Insulation System,
Optim. Eng. 2 (1), 5-29.
- M. A. Abramson (2002),
Mixed Variable Optimization of a Load-Bearing Thermal Insulation System
Using a Filter Pattern Search Algorithm,
Optim. Eng. 5 (2), 157-177.
- A. L. Marsden, M. Wang, J. E. Dennis, Jr., and P. Moin (2004),
Optimal Aeroacoustic Shape Design Using the Surrogate Management Framework,
Optim. Eng. 5 (2), 235-262.
- A. L. Marsden, M. Wang, J. E. Dennis, Jr., and P. Moin (2004),
Suppression of Vortex-Shedding Noise via Derivative-Free Shape Optimization,
Physics of Fluids 16 (10), L83-L86.
- K. R. O'Reilly (2006),
Quantitative Object Reconstruction using Abel-based Tomography and Mixed Variable Optimization,
MS thesis, AFIT.
- J. M. Beal, A. Shukla, O. A. Brezhneva, and M. A. Abramson (2007),
Optimal sensor placement for enhancing sensitivity to change in stiffness
for structural health monitoring, Optim. Eng., to appear.
- J. Han, M. Kokklaras,and P. Y. Papalambros (2006),
Optimal Design of Hybrid Fuel Cell Vehicles,
Accepted, Proc. 4th Int. ASME Conf. Fuel Cell Sci. Engin. Tech., #FUELCELL-2006-97161, June 19-21, 2006, Irvine, CA
- M. Kokklaras, Z. P. Mourelatos, and P. Y. Papalambros (2006),
Impact of Uncertainty Quantification on Design Decisions for a Hydraulic-Hybrid Powertrain Engine,
AIAA #2006-2001, 47th AIAA/ASME/ASCE/AHS/ASC Struct., Structural Dynamics, and Materials Conf.,
May 1-4, 2006, Newport, RI
- J. Allison, B. Roth, M. Kokkolaras, I. Kroo, and P. Y. Papalambros (2006),
Aircraft Family Design Using Decomposition-based Methods,
Proceedings of the 11th AIAA/ISSMO Multidisciplinary Analysis and
Optimization Conference, September 6-8, 2006, Portsmouth, Virginia.
- Z. Zhao, J.C. Meza, and M. Van Hove (2006),
Using Pattern Search Methods for Surface Structure Determination of Nanomaterials,
J. Phys.: Condens. Matter 18, 8693–8706
- R. L. Pingel, M. A. Abramson, T. J. Asaki, J. E. Dennis, Jr. (2006),
Characteristic Shape Sequences for Measures on Images, Rice CAAM Technical Report TR06-17.
- M. A. Abramson, T. J. Asaki, J. E. Dennis, Jr., K. R. O'Reilly, and R. L. Pingel (2007),
Quantitative Object Reconstruction via Abel Transform X-Ray Tomography
and Mixed Variable Optimization, Rice CAAM Technical Report TR07-03.
NOMADm v4.6 Software Download
Download NOMADm v4.6
Download some example problem files
Download Heat Shield problem files
NOMADm should work on any platform that uses MATLAB. The MATLAB Optimization Toolbox
is recommended, but not necessary to run the software. If it is not present, then a few of
the more obscure functions will not work. Changes to past versions are as follows
(a complete list is included in the accompanying documentation):
- (v4.6) Added a default discrete neighbors file for MVP problems.
- (v4.6) Revised implementation of MADS termination criteria.
- (v4.6) Particle swarm in the presence of mixed variables (categorical variables held constant).
- (v4.6) Fully integrated new (highly modified) self-contained version of CMA-ES.
- (v4.5) New option for specifying the frequency of recalibrating surrogates.
- (v4.5) Search options to apply Radial Basis Functions (RBF) as surrogates.
- (v4.5) Central Composite Design (CCD) for the initial Search step.
- (v4.5) Particle Swarm (PS) optimization as either a Search step or as a surrogate optimizer.
- (v4.5) New Search parameters for evaluating all or only some trial points generated by the Search step.
- (v4.5) Improved debugging capability.
- (v4.1) Rewrote the Latin Hypercube Search code to simplify it and ignore previously evaluated points.
- (v4.0) Complete revamping of surrogates for mixed variable problems.
- (v4.0) Rewrote the MADS direction-generating function to coincide with a revision of the paper.
- (v4.0) New termination criteria for the ranking & selection methods used for stochastic problems.
- (v4.0) New debugging option that prints run data to screen.
- (v4.0) New Complete Polling options for discrete neighbor and extended polling for MVP problems.
- (v4.0) New scheme for fully enumerating tangent cone generators when the problem is degenerate.
- (v3.8) Options to apply DACE, Nadaraya-Watson, or Custom simplified physics surrogates.
- (v3.7) A submenu for treating the problem as a sensor placement problem.
- (v3.6) Modified custom search and surrogate code to facilitate use of simplified physics surrogates
- (v3.5) An option for ordering poll directions according to their angle with the negative of the simplex gradient
- (v3.4) A feature allowing the user a Closed Constraints file for adding yes/no constraints for use with MADS
- (v3.4) An option to save the performance history to text file for future post-processing
- (v3.4) Schemes for generating partially conforming directions when active nonredundant constraints are linearly dependent
- (v3.3) Incorporation of a ranking and selection scheme for solving stochastic optimization problems
- (v3.2) Implementation of surrogates for MVP problems
- (v3.2) Implementation of an optional EXTENDED SEARCH step for MVP problems
- (v3.2) A new Search option for optimizing a Nadaraya-Watson surrogate
- (v3.2) Deletion of path restrictions for the DACE and CMA-ES software packages
- (v3.2) Big improvements to the user interface, including enhanced SEARCH input screen,
new Solution screen, color-coded Results menu to match plots, and completely
overhauled user interface structure
- (v3.0) Implementation of the new MADS algorithm
- (v3.0) Implementation of DACE surrogates for use in the SEARCH step of the algorithm
- (v3.0) A new SEARCH screen that offers much more flexibility in setting up the SEARCH step
- (v3.0) New choices for poll ordering
- (v3.0) A revised restart capability, where the user can start and stop the code at any time,
change parameters, and resume the run
- (v3.0) A utility for compiling functions files written in C (in addition to the FORTRAN
capability that was already part of previous versions)
- (v3.0) Extensive recoding for efficiency and compatibility with normal MATLAB coding and
documentation conventions
NOTE: Since this code is now over 9000 lines of MATLAB code, there are bound to be bugs in it, in spite of my efforts to thoroughly test all the options. PLEASE e-mail me with any bugs that you encounter, and also with any suggestions that you have for improving the code, as I want to make the code as cool and bug-free as possible.
Companion Software Download
NOMADm optionally incorporates three additional MATLAB packages for constructing and optimizing surrogates: DACE (a suite of DACE algorithms using kriging), NW (a set of functions that apply the Nadaraya-Watson estimator), and RBF (a set of functions that apply radial basis functions). (Note: The CMA-ES evolutionary strategy code is no longer kept separate from this code. Instead, a highly modified version of Nikolaus Hansen's code has been incorporated directly into the NOMADm files. Special thanks to Niko for an exceptional piece of software.) To use one of these packages within NOMADm, after installation, the path where the files are located must be added to the MATLAB path via the "File --> Set Path" menu choice from the main MATLAB figure window. If done correctly, relaunching NOMADm will result in the appropriate help file appearing in the NOMADm Help Menu. These packages can be downloaded separately by clicking on the following links:
Download DACE Toolbox
Download NW Toolbox
Download RBF Toolbox
Acknowledgements
I owe a special debt of gratitude to my former advisors, John Dennis and Charles Audet, whose assistance in this project has been invaluable. I would also like to thank Keith Berrier, Olga Brezhneva, Ana Custodio, Gilles Couture, Thierry Dalon, John Dunlap, Arantzazu Garcia-Lekue, Alison Marsden, Rachael Pingel, Jacob Sondergaard, and Luis Vicente for numerous suggestions for correcting and improving the code. Also, thanks to Rakesh Kumar at MathWorks, Inc. for helpful discussions, and thanks to several other users, who have identified bugs and patiently waited for the fix.
Last modifed September 12, 2007. You can e-mail me by inserting my name
as specified into the address: FirstName.LastName@afit.edu