class_docstr: Quadratic subproblem solved by nearly exact iterative method.
  
  Notes
  -----
  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.
  
  References
  ----------
  .. [1] A.R. Conn, N.I. Gould, and P.L. Toint, "Trust region methods",
         Siam, pp. 169-200, 2000.
  .. [2] J. Nocedal and  S. Wright, "Numerical optimization",
         Springer Science & Business Media. pp. 83-91, 2006.
  .. [3] 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.
class_docstr_tok: ["Quadratic","subproblem","solved","by","nearly","exact","iterative","method",".","Notes","--","--","-","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",".","References","--","--","--","--","--","..","[","1","]","A.R",".","Conn",",","N.I",".","Gould",",","and","P.L",".","Toint",",","``","Trust","region","methods","''",",","Siam",",","pp",".","169-200",",","2000",".","..","[","2","]","J.","Nocedal","and","S.","Wright",",","``","Numerical","optimization","''",",","Springer","Science","&","Business","Media",".","pp",".","83-91",",","2006",".","..","[","3","]","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","."]
docstr: Solve quadratic subproblem
docstr_tok: ["Solve","quadratic","subproblem"]
code: def solve(self, tr_radius):
      """Solve quadratic subproblem"""
  
      lambda_current, lambda_lb, lambda_ub = self._initial_values(
          tr_radius
      )
      n = self.dimension
      hits_boundary = True
      already_factorized = False
      self.niter = 0
  
      while True:
          # Compute Cholesky factorization
          if already_factorized:
              already_factorized = False
          else:
              H = self.hess + lambda_current * np.eye(n)
              U, info = self.cholesky(
                  H, lower=False, overwrite_a=False, clean=True
              )
  
          self.niter += 1
  
          # Check if factorization succeeded
          if info == 0 and self.jac_mag > self.CLOSE_TO_ZERO:
              # Successful factorization
  
              # Solve `U.T U p = s`
              p = cho_solve((U, False), -self.jac)
  
              p_norm = norm(p)
  
              # Check for interior convergence
              if p_norm <= tr_radius and lambda_current == 0:
                  hits_boundary = False
                  break
  
              # Solve `U.T w = p`
              w = solve_triangular(U, p, trans="T")
  
              w_norm = norm(w)
  
              # Compute Newton step accordingly to
              # formula (4.44) p.87 from ref [2]_.
              delta_lambda = (
                  (p_norm / w_norm) ** 2
                  * (p_norm - tr_radius)
                  / tr_radius
              )
              lambda_new = lambda_current + delta_lambda
  
              if p_norm < tr_radius:  # Inside boundary
                  s_min, z_min = estimate_smallest_singular_value(U)
  
                  ta, tb = self.get_boundaries_intersections(
                      p, z_min, tr_radius
                  )
  
                  # Choose `step_len` with the smallest magnitude.
                  # The reason for this choice is explained at
                  # ref [3]_, p. 6 (Immediately before the formula
                  # for `tau`).
                  step_len = min([ta, tb], key=abs)
  
                  # Compute the quadratic term  (p.T*H*p)
                  quadratic_term = np.dot(p, np.dot(H, p))
  
                  # Check stop criteria
                  relative_error = (step_len**2 * s_min**2) / (
                      quadratic_term + lambda_current * tr_radius**2
                  )
                  if relative_error <= self.k_hard:
                      p += step_len * z_min
                      break
  
                  # Update uncertanty bounds
                  lambda_ub = lambda_current
                  lambda_lb = max(
                      lambda_lb, lambda_current - s_min**2
                  )
  
                  # Compute Cholesky factorization
                  H = self.hess + lambda_new * np.eye(n)
                  c, info = self.cholesky(
                      H, lower=False, overwrite_a=False, clean=True
                  )
  
                  # Check if the factorization have succeeded
                  #
                  if info == 0:  # Successful factorization
                      # Update damping factor
                      lambda_current = lambda_new
                      already_factorized = True
                  else:  # Unsuccessful factorization
                      # Update uncertanty bounds
                      lambda_lb = max(lambda_lb, lambda_new)
  
                      # Update damping factor
                      lambda_current = max(
                          np.sqrt(lambda_lb * lambda_ub),
                          lambda_lb
                          + self.UPDATE_COEFF * (lambda_ub - lambda_lb),
                      )
  
              else:  # Outside boundary
                  # Check stop criteria
                  relative_error = abs(p_norm - tr_radius) / tr_radius
                  if relative_error <= self.k_easy:
                      break
  
                  # Update uncertanty bounds
                  lambda_lb = lambda_current
  
                  # Update damping factor
                  lambda_current = lambda_new
  
          elif info == 0 and self.jac_mag <= self.CLOSE_TO_ZERO:
              # jac_mag very close to zero
  
              # Check for interior convergence
              if lambda_current == 0:
                  p = np.zeros(n)
                  hits_boundary = False
                  break
  
              s_min, z_min = estimate_smallest_singular_value(U)
              step_len = tr_radius
  
              # Check stop criteria
              if (
                  step_len**2 * s_min**2
                  <= self.k_hard * lambda_current * tr_radius**2
              ):
                  p = step_len * z_min
                  break
  
              # Update uncertanty bounds
              lambda_ub = lambda_current
              lambda_lb = max(lambda_lb, lambda_current - s_min**2)
  
              # Update damping factor
              lambda_current = max(
                  np.sqrt(lambda_lb * lambda_ub),
                  lambda_lb
                  + self.UPDATE_COEFF * (lambda_ub - lambda_lb),
              )
  
          else:  # Unsuccessful factorization
              # Compute auxiliary terms
              delta, v = singular_leading_submatrix(H, U, info)
              v_norm = norm(v)
  
              # Update uncertanty interval
              lambda_lb = max(
                  lambda_lb, lambda_current + delta / v_norm**2
              )
  
              # Update damping factor
              lambda_current = max(
                  np.sqrt(lambda_lb * lambda_ub),
                  lambda_lb
                  + self.UPDATE_COEFF * (lambda_ub - lambda_lb),
              )
  
      self.lambda_lb = lambda_lb
      self.lambda_current = lambda_current
      self.previous_tr_radius = tr_radius
  
      return p, hits_boundary
  
file_path: scipy/scipy/optimize/_trustregion_exact.py
imports: import numpy
  from scipy.linalg import norm, get_lapack_funcs, solve_triangular, cho_solve
  from ._trustregion import _minimize_trust_region, BaseQuadraticSubproblem
label_desc: Use image node_id 3 for calling the IterativeSubproblem obj's underlying member method code with example usage: obj.solve(tr_radius) and returns: p,  hits_boundary