OptimLib

OptimLib is a lightweight C++ library of numerical optimization methods for nonlinear functions.

Features:

A C++11/14/17 library of local and global optimization algorithms, as well as root finding techniques.
Derivative-free optimization using advanced, parallelized metaheuristic methods.
Constrained optimization routines to handle simple box constraints, as well as systems of nonlinear constraints.
For fast and efficient matrix-based computation, OptimLib supports the following templated linear algebra libraries:
- Armadillo
- Eigen (version >= 3.4.0)
Automatic differentiation functionality is available through use of the Autodiff library
OpenMP-accelerated algorithms for parallel computation.
Straightforward linking with parallelized BLAS libraries, such as OpenBLAS.
Available as a single precision (float) or double precision (double) library.
Available as a header-only library, or as a compiled shared library.
Released under a permissive, non-GPL license.

Algorithms

A list of currently available algorithms includes:

Broyden's Method (for root finding)
Newton's method, BFGS, and L-BFGS
Gradient descent: basic, momentum, Adam, AdaMax, Nadam, NadaMax, and more
Nonlinear Conjugate Gradient
Nelder-Mead
Differential Evolution (DE)
Particle Swarm Optimization (PSO)

Documentation

Full documentation is available online:

A PDF version of the documentation is available here.

API

The OptimLib API follows a relatively simple convention, with most algorithms called in the following manner:

algorithm_id(<initial/final values>, <objective function>, <objective function data>);

The inputs, in order, are:

A writable vector of initial values to define the starting point of the algorithm. In the event of successful completion, the initial values will be overwritten by the solution vector.
The 'objective function' is the user-defined function to be minimized (or zeroed-out in the case of root finding methods).
The final input is optional: it is any object that contains additional parameters necessary to evaluate the objective function.

For example, the BFGS algorithm is called using

bfgs(ColVec_t& init_out_vals, std::function<double (const ColVec_t& vals_inp, ColVec_t* grad_out, void* opt_data)> opt_objfn, void* opt_data);

where ColVec_t is used to represent, e.g., arma::vec or Eigen::VectorXd types.

Installation

OptimLib is available as a compiled shared library, or as header-only library, for Unix-alike systems only (e.g., popular Linux-based distros, as well as macOS). Use of this library with Windows-based systems, with or without MSVC, is not supported.

Requirements

OptimLib requires either the Armadillo or Eigen C++ linear algebra libraries. (Note that Eigen version 3.4.0 requires a C++14-compatible compiler.)

Before including the header files, define one of the following:

#define OPTIM_ENABLE_ARMA_WRAPPERS
#define OPTIM_ENABLE_EIGEN_WRAPPERS

Example:

#define OPTIM_ENABLE_EIGEN_WRAPPERS
#include "optim.hpp"

Installation Method 1: Shared Library

The library can be installed on Unix-alike systems via the standard ./configure && make method.

First clone the library and any necessary submodules:

# clone optim into the current directory
git clone https://github.com/kthohr/optim ./optim

# change directory
cd ./optim

# clone necessary submodules
git submodule update --init

Set (one) of the following environment variables before running configure:

export ARMA_INCLUDE_PATH=/path/to/armadillo
export EIGEN_INCLUDE_PATH=/path/to/eigen

Finally:

# build and install with Eigen
./configure -i "/usr/local" -l eigen -p
make
make install

The final command will install OptimLib into /usr/local.

Configuration options (see ./configure -h):

Primary

-h print help
-i installation path; default: the build directory
-f floating-point precision mode; default: double
-l specify the choice of linear algebra library; choose arma or eigen
-m specify the BLAS and Lapack libraries to link with; for example, -m "-lopenblas" or -m "-framework Accelerate"
-o compiler optimization options; defaults to -O3 -march=native -ffp-contract=fast -flto -DARMA_NO_DEBUG
-p enable OpenMP parallelization features (recommended)

Secondary

-c a coverage build (used with Codecov)
-d a 'development' build
-g a debugging build (optimization flags set to -O0 -g)

Special

