numericalderivative.ShiXieXuanNocedalGeneral

class numericalderivative.ShiXieXuanNocedalGeneral(general_finite_difference, absolute_precision=1e-15, minimum_test_ratio=1.5, maximum_test_ratio=6.0, alpha_parameter=2.0, step_factor=4.0, verbose=False)

Compute an approximately optimal step for the forward F.D. formula of any derivative

Uses general finite difference formula to compute an approximate value of \(f^{(d)}(x)\):

\[f^{(d)}(x) \approx \frac{d!}{h^d} \sum_{i = i_{\min}}^{i_\max} c_i f(x + h i)\]

where \(f\) is the function, \(x \in \mathbb{R}\) is the point, \(h > 0\) is the differentiation step, \(d \in \mathbb{N}\) is the differentiation order and \((c_i \in \mathbb{R})_{i_\min \leq i\leq i_\max}\) are the weights. The weights are computed so that the formula has order \(p\geq 1\): see GeneralFiniteDifference for more details on this topic. If \(f^{(d + p)}(x) \neq 0\), then the step which minimizes the total error is (see (Shi, Xie, Xuan & Nocedal, 2022) eq. 3.3 page 9):

\[h^\star = \left(\frac{d}{p} (d + p)! \frac{\|\boldsymbol{c}\|_1}{|b_{d + p}|} \frac{\epsilon_f}{\left|f^{(d + p)}(x)\right|}\right)^{\frac{1}{d + p}}\]

where \(\epsilon_f > 0\) is the absolute error of the function evaluation and \(p \in \mathbb{N}\) is the order of precision of the formula. If the order of magnitude of the order \(d + p\) derivative can be guessed, then compute_step() can be used. Alternatively, the goal of ShiXieXuanNocedalGeneral is to compute \(h^\star\) using function evaluations only and without estimating \(f^{(d + p)}(x)\).

The algorithm considers the test ratio (see (Shi, Xie, Xuan & Nocedal, 2022) eq. 3.14 page 7, with correction):

\[r(h) = \frac{\left|\left(\widetilde{f}^{(d)}(x; h) - \widetilde{f}^{(d)}(x; \alpha h) \right) h^d\right|}{A \epsilon_f}.\]

where \(h > 0\) is the step and \(\epsilon_f> 0\) is the absolute precision of evaluation of the function. The goal of the algorithm is to find the step such that (see (Shi, Xie, Xuan & Nocedal, 2022) eq. 2.4 page 4):

\[r_\ell \leq r(h) \leq r_u\]

where \(r_\ell > 1\) is the lower bound of the test ratio and \(r_u > r_\ell + 2\) is the upper bound. The algorithm is based on bisection.

If the algorithm succeeds, the method produces a step \(\widetilde{h}\) such that:

\[\widetilde{h} \in \left[(r_\ell - 1)^{\frac{1}{d + p}}, (r_u + 1)^{\frac{1}{d + p}}\right] \left(\frac{\epsilon_f}{\left|\overline{b}_{d + p} f^{(d + p)}(x)\right|}\right)^{\frac{1}{d + p}}\]

where:

\[\overline{b}_{d + p} = \frac{d! (1 - \alpha^p) b_{d + p}}{(d + p)!}.\]

Parameters:

functionGeneralFiniteDifference

The function to differentiate.

xfloat

The point where the derivative is to be evaluated.

differentiation_orderint

The order of differentiation.

For example differentiation_order = 1 is the first derivative.

formula_accuracyint

The order of precision of the formula. For the central F.D. formula, then the formula accuracy is necessarily even. If required, increase the formula accuracy by 1 unit.

absolute_precisionfloat, > 0, optional

The absolute precision of evaluation of f. If the function value is close to zero (e.g. for the sin function at x = np.pi where f(x) is close to 1.0e-32), then the absolute precision cannot always be computed from the relative precision.

minimum_test_ratiofloat, > 1

The minimum value of the test ratio.

maximum_test_ratiofloat, > minimum_test_ratio

The maximum value of the test ratio.

alpha_parameterfloat, > 0, != 1

The parameter alpha used in the test ratio

step_factorfloat, > 1

The multiplier of the step This is used to update the step in the search algorithm

argslist

A list of optional arguments that the function takes as inputs. By default, there is no extra argument and calling sequence of the function must be y = function(x). If there are extra arguments, then the calling sequence of the function must be y = function(x, arg1, arg2, ...) where arg1, arg2, ..., are the items in the args list.

verbosebool, optional

Set to True to print intermediate messages.

Methods

