# Optimization Resources A collection of software and resources for nonlinear optimization.

Maintained by Coralia Cartis (University of Oxford), Jaroslav Fowkes (STFC Rutherford Appleton Laboratory) and Lindon Roberts (Australian National University).
There are many software packages for solving optimization problems. Here we provide a list of some available solvers that we have developed and a number of other packages that are available for solving a broad variety of problems in several programming languages. On this page we focus on nonlinear optimization (not other important categories such as linear programming or integer programming problems).

#### Nonlinear Optimization Problems

These problems take the form $$\min_{x\in\mathbb{R}^n} f(x),$$ where $f$ is an 'objective' function (implemented as a piece of code) which takes the length-$n$ array $x$ of continuous variables and computes some quantity of interest depending on $x$. If the problem is to maximize $f$, then you can instead minimize $(-1)\times f(x)$ to put it in the form required by most solvers.
##### Constraints
It is often the case that the variables $x$ can only take some values, and we call such problems constrained: $$\min_{x\in\Omega} f(x),$$ where $\Omega$ is some region of $n$-dimensional space defining the valid choices of $x$. This 'feasible region' is usually represented by a collection of constraint functions of the form $c(x)\geq 0$ or $c(x)=0$. Some simple constraints are sometimes considered explicitly, such as box constraints $a_i \leq x_i \leq b_i$ (i.e. the $i$-th entry of $x$ must be between $a_i$ and $b_i$). In general it is better to represent constraints in the simplest possible way (e.g. don't use $e^x \leq 1$ when you could use $x\leq 0$ instead).

#### Data Fitting/Inverse Problems

One very common special type of optimization problem is nonlinear least-squares problems, which are very common in data fitting and inverse problems. In this case, the objective function has the special form $$f(x) = \sum_{i=1}^{m} r_i(x)^2,$$ where each function $r_i(x)$ usually represents a fitting error corresponding to the $i$-th data point (out of $m$ total data points).

#### Problem Information to Supply

What information you have access to can determine what type of solver you should use. In general, most solvers will require you to provide a piece of code which computes $f(x)$ for any $x$ (and $c(x)$ for any constraints). Usually you will also need to be able to compute the gradient of the objective (and all constraints), that is provide code which returns the $n$-dimensional vector $\nabla f(x)$ for any $x$ (where the $i$-th entry of $\nabla f(x)$ is the derivative of $f$ with respect to the $i$-th entry of $x$). You can implement a gradient calculation by explicitly calculating the derivatives (if you know the explicit mathematical form of $f$), or use finite differencing techniques or algorithmic differentiation software packages.

For nonlinear least-squares problems and problems with multiple constraints, often you will need to write code to return a vector of results (e.g. given $x$, return the length-$m$ vector $r(x)=[r_1(x) \: \cdots \: r_m(x)]$ for nonlinear least-squares problems). In this case, instead of the gradient $\nabla f(x)$ you will need to provide the Jacobian matrix of first derivatives. For instance, if you have a function $r(x)=[r_1(x) \: \cdots \: r_m(x)]$ where $x$ has $n$ entries, the Jacobian matrix has $m$ rows and $n$ columns and the $i$-th row is $\nabla r_i(x)$.

Some solvers also allow you to provide code to calculate the second derivatives of $f$ (the Hessian of $f$), but this is usually not necessary. In general the more information you can provide, the better the optimization solver will perform, so it is sometimes worth the effort of writing Hessian code.

If you are writing code which returns very large matrices (e.g. Jacobians or Hessians), it is often useful to think about the sparsity of these matrices: which entries are always zero for every $x$? Many solvers allow you to provide Jacobians or Hessians as sparse matrices, which can give substantial savings on memory and computation time.

If your calculation of $f$ has some randomness (e.g. it requires a Monte Carlo simulation) or is very computationally expensive, then evaluating $\nabla f(x)$ may be very expensive or inaccurate. In this case, you may want to consider derivative-free solvers, which only require code to evaluate $f$.

• DFO-LS (open source, Python) - a derivative-free nonlinear least-squares solver (i.e. no first derivatives of the objective are required or estimated), with optional bound constraints. This solver is suitable when objective evaluations are expensive and/or have stochastic noise, and has many input parameters which allow it adapt to these problem types. It is based on our previous solver DFO-GN.
• oBB (open source, Python) - a parallelized solver for global optimization problems with general constraints. It requires first derivatives of the objective and bounds on its second derivatives. It is part of the COIN-OR collection (see below).
• P-IPM-LP (open source, MATLAB) - a perturbed Interior Point Method for linear programming problems (i.e. minimize a linear function subject to linear constraints).
• Py-BOBYQA (open source, Python) - a derivative-free general objective solver, with optional bound constraints. The algorithm is based on Mike Powell's original BOBYQA (Fortran), but includes a number of the features from DFO-LS, which improve its performance for noisy problems.
• trustregion (open source, Python) - a wrapper to Fortran routines for solving the trust-region subproblem. This subproblem is an important component of some optimization solvers.

These are some software packages which we have had some involvement with, directly or indirectly.

• COIN-OR (open source, many languages) - an organization which maintains a collection of many open-source optimization packages for a wide variety of problems. A list of packages by problem type is here and the source code is on Github.
• FitBenchmarking (open source, Python) - a tool for comparing different optimization software for data fitting problems. The documentation is here and the source code is on Github.
• GALAHAD (open source, Fortran with C, MATLAB, Python and Julia interfaces) - a collection of routines for constrained and unconstrainted nonlinear optimization, including useful subroutines such as trust-region and cubic regularization subproblem solvers. The source code is on Github.
• NAG Library (proprietary, many languages) - a large collection of mathematical software, inluding optimization routines for many problem types (nonlinear, LPs, QPs, global, mixed integer, etc.). Note: some of our research has been partially supported by NAG.

Software packages:

• Ipopt (open source, C++ with interfaces to many languages including Python, MATLAB, C and Julia) - a package for solving inequality-constrained nonlinear optimization problems.
• Julia Smooth Optimizers and JuliaOpt (open source, Julia) - a collection of packages for optimization, including solvers, profiling tools (such as creating performance profiles) and a CUTEst interface.
• KNitro (proprietary, free trial available, MATLAB) - a high quality solver for general constrained and unconstrained nonlinear optimization problems.
• NLOpt (open source, many languages including Python, MATLAB, Fortran and C) - a library which wraps many different nonlinear optimization solvers in a unified interface. Solvers include SQP, augmented Lagrangian and L-BFGS (local), DIRECT (global) and BOBYQA (local, derivative-free).
• RALFit (open source, Fortran with interfaces to C and Python) - a package for solving nonlinear least-squares problems (such as some data fitting and inverse problems).

Other resources:

• arXiv:math.OC - a repository of optimization-related preprints.
• Decision Tree for Optimization Software - an extensive database of software for many different types of optimization problem, carefully sorted by problem type.
• Global Optimization test problems - a collection of resources maintained by Arnold Neumaier (University of Vienna).
• NEOS server - an online server where you can submit jobs to be solved by specific solvers.
• NEOS guide - a reference page with explanations of the different types of optimization problems and summaries of many key algorithms (sorted by problem type). It also has its own page of optimization resources, such as key journals and conferences.
• Optimization Online - a repository of optimization-related preprints.

This section gives details of how to install the extensive CUTEst library of optimization test problems (paper) - earlier versions were called CUTE (1995) and CUTEr (2003) - as well as providing some standard collections of optimization test problems. CUTEst is a Fortran library, but we give instructions for installing wrappers for Matlab and Python. The other problem sets are implemented in Python.

To use CUTEst on Linux you will need to install four packages: archdefs, SIFDecode, CUTEst and MASTSIF. To keep things simple, install all four packages in the same directory:

mkdir cutest
cd cutest
git clone https://github.com/ralna/ARCHDefs ./archdefs
git clone https://github.com/ralna/SIFDecode ./sifdecode
git clone https://github.com/ralna/CUTEst ./cutest
git clone https://bitbucket.org/optrove/sif ./mastsif

Note that mastsif contains all the test problem definitions and is therefore quite large. If you're short on space you may want to copy only the *.SIF files for the problems you wish to test on. Next set the following environment variables in your ~/.bashrc to point to the installation directories used above:

# CUTEst
export ARCHDEFS=/path/to/cutest/archdefs/
export SIFDECODE=/path/to/cutest/sifdecode/
export MASTSIF=/path/to/cutest/mastsif/
export CUTEST=/path/to/cutest/cutest/
export MYARCH="pc64.lnx.gfo"
export MYMATLAB=/path/to/matlab/ # if using Matlab interface

Now you are ready to compile CUTEst using the interactive install script:

source ~/.bashrc # load above environment variables
cd ./cutest
$ARCHDEFS/install_optrove Answer the questions as appropriate, in particular answer the following as shown: Do you wish to install CUTEst (Y/n)? y Do you require the CUTEst-Matlab interface (y/N)? y # if using Matlab interface (see below) Select platform: # PC with generic 64-bit processor Select operating system: # Linux Select Matlab version: # R2016b or later Would you like to compile SIFDecode ... (Y/n)? y Would you like to compile CUTEst ... (Y/n)? y CUTEst may be compiled in (S)ingle or (D)ouble precision or (B)oth. Which precision do you require for the installed subset (D/s/b) ? D #### Installing the Python Interface To obtain a Python interface to CUTEst, please install PyCUTEst: https://github.com/jfowkes/pycutest To use CUTEst on Mac you will first need to install the Homebrew package manager: /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

Then you can easily install CUTEst:

brew tap optimizers/cutest
brew install cutest --without-single --with-matlab # if using Matlab interface
brew install mastsif  # if you want all the test problems
for f in "archdefs" "mastsif" "sifdecode" "cutest"; do \
echo ". $(brew --prefix$f)/$f.zshrc" >> ~/.zshrc; \ done If you installed CUTEst with Matlab support, you also need to define an environment variable pointing to your local Matlab installation in your ~/.zshrc, e.g., export MYMATLAB=/Applications/MATLAB_R2023b.app #### Installing the Python Interface To obtain a Python interface to CUTEst, please install PyCUTEst: https://github.com/jfowkes/pycutest #### Installing the Matlab Interface on Apple Silicon Macs This is rather involved unfortunately. First ensure that you have installed the Apple Silicon version of Matlab (and not the Intel Mac version). Then download the shell script below and place it somewhere on your PATH. I like to create ~/bin and add it to my PATH. Make the script executable: mkdir ~/bin # if not already done cp Downloads/cutest2matlab_macos.sh ~/bin/ chmod +x ~/bin/cutest2matlab_macos.sh export PATH=~/bin:$PATH  # if not already done; add this to your ~/.zshrc

Now you have to compile the CUTEst problems you wish to use. For example, if you wish to use the ROSENBR problem (Rosenbrock function), create a folder for it and run cutest2matlab_macos.sh:

mkdir rosenbrock
cd rosenbrock
cutest2matlab_macos.sh ROSENBR

This should produce two shared libraries:

libROSENBR.dylib
mcutest.mexmaca64

cd /the/directory/where/you/ran/cutest2matlab_macos.sh
prob = cutest_setup()

If that works, you should see a Matlab struct and you should be able to write, e.g.,

f = cutest_obj(prob.x)

#### Installing the Matlab Interface on Legacy Intel Macs

This is even more involved unfortunately. First download the following xml file and place it in ~/Library/Application\ Support/Mathworks/MATLAB/R2018a/ (substitute your Matlab version). Then download the shell script below and place it somewhere on your PATH. I like to create ~/bin and add it to my PATH. Make the script executable:

mkdir ~/bin  # if not already done