--header-only-version generate a header-only version of OptimLib (see below)

Installation Method 2: Header-only Library

OptimLib is also available as a header-only library (i.e., without the need to compile a shared library). Simply run configure with the --header-only-version option:

./configure --header-only-version

This will create a new directory, header_only_version, containing a copy of OptimLib, modified to work on an inline basis. With this header-only version, simply include the header files (#include "optim.hpp) and set the include path to the head_only_version directory (e.g.,-I/path/to/optimlib/header_only_version).

R Compatibility

To use OptimLib with an R package, first generate a header-only version of the library (see above). Then simply add a compiler definition before including the OptimLib files.

For RcppArmadillo:

#define OPTIM_USE_RCPP_ARMADILLO
#include "optim.hpp"

For RcppEigen:

#define OPTIM_USE_RCPP_EIGEN
#include "optim.hpp"

Examples

To illustrate OptimLib at work, consider searching for the global minimum of the Ackley function:

Ackley

This is a well-known test function with many local minima. Newton-type methods (such as BFGS) are sensitive to the choice of initial values, and will perform rather poorly here. As such, we will employ a global search method--in this case: Differential Evolution.

Code:

#define OPTIM_ENABLE_EIGEN_WRAPPERS
#include "optim.hpp"
        
#define OPTIM_PI 3.14159265358979

double 
ackley_fn(const Eigen::VectorXd& vals_inp, Eigen::VectorXd* grad_out, void* opt_data)
{
    const double x = vals_inp(0);
    const double y = vals_inp(1);

    const double obj_val = 20 + std::exp(1) - 20*std::exp( -0.2*std::sqrt(0.5*(x*x + y*y)) ) - std::exp( 0.5*(std::cos(2 * OPTIM_PI * x) + std::cos(2 * OPTIM_PI * y)) );
            
    return obj_val;
}
        
int main()
{
    Eigen::VectorXd x = 2.0 * Eigen::VectorXd::Ones(2); // initial values: (2,2)
        
    bool success = optim::de(x, ackley_fn, nullptr);
        
    if (success) {
        std::cout << "de: Ackley test completed successfully." << std::endl;
    } else {
        std::cout << "de: Ackley test completed unsuccessfully." << std::endl;
    }
        
    std::cout << "de: solution to Ackley test:\n" << x << std::endl;
        
    return 0;
}

On x86-based computers, this example can be compiled using:

g++ -Wall -std=c++14 -O3 -march=native -ffp-contract=fast -I/path/to/eigen -I/path/to/optim/include optim_de_ex.cpp -o optim_de_ex.out -L/path/to/optim/lib -loptim

Output:

de: Ackley test completed successfully.
elapsed time: 0.028167s

de: solution to Ackley test:
  -1.2702e-17
  -3.8432e-16

On a standard laptop, OptimLib will compute a solution to within machine precision in a fraction of a second.

The Armadillo-based version of this example:

#define OPTIM_ENABLE_ARMA_WRAPPERS
#include "optim.hpp"
        
#define OPTIM_PI 3.14159265358979

double 
ackley_fn(const arma::vec& vals_inp, arma::vec* grad_out, void* opt_data)
{
    const double x = vals_inp(0);
    const double y = vals_inp(1);

    const double obj_val = 20 + std::exp(1) - 20*std::exp( -0.2*std::sqrt(0.5*(x*x + y*y)) ) - std::exp( 0.5*(std::cos(2 * OPTIM_PI * x) + std::cos(2 * OPTIM_PI * y)) );
            
    return obj_val;
}
        
int main()
{
    arma::vec x = arma::ones(2,1) + 1.0; // initial values: (2,2)
        
    bool success = optim::de(x, ackley_fn, nullptr);
        
    if (success) {
        std::cout << "de: Ackley test completed successfully." << std::endl;
    } else {
        std::cout << "de: Ackley test completed unsuccessfully." << std::endl;
    }
        
    arma::cout << "de: solution to Ackley test:\n" << x << arma::endl;
        
    re

Optim

Install / Use

README