optimize._trustregion_exact

Nearly exact trust-region optimization subproblem.

Module Contents

Classes

IterativeSubproblem(self,x,fun,jac,hess,hessp=None,k_easy=0.1,k_hard=0.2) Quadratic subproblem solved by nearly exact iterative method.

Functions

_minimize_trustregion_exact(fun,x0,args=tuple,jac=None,hess=None,**trust_region_options) Minimization of scalar function of one or more variables using
estimate_smallest_singular_value(U) Given upper triangular matrix U estimate the smallest singular
gershgorin_bounds(H) Given a square matrix H compute upper
singular_leading_submatrix(A,U,k) Compute term that makes the leading k by k
_minimize_trustregion_exact(fun, x0, args=tuple, jac=None, hess=None, **trust_region_options)

Minimization of scalar function of one or more variables using a nearly exact trust-region algorithm.

initial_tr_radius : float
Initial trust-region radius.
max_tr_radius : float
Maximum value of the trust-region radius. No steps that are longer than this value will be proposed.
eta : float
Trust region related acceptance stringency for proposed steps.
gtol : float
Gradient norm must be less than gtol before successful termination.
estimate_smallest_singular_value(U)

Given upper triangular matrix U estimate the smallest singular value and the correspondent right singular vector in O(n**2) operations.

U : ndarray
Square upper triangular matrix.
s_min : float
Estimated smallest singular value of the provided matrix.
z_min : ndarray
Estimatied right singular vector.

The procedure is based on [1]_ and is done in two steps. First it finds a vector e with components selected from {+1, -1} such that the solution w from the system U.T w = e is as large as possible. Next it estimate U v = w. The smallest singular value is close to norm(w)/norm(v) and the right singular vector is close to v/norm(v).

The estimation will be better more ill-conditioned is the matrix.

[1]Cline, A. K., Moler, C. B., Stewart, G. W., Wilkinson, J. H. An estimate for the condition number of a matrix. 1979. SIAM Journal on Numerical Analysis, 16(2), 368-375.
gershgorin_bounds(H)

Given a square matrix H compute upper and lower bounds for its eigenvalues (Gregoshgorin Bounds). Defined ref. [1].

[1]Conn, A. R., Gould, N. I., & Toint, P. L. Trust region methods. 2000. Siam. pp. 19.
singular_leading_submatrix(A, U, k)

Compute term that makes the leading k by k submatrix from A singular.

A : ndarray
Symmetric matrix that is not positive definite.
U : ndarray
Upper triangular matrix resulting of an incomplete Cholesky decomposition of matrix A.
k : int
Positive integer such that the leading k by k submatrix from A is the first non-positive definite leading submatrix.
delta : float
Amout that should be added to the element (k, k) of the leading k by k submatrix of A to make it singular.
v : ndarray
A vector such that v.T B v = 0. Where B is the matrix A after delta is added to its element (k, k).
class IterativeSubproblem(x, fun, jac, hess, hessp=None, k_easy=0.1, k_hard=0.2)

Quadratic subproblem solved by nearly exact iterative method.

This subproblem solver was based on [1]_, [2] and [3], which implement similar algorithms. The algorithm is basically that of [1]_ but ideas from [2] and [3] were also used.

[1]A.R. Conn, N.I. Gould, and P.L. Toint, “Trust region methods”, Siam, pp. 169-200, 2000.
[2](1, 2) J. Nocedal and S. Wright, “Numerical optimization”, Springer Science & Business Media. pp. 83-91, 2006.
[3](1, 2) J.J. More and D.C. Sorensen, “Computing a trust region step”, SIAM Journal on Scientific and Statistical Computing, vol. 4(3), pp. 553-572, 1983.
__init__(x, fun, jac, hess, hessp=None, k_easy=0.1, k_hard=0.2)
_initial_values(tr_radius)

Given a trust radius, return a good initial guess for the damping factor, the lower bound and the upper bound. The values were chosen accordingly to the guidelines on section 7.3.8 (p. 192) from [1]_.

solve(tr_radius)

Solve quadratic subproblem