Coder Social home page Coder Social logo

lindonroberts / trust-region Goto Github PK

View Code? Open in Web Editor NEW
23.0 1.0 2.0 116 KB

Python trust-region subproblem solvers for nonlinear optimization

License: GNU General Public License v3.0

Python 31.41% Fortran 30.73% Meson 1.55% C 36.31%
optimization optimization-algorithms optimization-tools optimization-methods nonlinear-optimization python numerical-optimization numerical-analysis

trust-region's Introduction

trustregion: Trust-region subproblem solver

Build Status

GNU GPL v3 License

Latest PyPI version

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):

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:

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

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:

$ pip install pytest
$ cd trustregion/tests
$ python -m pytest

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.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.