trustregion 1.2

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.