Automatic Differentiation :: SAS/OR(R) 12.1 User's Guide: Mathematical Programming

Automatic Differentiation

Forward-Difference Approximations
Central-Difference Approximations

PROC OPTMODEL automatically generates statements to evaluate the derivatives for most objective expressions and nonlinear constraints. PROC OPTMODEL generates analytic derivatives for objective and constraint expressions written in terms of the procedure’s mathematical operators and most standard SAS library functions.

Note: Some functions, such as ABS, FLOOR, and SIGN, and some operators, such as IF-THEN, <> (element minimum operator), and >< (element maximum operator), must be used carefully in modeling expressions because functions including such components are not continuously differentiable or even continuous.

Expressions that reference user-defined functions or some SAS library functions might require numerical approximation of derivatives. PROC OPTMODEL uses either forward-difference approximation or central-difference approximation as specified by the FD= option (see the section PROC OPTMODEL Statement).

Note: The numerical gradient approximations are significantly slower than automatically generated derivatives when the number of optimization variables is large.

Forward-Difference Approximations

The FD=FORWARD option requests the use of forward-difference derivative approximations. For a function of variables, the first-order derivatives are approximated by

$g_ i = \frac{\partial f}{\partial x_ i} = \frac{f( x + e_ i h_ i ) - f( x )}{h_ i}$

Notice that up to additional function calls are needed here. The step lengths , $i=1,\ldots ,n$ , are based on the assumed function precision, DIGITS:

$h_ i = 10^{-\emph{DIGITS}/2} (1 + |x_ i|)$

You can use the FDIGITS= option to specify the function precision, DIGITS, for the objective function. For constraints, use the CDIGITS= option.

The second-order derivatives are approximated by using up to extra function calls (Dennis and Schnabel; 1983, pp. 80, 104):

$\displaystyle \frac{\partial ^2 f}{\partial x^2_ i}$	$\displaystyle =$	$\displaystyle \frac{f(x + h_ ie_ i) - 2f(x) + f(x - h_ ie_ i)}{h^2_ i}$
$\displaystyle \frac{\partial ^2 f}{\partial x_ i \partial x_ j}$	$\displaystyle =$	$\displaystyle \frac{f(x+h_ ie_ i+h_ je_ j) - f(x+h_ ie_ i) - f(x+h_ je_ j) + f(x)}{h_ ih_ j}$

Notice that the diagonal of the Hessian uses a central-difference approximation (Abramowitz and Stegun; 1972, p. 884). The step lengths are

$h_ i = 10^{-\emph{DIGITS}/3} (1 + |x_ i|)$

Central-Difference Approximations

The FD=CENTRAL option requests the use of central-difference derivative approximations. Generally, central-difference approximations are more accurate than forward-difference approximations, but they require more function evaluations. For a function of variables, the first-order derivatives are approximated by

$g_ i = \frac{\partial f}{\partial x_ i} = \frac{f( x + e_ i h_ i ) - f( x - e_ i h_ i )}{2 h_ i}$

Notice that up to additional function calls are needed here. The step lengths , $i=1,\ldots , n$ , are based on the assumed function precision, DIGITS:

$h_ i = 10^{-\emph{DIGITS}/3} (1 + |x_ i|)$

You can use the FDIGITS= option to specify the function precision, DIGITS, for the objective function. For constraints, use the CDIGITS= option.

The second-order derivatives are approximated by using up to extra function calls (Abramowitz and Stegun; 1972, p. 884):

$\displaystyle \frac{\partial ^2 f}{\partial x^2_ i}$	$\displaystyle =$	$\displaystyle \frac{-f(x + 2h_ ie_ i) + 16f(x + h_ ie_ i) - 30f(x) + 16f(x - h_ ie_ i) - f(x - 2h_ ie_ i)}{12h^2_ i}$
$\displaystyle \frac{\partial ^2 f}{\partial x_ i \partial x_ j}$	$\displaystyle =$	$\displaystyle \frac{f(x+h_ ie_ i+h_ je_ j) - f(x+h_ ie_ i-h_ je_ j) - f(x-h_ ie_ i+h_ je_ j) + f(x-h_ ie_ i-h_ je_ j)}{4h_ ih_ j} \nonumber$

The step lengths are

$h_ i = 10^{-\emph{DIGITS}/3} (1 + |x_ i|)$