# `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.

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 _ 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.

  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. .

  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 _,  and , which implement similar algorithms. The algorithm is basically that of _ but ideas from  and  were also used.

  A.R. Conn, N.I. Gould, and P.L. Toint, “Trust region methods”, Siam, pp. 169-200, 2000.
  (1, 2) J. Nocedal and S. Wright, “Numerical optimization”, Springer Science & Business Media. pp. 83-91, 2006.
  (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 _.

`solve`(tr_radius)