Trust-region subproblem solvers for nonlinear/nonconvex optimization

## Project description

This package provides Python routines for solving the trust-region subproblem from nonlinear, nonconvex optimization. For more details on trust-region methods, see the book: A. R. Conn, N. I. M. Gould and Ph. L. Toint (2000), Trust-Region Methods, MPS-SIAM Series on Optimization.

The trust-region subproblem we solve is

`min_{s in R^n} g^T s + 0.5 s^T H s, subject to ||s||_2 <= delta (and sl <= s <= su)`

**Quick install**

`$ sudo apt-get install gfortran $ pip install --user numpy $ pip install --user trustregion`

For more details, see below. Note that NumPy must be installed first, as it is used to compile the Fortran-linked modules.

**Interface**

The Python package `trustregion`

provides one routine, `solve`

, with interface:

`import trustregion s = trustregion.solve(g, H, delta, sl=None, su=None, verbose_output=False) s, gnew, crvmin = trustregion.solve(g, H, delta, sl=None, su=None, verbose_output=True)`

where the inputs are

`g`

, the gradient of the objective (as a 1D NumPy array)`H`

, the symmetric Hessian matrix of the objective (as a 2D square NumPy array) - this can be`None`

if the model is linear`delta`

, the trust-region radius (non-negative float)`sl`

, the lower bounds on the step (as a 1D NumPy array) - this can be`None`

if not present, but`sl`

and`su`

must either be both`None`

or both set`su`

, the upper bounds on the step (as a 1D NumPy array) - this can be`None`

if not present, but`sl`

and`su`

must either be both`None`

or both set`verbose_output`

, a flag indicating which outputs to return.

The outputs are:

`s`

, an approximate minimizer of the subproblem (as a 1D NumPy array)`gnew`

, the gradient of the objective at the solution`s`

(i.e.`gnew = g + H.dot(s)`

)`crvmin`

, a float giving information about the curvature of the problem. If`s`

is on the trust-region boundary (given by`delta`

), then`crvmin=0`

. If`s`

is constrained in all directions by the box constraints, then`crvmin=-1`

. Otherwise,`crvmin>0`

is the smallest curvature seen in the Hessian.

**Example Usage**

Examples for the use of `trustregion.solve`

can be found in the examples directory on Github.

**Algorithms**

`trustregion`

implements three different methods for solving the subproblem, based on the problem class (in Fortran 90, wrapped to Python):

`trslin.f90`

solves the linear objective case (where`H=None`

or`H=0`

), using Algorithm B.1 from: L. Roberts (2019), Derivative-Free Algorithms for Nonlinear Optimisation Problems, PhD Thesis, University of Oxford.`trsapp.f90`

solves the quadratic case without box constraints. It is a minor modification of the routine of the same name in`NEWUOA`

[M. J. D. Powell (2004), The NEWUOA software for unconstrained optimization without derivatives, technical report DAMTP 2004/NA05, University of Cambridge].`trsbox.f90`

solves the quadratic case with box constraints. It is a minor modification of the routine of the same name in`BOBYQA`

[M. J. D. Powell (2009), The BOBYQA algorithm for bound constrained optimization without derivatives, technical report DAMTP 2009/NA06, University of Cambridge].

In the linear case, an active-set method is used to solve the resulting convex problem. In the quadratic cases, a modification of the Steihaug-Toint/conjugate gradient method is used. For more details, see the relevant references above.

## Requirements

`trustregion`

requires the following software to be installed:

Fortran compiler (e.g. gfortran)

Python 2.7 or Python 3 (http://www.python.org/)

Additionally, the following python packages should be installed (these will be installed automatically if using *pip*, see Installation using pip):

NumPy 1.11 or higher (http://www.numpy.org/)

## Installation using pip

For easy installation, use pip as root:

`$ [sudo] pip install numpy $ [sudo] pip install trustregion`

Note that NumPy should be installed before `trustregion`

, as it is used to compile the Fortran modules.

If you do not have root privileges or you want to install `trustregion`

for your private use, you can use:

`$ pip install --user numpy $ pip install --user trustregion`

which will install `trustregion`

in your home directory.

Note that if an older install of `trustregion`

is present on your system you can use:

`$ [sudo] pip install --upgrade trustregion`

to upgrade `trustregion`

to the latest version.

## Manual installation

Alternatively, you can download the source code from Github and unpack as follows:

`$ git clone https://github.com/lindonroberts/trust-region $ cd trust-region`

To upgrade `trustregion`

to the latest version, navigate to the top-level directory (i.e. the one containing `setup.py`

) and rerun the installation using `pip`

, as above:

`$ git pull $ [sudo] pip install . # with admin privileges`

## Testing

If you installed `trustregion`

manually, you can test your installation by running:

`$ python setup.py test`

Alternatively, the documentation provides some simple examples of how to run `trustregion`

.

## Uninstallation

If `trustregion`

was installed using *pip* you can uninstall as follows:

`$ [sudo] pip uninstall trustregion`

If `trustregion`

was installed manually you have to remove the installed files by hand (located in your python site-packages directory).

## Bugs

Please report any bugs using GitHub’s issue tracker.

## License

This algorithm is released under the GNU GPL license.

## Project details

## Release history Release notifications | RSS feed

## Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.