MANGO provides interfaces to a wide variety of optimization algorithms, including both local and global algorithms, and derivative-free and derivative-based algorithms, for both general and least-squares minimization. (For derivative-based algorithms, MANGO uses finite difference derivatives.) Most of the algorithms are provided via interfaces to outside software packages (GSL, PETSc, NLOPT, and HOPSPACK). MANGO can also provide its own optimization algorithms. Presently there is one such native algorithm, mango_levenberg_marquardt.
The available algorithms are
mango_levenberg_marquardt,
mango_imfil,
petsc_nm,
petsc_pounders,
petsc_brgn,
nlopt_gn_direct,
nlopt_gn_direct_l,
nlopt_gn_direct_l_rand,
nlopt_gn_direct_noscal,
nlopt_gn_direct_l_noscal,
nlopt_gn_direct_l_rand_noscal,
nlopt_gn_orig_direct,
nlopt_gn_orig_direct_l,
nlopt_gn_crs2_lm,
nlopt_ln_cobyla,
nlopt_ln_bobyqa,
nlopt_ln_praxis,
nlopt_ln_neldermead,
nlopt_ln_sbplx,
nlopt_ld_mma,
nlopt_ld_ccsaq,
nlopt_ld_slsqp,
nlopt_ld_lbfgs,
nlopt_ld_tnewton_precond_restart,
nlopt_ld_tnewton_precond,
nlopt_ld_tnewton_restart,
nlopt_ld_tnewton,
nlopt_ld_var1,
nlopt_ld_var2,
hopspack,
gsl_lm,
gsl_dogleg,
gsl_ddogleg,
gsl_subspace2d,
gsl_conjugate_fr,
gsl_conjugate_pr,
gsl_bfgs,
gsl_nm
This same list is enumerated in mango::algorithm_type. You can also find the algorithm list in the table here, which also shows properties of each algorithm such as whether bound constraints are supported or required, whether (finite-difference) derivatives are used, etc.
Each algorithm can be identified either by an integer index or by a string, identical to the name of the integer index but lowercase. For instance, PETSc's POUNDERS algorithm can be identified either with the integer constant mango::PETSC_POUNDERS or by the string "petsc_pounders". The string always begins with the name of the software package in which the algorithm is implemented: gsl, nlopt, petsc, hopspack, or mango for the case of algorithms implemented directly in MANGO. For packages that support multiple algorithms (all packages except HOPSPACK), the algorithm name then contains an underscore, followed by the name of the specific algorithm.
There are three ways to select an algorithm: from within your driver code by specifying the enumerated constant or string, or by loading in the string from a file. From C++, the first two approaches are provided by mango::Problem::set_algorithm(), while the file-based approach is provided by mango::Problem::read_input_file(). For instance after creating a problem instance
we could call
or
or
In the last case, the input file should consist of 2 lines. The first line is an integer giving the number of worker groups, while the second line contains the string representation of the algorithm name (e.g. nlopt_ln_neldermead).
When calling MANGO from fortran, after creating an optimization problem object with
the corresponding subroutine calls to select the algorithm are
or
or
We now discuss the algorithms provided by each package.
The Gnu Scientific Library contains several serial (non-parallelized) algorithms for general and least-squares optimization. GSL is usually available on HPC systems. It can also be installed on personal computers using package manager systems like macports or apt-get. To use GSL algorithms, MANGO must be built with MANGO_GSL_AVAILABLE=T set in the makefile.
For general optimization problem, MANGO provides four GSL algorithms, which are discussed in detail here in the GSL manual. The option gsl_nm is the Nelder-Mead simplex algorithm, specifically the gsl_multimin_fminimizer_nmsimplex2 version discussed in the GSL manual. The option gsl_bfgs is the version of BFGS called gsl_multimin_fdfminimizer_vector_bfgs2 in the GSL manual. The options gsl_conjugate_fr and gsl_conjugate_pr give the Fletcher-Reeves and Polak-Ribiere conjugate gradient algorithms respectively. The steepest-descent algorithm discussed in the GSL manual is not supported in MANGO. Note that none of these GSL algorithms support bound constraints.
For least-squares problems, MANGO provides four GSL algorithms, which are discussed in detail here in the GSL manual: gsl_lm (Levenberg-Marquardt), gsl_dogleg (Powell's dogleg method), gsl_ddogleg (double dogleg), and gsl_subspace2d (two-dimensional subspace). Note that none of these GSL least-squares algorithms support bound constraints, and all require N_terms >= N_parameters. The "Levenberg-Marquardt with Geodesic Acceleration" and "Steihaug-Toint Conjugate Gradient" algorithms, discussed in the GSL manual, are not presently supported in MANGO.
NLOpt is a library with many serial algorithms for general optimization. It has no algorithms specific to least-squares problems. NLOpt is not commonly found on HPC systems. It can be downloaded and built by changing to the mango/external_packages directory and running
> install_nlopt
To use NLOpt algorithms, MANGO must be built with MANGO_NLOPT_AVAILABLE=T set in the makefile.
So many algorithms are available in NLOpt that they will not be listed here; consult mango::algorithm_type or algorithms.dat for the complete list. A detailed explanation of each algorithm can be found here in the NLOpt manual.
The MANGO name for each NLOpt algorithm is identical to the corresponding name in NLOpt; e.g. the algorithm named NLOPT_LN_NELDERMEAD in NLOpt is called mango::NLOPT_LN_NELDERMEAD and nlopt_ln_neldermead in MANGO. Each NLOpt algorithm name begins with nlopt_ followed by gn_, ln_, or ld_. The letter g vs l indicates a global vs local algorithm. The letter n vs d indicates a derivative-free vs derivative-based algorithm respectively. So, for instance, nlopt_gn_direct is a global derivative-free algorithm, nlopt_ln_praxis is a local derivative-free algorithm, and nlopt_ld_lbfgs is a local derivative-based algorithm. All of the global algorithms require that bound constraints be set.
PETSc is a large library for scientific computing, and it includes the optimization library TAO. PETSc is usually available on HPC systems. It can also be installed on personal computers using package manager systems like macports, or following the instructions here. To use PETSc/TAO algorithms, MANGO must be built with MANGO_PETSC_AVAILABLE=T set in the makefile.
MANGO presently supports three optimization algorithms from TAO. petsc_nm is the Nelder-Mead simplex algorithm for local derivative-free general optimization problems. petsc_pounders is the POUNDERS algorithm for least-squares derivative-free minimization. petsc_brgn is the "Bound-constrained regularized Gauss-Newton" algorithm for least-squares derivative-based minimization. Note that petsc_brgn is available only for PETSc versions 3.11 and higher. For more details of the algorithms, see the TAO manual here and the TAO API reference.
The least-squares algorithms petsc_pounders and petsc_brgn are the only least-squares algorithms in MANGO that support bound constraints. These two algorithms do not require N_terms >= N_parameters, in contrast to the GSL least-squares algorithms.
HOPSPACK is a library for parallelized derivative-free general optimization. HOPSPACK is not commonly available on HPC systems. It can be downloaded by changing to the mango/external_packages directory and running
> install_hopspack
This command will not actually build the library; rather it is compiled at the same time as MANGO, since MANGO needs to modify several of the HOPSPACK source files. To use HOPSPACK, MANGO must be built with MANGO_HOPSPACK_AVAILABLE=T set in the makefile.
The HOPSPACK package contains only a single algorithm, so there is no underscore in the integer or string name for this algorithm in MANGO (mango::HOPSPACK and "mango_hopspack" respectively). This algorithm is unique in that it supports concurrent (i.e. parallel) evaluations of the objective function even though it does not use finite-difference derivatives. HOPSPACK does not require bound constraints, but it performs best when accurate bound constraints are supplied.
Presently, MANGO provides just one of its own algorithms, with integer mango::MANGO_LEVENBERG_MARQUARDT and string name "mango_levenberg_marquardt". This is a derivative-based algorithm for local least-squares minimization. MANGO's implementation of the Levenberg-Marquardt algorithm has several advantages compared to gsl_lm. First, MANGO's version uses concurrent (i.e. parallel) evaluation of the residuals over several values of the parameter \( \lambda \), whereas gsl_lm uses a serial search in \( \lambda \), making gsl_lm quite load-imbalanced. Second, mango_levenberg_marquardt does not require N_terms >= N_parameters, unlike gsl_lm.
To use mango_levenberg_marquardt, you must have the Eigen library, which is available on many HPC systems. Eigen can also be downloaded by changing to the mango/external_packages directory and running
> install_eigen
This command will not do any compiling or linking, since Eigen is a header-only library. To use mango_levenberg_marquardt, MANGO must be built with MANGO_EIGEN_AVAILABLE=T set in the makefile.