Finite-Difference Approximations of Derivatives

The NLP Procedure

Finite-Difference Approximations of Derivatives

The FD= and FDHESSIAN= options specify the use of finite difference approximations of the derivatives. The FD= option specifies that all derivatives are approximated using function evaluations, and the FDHESSIAN= option specifies that second-order derivatives are approximated using gradient evalutions.

Computing derivatives by finite-difference approximations can be very time consuming, especially for second-order derivatives based only on values of the objective function (FD= option). If analytical derivatives are difficult to obtain (for example, if a function is computed by an iterative process), you might consider one of the optimization techniques that uses first-order derivatives only (TECH=QUANEW, TECH=DBLDOG, or TECH=CONGRA).

Forward Difference Approximations

The forward-difference derivative approximations consume less computer time but are usually not as precise as those using central-difference formulas.

First-order derivatives: n additional function calls are needed:
$g_i = {\partial f \over \partial x_i} = {f(x + h_ie_i) - f(x) \over h_i}$
Second-order derivatives based on function calls only (Dennis and Schnabel 1983, p. 80, 104): for dense Hessian, n+n²/2 additional function calls are needed:
${\partial^2 f \over \partial x_i \partial x_j} = {f(x+h_ie_i+h_je_j) - f(x+h_ie_i) - f(x+h_je_j) + f(x) \over h_i h_j}$
Second-order derivatives based on gradient calls (Dennis and Schnabel, 1983, p. 103): n additional gradient calls are needed:
${\partial^2 f \over \partial x_i \partial x_j} = {g_i(x + h_je_j) - g_i(x) \over 2h_j} + {g_j(x + h_ie_i) - g_j(x) \over 2h_i}$

Central Difference Approximations

First-order derivatives: 2n additional function calls are needed:
$g_i = {\partial f \over \partial x_i} = {f(x + h_ie_i) - f(x - h_ie_i) \over 2h_i}$
Second-order derivatives based on function calls only (Abramowitz and Stegun 1972, p. 884): for dense Hessian, 2n+4n²/2 additional function calls are needed:
${\partial^2 f \over \partial x^2_i} & = & {-f(x + 2h_ie_i) + 16f(x + h_ie_i) - ... ...- f(x+h_ie_i-h_je_j) - f(x-h_ie_i+h_je_j) + f(x-h_ie_i-h_je_j) \over 4h_ih_j}$
Second-order derivatives based on gradient: 2n additional gradient calls are needed:
${\partial^2 f \over \partial x_i \partial x_j} = {g_i(x + h_je_j) - g_i(x - h_je_j) \over 4h_j} + {g_j(x + h_ie_i) - g_j(x - h_ie_i) \over 4h_i}$

The FDIGITS= and CDIGITS= options can be used for specifying the number of accurate digits in the evaluation of objective function and nonlinear constraints. These specifications are helpful in determining an appropriate interval size h to be used in the finite-difference formulas.

The FDINT= option specifies whether the finite difference intervals h should be computed using an algorithm of Gill, Murray, Saunders, and Wright (1983) or based only on the information of the FDIGITS= and CDIGITS= options. For FDINT=OBJ, the interval h is based on the behavior of the objective function; for FDINT=CON, the interval h is based on the behavior of the nonlinear constraints functions; and for FDINT=ALL, the interval h is based on both, the behavior of the objective function and the nonlinear constraints functions. Note that the algorithm of Gill, Murray, Saunders, and Wright (1983) to compute the finite difference intervals h_j can be very expensive in the number of function calls. If the FDINT= option is specified, it is currently performed twice, the first time before the optimization process starts and the second time after the optimization terminates.

If FDINT= is not specified, the step sizes h_j, j = 1, ... ,n, are defined as follows:

for the forward-difference approximation of first-order derivatives using function calls and second-order derivatives using gradient calls: $h_j = \sqrt[2]{\eta_j} (1. + | x_j|)$ ,
for the forward-difference approximation of second-order derivatives that use only function calls and all central-difference formulas: $h_j = \sqrt[3]{\eta_j} (1. + | x_j|)$ .

where $\eta$ is defined using the FDIGITS= option:

If the number of accurate digits is specified with FDIGITS=r, $\eta$ is set to 10^-r.
If FDIGITS= is not specified, $\eta$ is set to the machine precision $\epsilon$ .

For FDINT=OBJ and FDINT=ALL, the FDIGITS= specification is used in computing the forward and central finite-difference intervals.

If the problem has nonlinear constraints and the FD[=] option is specified, the first-order formulas are used to compute finite difference approximations of the Jacobian matrix JC(x). You can use the CDIGITS= option to specify the number of accurate digits in the constraint evaluations to define the step sizes h_j, j = 1, ... ,n. For FDINT=CON and FDINT=ALL, the CDIGITS= specification is used in computing the forward and central finite-difference intervals.

Note: If you are not able to specify analytic derivatives and the finite-difference approximations provided by PROC NLP are not good enough to solve your problem, you may program better finite-difference approximations using the GRADIENT, JACOBIAN, CRPJAC, or HESSIAN statement and the program statements.

Chapter Contents
Previous
Next
Top