Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/scipy/optimize/_trustregion_dogleg.py: 23%
39 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-12-12 06:31 +0000
1"""Dog-leg trust-region optimization."""
2import numpy as np
3import scipy.linalg
4from ._trustregion import (_minimize_trust_region, BaseQuadraticSubproblem)
6__all__ = []
9def _minimize_dogleg(fun, x0, args=(), jac=None, hess=None,
10 **trust_region_options):
11 """
12 Minimization of scalar function of one or more variables using
13 the dog-leg trust-region algorithm.
15 Options
16 -------
17 initial_trust_radius : float
18 Initial trust-region radius.
19 max_trust_radius : float
20 Maximum value of the trust-region radius. No steps that are longer
21 than this value will be proposed.
22 eta : float
23 Trust region related acceptance stringency for proposed steps.
24 gtol : float
25 Gradient norm must be less than `gtol` before successful
26 termination.
28 """
29 if jac is None:
30 raise ValueError('Jacobian is required for dogleg minimization')
31 if not callable(hess):
32 raise ValueError('Hessian is required for dogleg minimization')
33 return _minimize_trust_region(fun, x0, args=args, jac=jac, hess=hess,
34 subproblem=DoglegSubproblem,
35 **trust_region_options)
38class DoglegSubproblem(BaseQuadraticSubproblem):
39 """Quadratic subproblem solved by the dogleg method"""
41 def cauchy_point(self):
42 """
43 The Cauchy point is minimal along the direction of steepest descent.
44 """
45 if self._cauchy_point is None:
46 g = self.jac
47 Bg = self.hessp(g)
48 self._cauchy_point = -(np.dot(g, g) / np.dot(g, Bg)) * g
49 return self._cauchy_point
51 def newton_point(self):
52 """
53 The Newton point is a global minimum of the approximate function.
54 """
55 if self._newton_point is None:
56 g = self.jac
57 B = self.hess
58 cho_info = scipy.linalg.cho_factor(B)
59 self._newton_point = -scipy.linalg.cho_solve(cho_info, g)
60 return self._newton_point
62 def solve(self, trust_radius):
63 """
64 Minimize a function using the dog-leg trust-region algorithm.
66 This algorithm requires function values and first and second derivatives.
67 It also performs a costly Hessian decomposition for most iterations,
68 and the Hessian is required to be positive definite.
70 Parameters
71 ----------
72 trust_radius : float
73 We are allowed to wander only this far away from the origin.
75 Returns
76 -------
77 p : ndarray
78 The proposed step.
79 hits_boundary : bool
80 True if the proposed step is on the boundary of the trust region.
82 Notes
83 -----
84 The Hessian is required to be positive definite.
86 References
87 ----------
88 .. [1] Jorge Nocedal and Stephen Wright,
89 Numerical Optimization, second edition,
90 Springer-Verlag, 2006, page 73.
91 """
93 # Compute the Newton point.
94 # This is the optimum for the quadratic model function.
95 # If it is inside the trust radius then return this point.
96 p_best = self.newton_point()
97 if scipy.linalg.norm(p_best) < trust_radius:
98 hits_boundary = False
99 return p_best, hits_boundary
101 # Compute the Cauchy point.
102 # This is the predicted optimum along the direction of steepest descent.
103 p_u = self.cauchy_point()
105 # If the Cauchy point is outside the trust region,
106 # then return the point where the path intersects the boundary.
107 p_u_norm = scipy.linalg.norm(p_u)
108 if p_u_norm >= trust_radius:
109 p_boundary = p_u * (trust_radius / p_u_norm)
110 hits_boundary = True
111 return p_boundary, hits_boundary
113 # Compute the intersection of the trust region boundary
114 # and the line segment connecting the Cauchy and Newton points.
115 # This requires solving a quadratic equation.
116 # ||p_u + t*(p_best - p_u)||**2 == trust_radius**2
117 # Solve this for positive time t using the quadratic formula.
118 _, tb = self.get_boundaries_intersections(p_u, p_best - p_u,
119 trust_radius)
120 p_boundary = p_u + tb * (p_best - p_u)
121 hits_boundary = True
122 return p_boundary, hits_boundary