### 17 releases (10 breaking)

0.11.0 | Sep 12, 2024 |
---|---|

0.9.1 | Sep 9, 2024 |

0.4.0 | Jul 30, 2024 |

#**157** in Math

**871** downloads per month

Used in **4** crates
(2 directly)

**MIT/Apache**

**1MB**

2.5K
SLoC

# Function Minimization in Rust, Simplified

, (/ɡəˈneɪʃ/) named after the Hindu god of wisdom, provides several common minimization algorithms as well as a straightforward, trait-based interface to create your own extensions. This crate is intended to be as simple as possible. The user needs to implement the `ganesh`

trait on some struct which will take a vector of parameters and return a single-valued `Function`

($`Result`

$). Users can optionally provide a gradient function to speed up some algorithms, but a default central finite-difference implementation is provided so that all algorithms will work out of the box.`f``(`\mathbb`{`R`}``^`n`)` \to \mathbb`{`R`}`

[!CAUTION] This crate is still in an early development phase, and the API is not stable. It can (and likely will) be subject to breaking changes before the 1.0.0 version release (and hopefully not many after that).

# Table of Contents

# Key Features

- Simple but powerful trait-oriented library which tries to follow the Unix philosophy of "do one thing and do it well".
- Generics to allow for different numeric types to be used in the provided algorithms.
- Algorithms that are simple to use with sensible defaults.
- Traits which make developing future algorithms simple and consistent.

# Quick Start

This crate provides some common test functions in the

module. Consider the following implementation of the Rosenbrock function:`test_functions`

`use` `std``::``convert``::`Infallible`;`
`use` `ganesh``::``prelude``::``*``;`
`pub` `struct` `Rosenbrock` `{`
`pub` `n``:` `usize`,
`}`
`impl` `Function``<``f64`, `(``)`, Infallible`>` `for`` ``Rosenbrock` `{`
`fn` `evaluate``(``&``self`, `x``:` `&`[`f64`], `_user_data``:` `&``mut` `(``)``)`` ``->` `Result``<``f64`, Infallible`>` `{`
`Ok``(``(``0``..``(``self``.`n `-` `1``)``)`
`.``map``(``|``i``|` `100.``0` `*` `(`x`[`i `+` `1``]` `-` x`[`i`]``.``powi``(``2``)``)``.``powi``(``2``)` `+` `(``1.``0` `-` x`[`i`]``)``.``powi``(``2``)``)`
`.``sum``(``)``)`
`}`
`}`

To minimize this function, we could consider using the Nelder-Mead algorithm:

`use` `ganesh``::``prelude``::``*``;`
`use` `ganesh``::``algorithms``::`NelderMead`;`
`fn` `main``(``)`` ``->` `Result``<``(``)`, Infallible`>` `{`
`let` problem `=` Rosenbrock `{` n`:` `2` `}``;`
`let` nm `=` `NelderMead``::`default`(``)``;`
`let` `mut` m `=` `Minimizer``::`new`(`nm`,` `2``)``;`
`let` x0 `=` `&``[``2.``0``,` `2.``0``]``;`
m`.``minimize``(``&`problem`,` x0`,` `&``mut` `(``)``)``?``;`
`println!``(``"``{}``"``,` m`.`status`)``;`
`Ok``(``(``)``)`
`}`

This should output

`MSG:`` term_f = STDDEV`
`X:`` +1.000 ± 0.707`
`+1.000`` ± 1.416`
`F``(X`)`:`` +0.000`
`N_F_EVALS:`` 159`
`N_G_EVALS:`` 0`
`CONVERGED:`` true`
`COV:`` `
`┌`` ┐`
`│`` 0.500 1.000 │`
`│`` 1.000 2.005 │`
`└`` ┘`

# Bounds

All minimizers in

have access to a feature which allows algorithms which usually function in unbounded parameter spaces to only return results inside a bounding box. This is done via a parameter transformation, the same one used by `ganesh`

and `LMFIT`

. This transform is not enacted on algorithms which already have bounded implementations, like `MINUIT`

. While the user inputs parameters within the bounds, unbounded algorithms can (and in practice will) convert those values to a set of unbounded "internal" parameters. When functions are called, however, these internal parameters are converted back into bounded "external" parameters, via the following transformations:`L -BFGS-B`

Upper and lower bounds:

`x_``\`text`{`int`}` = `\`arcsin`\`left(2`\`frac`{`x_`\`text`{`ext`}` - x_`\`text`{`min`}``}``{`x_`\`text`{`max`}` - x_`\`text`{`min`}``}` - 1`\`right)

`x_``\`text`{`ext`}` = x_`\`text`{`min`}` + `\`left(`\`sin(x_`\`text`{`int`}`) + 1`\`right)`\`frac`{`x_`\`text`{`max`}` - x_`\`text`{`min`}``}``{`2`}`

Upper bound only:

`x_``\`text`{`int`}` = `\`sqrt`{`(x_`\`text`{`max`}` - x_`\`text`{`ext`}` + 1)^2 - 1`}`

`x_``\`text`{`ext`}` = x_`\`text`{`max`}` + 1 - `\`sqrt`{`x_`\`text`{`int`}`^2 + 1`}`

Lower bound only:

`x_``\`text`{`int`}` = `\`sqrt`{`(x_`\`text`{`ext`}` - x_`\`text`{`min`}` + 1)^2 - 1`}`

`x_``\`text`{`ext`}` = x_`\`text`{`min`}` - 1 + `\`sqrt`{`x_`\`text`{`int`}`^2 + 1`}`

As noted in the documentation for both

and `LMFIT`

, these bounds should be used with caution. They turn linear problems into nonlinear ones, which can mess with error propagation and even fit convergence, not to mention increase function complexity. Methods which output covariance matrices need to be adjusted if bounded, and `MINUIT`

recommends fitting a second time near a minimum without bounds to ensure proper error propagation.`MINUIT`

# Future Plans

- Eventually, I would like to implement MCMC algorithms and some more modern gradient-free optimization techniques.
- There are probably many optimizations and algorithm extensions that I'm missing right now because I just wanted to get it working first.
- A test suite

#### Dependencies

~3MB

~57K SLoC