compute_derivative(step)	Compute an approximate value of f'(x) using central finite difference.
compute_test_ratio(step)	Compute the test ratio
find_step([initial_step, iteration_maximum, ...])	Compute an approximate optimum step
get_a_parameter()	Return the A parameter
get_absolute_precision()	Return the absolute precision of the function evaluation
get_alpha_parameter()	Return the step multiplier
get_number_of_function_evaluations()	Returns the number of function evaluations.
get_ratio_min_max()	Return the minimum and maximum of the test ratio
get_step_factor()	Return the step multiplier
get_step_history()	Return the history of steps during the bissection search.

Returns:

None.

See also

FirstDerivativeForward, GeneralFiniteDifference

References

• Shi, H. J. M., Xie, Y., Xuan, M. Q., & Nocedal, J. (2022). Adaptive finite-difference interval estimation for noisy derivative-free optimization. SIAM Journal on Scientific Computing, 44 (4), A2302-A2321.

Examples

Compute the step of a badly scaled function.

>>> import numericalderivative as nd
>>>
>>> def scaled_exp(x):
>>>     alpha = 1.e6
>>>     return np.exp(-x / alpha)
>>>
>>> x = 1.0e-2
>>> differentiation_order = 1  # First derivative
>>> formula_accuracy = 2  # Order 2
>>> formula = nd.GeneralFiniteDifference(
>>>     scaled_exp,
>>>     x,
>>>     differentiation_order,
>>>     formula_accuracy,
>>>     direction="central",  # Central formula
>>> )
>>> algorithm = nd.ShiXieXuanNocedalGeneral(formula)
>>> h_optimal, number_of_iterations = algorithm.find_step()
>>> f_prime_approx = algorithm.compute_derivative(h_optimal)

Set the initial step.

>>> initial_step = 1.0e8
>>> h_optimal, number_of_iterations = algorithm.find_step(initial_step)

__init__(general_finite_difference, absolute_precision=1e-15, minimum_test_ratio=1.5, maximum_test_ratio=6.0, alpha_parameter=2.0, step_factor=4.0, verbose=False)

Methods

__init__(general_finite_difference[, ...])
compute_derivative(step)	Compute an approximate value of f'(x) using central finite difference.
compute_test_ratio(step)	Compute the test ratio
find_step([initial_step, iteration_maximum, ...])	Compute an approximate optimum step
get_a_parameter()	Return the A parameter
get_absolute_precision()	Return the absolute precision of the function evaluation
get_alpha_parameter()	Return the step multiplier
get_number_of_function_evaluations()	Returns the number of function evaluations.
get_ratio_min_max()	Return the minimum and maximum of the test ratio
get_step_factor()	Return the step multiplier
get_step_history()	Return the history of steps during the bissection search.

compute_derivative(step)

Compute an approximate value of f'(x) using central finite difference.

Parameters:

stepfloat, > 0

The step size.

Returns:

derivative_approxfloat

The approximation of the d-th derivative of f at point x.

compute_test_ratio(step)

Compute the test ratio

Parameters:

stepfloat, > 0

The finite difference step

alpha_parameterfloat

The alpha parameter

Returns:

test_ratiofloat, > 0

The test ratio

find_step(initial_step=None, iteration_maximum=53, logscale=True)

Compute an approximate optimum step

If it is not provided by the user, the default initial step is based on the hypothesis that the higher order derivative \(f^{(d + p)}(x)\) is equal to 1 and is computed from compute_step(). This initial guess is not always accurate and can lead to failure of the algorithm.

Parameters:

initial_stepfloat, > 0

The initial step in the algorithm.

iteration_maximumint, optional

The number of number_of_iterations.

logscalebool, optional

Set to True to use a logarithmic scale when updating the step k during the search. Set to False to use a linear scale when updating the step k during the search.

Returns:

estim_stepfloat

A step size which is near to optimal.

number_of_iterationsint

The number of iterations required to reach that optimum.

get_a_parameter()

Return the A parameter

Returns:

a_parameterfloat

The A parameter

get_absolute_precision()

Return the absolute precision of the function evaluation

Returns:

absolute_precisionfloat

The absolute precision of evaluation of f.

get_alpha_parameter()

Return the step multiplier

This is used to update the step at each step of the search algorithm

Returns:

alpha_parameterfloat

The parameter involved in the test ratio

get_number_of_function_evaluations()

Returns the number of function evaluations.

Returns:

number_of_function_evaluationsint

The number of function evaluations.

get_ratio_min_max()

Return the minimum and maximum of the test ratio

Returns:

minimum_test_ratiofloat, > 0

The lower bound of the test ratio.

maximum_test_ratiofloat, > 0

The upper bound of the test ratio.

get_step_factor()

Return the step multiplier

This is used to update the step at each step of the search algorithm

Returns:

step_factorfloat

The multiplier of the step

get_step_history()

Return the history of steps during the bissection search.

Returns:

step_historylist(float)

The list of steps k during intermediate iterations of the bissection search. This is updated by find_step().