tfp.substrates.numpy.math.find_root_chandrupatla

Finds root(s) of a scalar function using Chandrupatla's method.

tfp.substrates.numpy.math.find_root_chandrupatla(
    objective_fn,
    low=None,
    high=None,
    position_tolerance=1e-08,
    value_tolerance=0.0,
    max_iterations=50,
    stopping_policy_fn=tf.reduce_all,
    validate_args=False,
    name='find_root_chandrupatla'
)

Chandrupatla's method [1, 2] is a root-finding algorithm that is guaranteed to converge if a root lies within the given bounds. It generalizes the bisection method; at each step it chooses to perform either bisection or inverse quadratic interpolation. This makes it similar in spirit to Brent's method, which also considers steps that use the secant method, but Chandrupatla's method is simpler and often converges at least as quickly [3].

objective_fn Python callable for which roots are searched. It must be a callable of a single variable. objective_fn must return a Tensor with shape batch_shape and dtype matching lower_bound and upper_bound.
low Float Tensor of shape batch_shape representing a lower bound(s) on the value of a root(s). If either of low or high is not provided, both are ignored and tfp.math.bracket_root is used to attempt to infer bounds. Default value: None.
high Float Tensor of shape batch_shape representing an upper bound(s) on the value of a root(s). If either of low or high is not provided, both are ignored and tfp.math.bracket_root is used to attempt to infer bounds. Default value: None.
position_tolerance Optional Tensor representing the maximum absolute error in the positions of the estimated roots. Shape must broadcast with batch_shape. Default value: 1e-8.
value_tolerance Optional Tensor representing the absolute error allowed in the value of the objective function. If the absolute value of objective_fn is smaller than value_tolerance at a given position, then that position is considered a root for the function. Shape must broadcast with batch_shape. Default value: 1e-8.
max_iterations Optional Tensor or Python integer specifying the maximum number of steps to perform. Shape must broadcast with batch_shape. Default value: 50.
stopping_policy_fn Python callable controlling the algorithm termination. It must be a callable accepting a Tensor of booleans with the same shape as lower_bound and upper_bound (denoting whether each search is finished), and returning a scalar boolean Tensor indicating whether the overall search should stop. Typical values are tf.reduce_all (which returns only when the search is finished for all points), and tf.reduce_any (which returns as soon as the search is finished for any point). Default value: tf.reduce_all (returns only when the search is finished for all points).
validate_args Python bool indicating whether to validate arguments. Default value: False.
name Python str name prefixed to ops created by this function. Default value: 'find_root_chandrupatla'.

root_search_results A Python namedtuple containing the following items: estimated_root: Tensor containing the last position explored. If the search was successful within the specified tolerance, this position is a root of the objective function. objective_at_estimated_root: Tensor containing the value of the objective function at position. If the search was successful within the specified tolerance, then this is close to 0. num_iterations: The number of iterations performed.

References

[1] Tirupathi R. Chandrupatla. A new hybrid quadratic/bisection algorithm for finding the zero of a nonlinear function without using derivatives. Advances in Engineering Software, 28.3:145-149, 1997. [2] Philipp OJ Scherer. Computational Physics. Springer Berlin, Heidelberg, 2010. Section 6.1.7.3 https://books.google.com/books?id=cC-8BAAAQBAJ&pg=PA95 [3] Jason Sachs. Ten Little Algorithms, Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method (2015). https://www.embeddedrelated.com/showarticle/855.php