Python Interface

Installation

We don’t have a setup.py yet but use CMake to build the interface. Ensure that either TRLIB_BUILD_PYTHON2` or ``TRLIB_BUILD_PYTHON3 is set to ON before compilation, depending on the python version you like to use. At the moment you have to ensure that $TRLIB_DIR/build is contained in your $PYTHON_PATH.

Usage

Use the function trlib_solve() to solve a trust region subproblem und umin() to solve an unconstrained nonlinear optimization problem with a standard trust-region algorithm.

Functions

trlib_solve(hess, grad, radius, invM = lambda x: x, TR=None, reentry=False, verbose=0, ctl_invariant=0, convexify=1, earlyterm=1)

Solves trust-region subproblem

\(\min_{x \in \mathbb R^n} \tfrac 12 x^T H x + g^T x \quad \text{s.t.} \, \Vert x \Vert_M \le r\)

with a projected CG/Lanczos method.

Parameters:
  • hess ({sparse matrix, dense matrix, LinearOperator}) – hessian matrix/operator H with shape (n,n)
  • grad (array) – gradient g with shape (n,1)
  • radius (float) – trust-region radius r
  • invM ({sparse matrix, dense matrix, LinearOperator}, optional) – inverse of matrix/operator defining trust-region constraint norm, default: identity, acts as preconditioner in CG/Lanczos
  • TR (dict, optional) – TR output of previous call for hotstarting
  • reentry (boolean, optional) – set this to True, if you want to resolve with all data fixed but changed trust-region radius, provide TR of previous call
  • verbose (int, optional) – verbosity level
  • ctl_invariant (int, optional) – flag that determines how to treat hard-case, see C API of trlib_krylov_min()
  • convexify (int, optional) – flag that determines if resolving with convexified should be tried if solution seems unrealistic
  • earlyterm (int, optional) – flag that determines if solver should terminate early prior to convergence if it seems unlikely that progress will be made soon
Returns:

(sol, TR): solution vector and trust-region instance data, needed for warmstart

  • TR[‘ret’] gives return code of trlib_krylov_min(),
  • TR[‘obj’] gives objective funtion value,
  • TR[‘lam’] lagrange multiplier
Return type:

(array, dict)
Example:

Solve a sample large-scale problem with indefinite diagonal hessian matrix:

>>> import scipy.sparse
>>> import numpy as np
>>> H = scipy.sparse.diags(np.linspace(-1.0, 100.0, 1000),0)
>>> g = np.ones(1000)
>>> x, TR = trlib.trlib_solve(H, g, 1.0)
>>> np.linalg.norm(x)
1.0000000000000002
>>> x, TR = trlib.trlib_solve(H, g, .5, reentry=True, TR=TR)
0.50000000000000011
umin(obj, grad, hessvec, x, tol=1e-5, eta1=1e-2, eta2=.95, gamma1=.5, gamma2=2., itmax=-1, verbose=1)

Standard Trust Region Algorithm for Unconstrained Optimization Problem:

\(\min_{x \in \mathbb R^n} f(x)\)

This implements Algorithm 6.1 of [Gould1999] with slight modifications:

  • check for descent
  • aggresive trust region reduction upon failed step if next iteration will have the same subproblem solution
Parameters:
  • obj (function) – callback that computes \(x \mapsto f(x)\)
  • grad (function) – callback that computes \(x \mapsto \nabla f(x)\)
  • hessvec (function) – callback that computes \((x, d) \mapsto \nabla^2 f(x) \cdot d\)
  • x (array) – starting point
  • tol (float, optional) – convergence tolerance, convergence achieved if \(\Vert \nabla f(x) \Vert_2 \le \texttt{tol}\)
  • eta1 (float, optional) – tolerance to discard step: \(\rho = \frac{\text{actual reducion}}{\text{predicted reduction}} \le \eta_1\)
  • eta2 (float, optional) – tolerance to enlarge trust region: \(\rho = \frac{\text{actual reducion}}{\text{predicted reduction}} \ge \eta_2\)
  • gamma1 (float, optional) – reduction factor for trust region radius upon failed step
  • gamma2 (float, optional) – blow-up factor for trust region radius upon succesfully accepted step
  • itmax (int, optional) – maximum number of iterations
  • verbose (int, optional) – verbosity level
Returns:

last point, solution in case of convergence
Return type:

array
Example:

Compute the minimizer of the extended Rosenbrock function in R^10:

>>> import trlib
>>> import numpy as np
>>> import scipy.optimize
>>> trlib.umin(scipy.optimize.rosen, scipy.optimize.rosen_der,
        scipy.optimize.rosen_hess_prod, np.zeros(5))
it   obj         ‖g‖        radius     step       rho          ?  nhv
  0 +4.0000e+00 4.0000e+00 4.4721e-01 4.4721e-01 -3.9705e+00  -    2
  1 +4.0000e+00 4.0000e+00 2.2361e-01 2.2361e-01 +6.4377e-01  +    0
  2 +3.7258e+00 1.0252e+01 2.2361e-01 4.5106e-02 +1.0011e+00  +    1
  3 +3.4943e+00 2.3702e+00 4.4721e-01 4.4721e-01 -1.6635e+00  -    3
  4 +3.4943e+00 2.3702e+00 2.2361e-01 2.2361e-01 +6.3041e-01  +    0
  5 +3.1553e+00 1.0513e+01 2.2361e-01 3.2255e-02 +1.0081e+00  +    1
  6 +2.9844e+00 3.0912e+00 4.4721e-01 4.4721e-01 -8.6302e-01  -    3
  7 +2.9844e+00 3.0912e+00 2.2361e-01 2.2361e-01 +8.2990e-01  +    0
  8 +2.5633e+00 8.4640e+00 2.2361e-01 4.1432e-02 +1.0074e+00  +    2
  9 +2.4141e+00 3.2440e+00 4.4721e-01 4.4721e-01 -3.3029e-01  -    4
 10 +2.4141e+00 3.2440e+00 2.2361e-01 2.2361e-01 +7.7786e-01  +    0
 11 +1.9648e+00 6.5362e+00 2.2361e-01 2.2361e-01 +1.1319e+00  +    4
 12 +1.4470e+00 5.1921e+00 4.4721e-01 4.0882e-01 +1.7910e-01  +    5
 13 +1.3564e+00 1.6576e+01 4.4721e-01 7.9850e-02 +1.0404e+00  +    2
 14 +6.8302e-01 3.7423e+00 8.9443e-01 4.0298e-01 -4.9142e-01  -    5
 15 +6.8302e-01 3.7423e+00 3.6268e-01 3.6268e-01 +8.1866e-02  +    0
 16 +6.5818e-01 1.3817e+01 3.6268e-01 4.8671e-02 +1.0172e+00  +    1
 17 +3.1614e-01 5.9764e+00 7.2536e-01 1.3202e-02 +1.0081e+00  +    2
 18 +2.8033e-01 1.4543e+00 1.4507e+00 3.5557e-01 -8.6703e-02  -    5
 19 +2.8033e-01 1.4543e+00 3.2001e-01 3.2001e-01 +3.4072e-01  +    0
it   obj         ‖g‖        radius     step       rho          ?  nhv
 20 +2.3220e-01 1.0752e+01 3.2001e-01 2.0244e-02 +1.0101e+00  +    1
 21 +1.2227e-01 5.0526e+00 6.4002e-01 1.1646e-02 +1.0073e+00  +    2
 22 +9.6271e-02 1.6755e+00 1.2800e+00 1.4701e-03 +9.9992e-01  +    1
 23 +9.5040e-02 6.1617e-01 2.5601e+00 3.3982e-01 -3.6365e-01  -    5
 24 +9.5040e-02 6.1617e-01 3.0584e-01 3.0584e-01 +1.3003e-01  +    0
 25 +8.6495e-02 9.2953e+00 3.0584e-01 1.1913e-02 +1.0071e+00  +    1
 26 +3.0734e-02 4.0422e+00 6.1167e-01 7.7340e-03 +1.0056e+00  +    2
 27 +1.7104e-02 1.1570e+00 1.2233e+00 9.7535e-04 +1.0004e+00  +    1
 28 +1.6540e-02 3.6078e-01 2.4467e+00 2.0035e-01 +5.5171e-01  +    5
 29 +8.6950e-03 3.5281e+00 2.4467e+00 3.7360e-03 +1.0023e+00  +    1
 30 +2.0894e-03 1.4262e+00 4.8934e+00 2.4287e-03 +1.0018e+00  +    2
 31 +5.8038e-04 3.5326e-01 9.7868e+00 4.3248e-04 +1.0004e+00  +    2
 32 +5.1051e-04 7.3221e-02 1.9574e+01 4.3231e-02 +9.9862e-01  +    5
 33 +1.4135e-05 1.4757e-01 3.9147e+01 2.0304e-04 +1.0001e+00  +    3
 34 +7.1804e-07 1.3804e-02 7.8294e+01 1.5512e-03 +1.0008e+00  +    5
 35 +2.2268e-11 1.8517e-04 1.5659e+02 2.0956e-06 +1.0000e+00  +    5
 36 +3.7550e-21 1.2923e-10