trustregion: Trustregion subproblem solver
This package provides Python routines for solving the trustregion subproblem from nonlinear, nonconvex optimization. For more details on trustregion methods, see the book: A. R. Conn, N. I. M. Gould and Ph. L. Toint (2000), TrustRegion Methods, MPSSIAM Series on Optimization.
The trustregion 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 aptget 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 Fortranlinked 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 beNone
if the model is linear 
delta
, the trustregion radius (nonnegative float) 
sl
, the lower bounds on the step (as a 1D NumPy array)  this can beNone
if not present, butsl
andsu
must either be bothNone
or both set 
su
, the upper bounds on the step (as a 1D NumPy array)  this can beNone
if not present, butsl
andsu
must either be bothNone
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 solutions
(i.e.gnew = g + H.dot(s)
) 
crvmin
, a float giving information about the curvature of the problem. Ifs
is on the trustregion boundary (given bydelta
), thencrvmin=0
. Ifs
is constrained in all directions by the box constraints, thencrvmin=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 (whereH=None
orH=0
), using Algorithm B.1 from: L. Roberts (2019), DerivativeFree 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 inNEWUOA
[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 inBOBYQA
[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 activeset method is used to solve the resulting convex problem. In the quadratic cases, a modification of the SteihaugToint/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/trustregion $ cd trustregion
To upgrade trustregion
to the latest version, navigate to the toplevel 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 sitepackages directory).
Bugs
Please report any bugs using GitHub's issue tracker.
License
This algorithm is released under the GNU GPL license.