Main Content

Automatic Differentiation Background

What Is Automatic Differentiation?

Automatic differentiation (also known as autodiff, AD, or algorithmic differentiation) is a widely used tool in optimization. The solve function uses automatic differentiation by default in problem-based optimization for general nonlinear objective functions and constraints; see Automatic Differentiation in Optimization Toolbox.

Automatic differentiation is a set of techniques for evaluating derivatives (gradients) numerically. The method uses symbolic rules for differentiation, which are more accurate than finite difference approximations. Unlike a purely symbolic approach, automatic differentiation evaluates expressions numerically early in the computations, rather than carrying out large symbolic computations. In other words, automatic differentiation evaluates derivatives at particular numeric values; it does not construct symbolic expressions for derivatives.

  • Forward mode automatic differentiation evaluates a numerical derivative by performing elementary derivative operations concurrently with the operations of evaluating the function itself. As detailed in the next section, the software performs these computations on a computational graph.

  • Reverse mode automatic differentiation uses an extension of the forward mode computational graph to enable the computation of a gradient by a reverse traversal of the graph. As the software runs the code to compute the function and its derivative, it records operations in a data structure called a trace.

As many researchers have noted (for example, Baydin, Pearlmutter, Radul, and Siskind [1]), for a scalar function of many variables, reverse mode calculates the gradient more efficiently than forward mode. Because an objective function is scalar, solve automatic differentiation uses reverse mode.

Forward Mode

Consider the problem of evaluating this function and its gradient:

f(x)=x1exp(12(x12+x22)).

Automatic differentiation works at particular points. In this case, take x1 = 2, x2 = 1/2.

The following computational graph encodes the calculation of the function f(x).

To compute the gradient of f(x) using forward mode, you compute the same graph in the same direction, but modify the computation based on the elementary rules of differentiation. To further simplify the calculation, you fill in the value of the derivative of each subexpression ui as you go. To compute the entire gradient, you must traverse the graph twice, once for the partial derivative with respect to each independent variable. Each subexpression in the chain rule has a numeric value, so the entire expression has the same sort of evaluation graph as the function itself.

The computation is a repeated application of the chain rule. In this example, the derivative of f with respect to x1 expands to this expression:

dfdx1=du6dx1=u6u1+u6u5u5x1=u6u1+u6u5u5u4u4x1=u6u1+u6u5u5u4u4u3u3x1=u6u1+u6u5u5u4u4u3u3u1u1x1.

Let u˙i represent the derivative of the expression ui with respect to x1. Using the evaluated values of the ui from the function evaluation, you compute the partial derivative of f with respect to x1 as shown in the following figure. Notice that all the values of the u˙i become available as you traverse the graph from top to bottom.

To compute the partial derivative with respect to x2, you traverse a similar computational graph. Therefore, when you compute the gradient of the function, the number of graph traversals is the same as the number of variables. This process can be slow for many applications, when the objective function or nonlinear constraints depend on many variables.

Reverse Mode

Reverse mode uses one forward traversal of a computational graph to set up the trace. Then it computes the entire gradient of the function in one traversal of the graph in the opposite direction. For problems with many variables, this mode is far more efficient.

The theory behind reverse mode is also based on the chain rule, along with associated adjoint variables denoted with an overbar. The adjoint variable for ui is

u¯i=fui.

In terms of the computational graph, each outgoing arrow from a variable contributes to the corresponding adjoint variable by its term in the chain rule. For example, the variable u–1 has outgoing arrows to two variables, u1 and u6. The graph has the associated equation

fu1=fu1u1u1+fu6u6u1=u¯1u1u1+u¯6u6u1.

In this calculation, recalling that u1=u12 and u6 = u5u–1, you obtain

u¯1=u¯12u1+u¯6u5.

During the forward traversal of the graph, the software calculates the intermediate variables ui. During the reverse traversal, starting from the seed value u¯6=ff=1, the reverse mode computation obtains the adjoint values for all variables. Therefore, reverse mode computes the gradient in just one computation, saving a great deal of time compared to forward mode.

The following figure shows the computation of the gradient in reverse mode for the function

f(x)=x1exp(12(x12+x22)).

Again, the computation takes x1 = 2, x2 = 1/2. The reverse mode computation relies on the ui values that are obtained during the computation of the function in the original computational graph. In the right portion of the figure, the computed values of the adjoint variables appear next to the adjoint variable names, using the formulas from the left portion of the figure.

The final gradient values appear as u¯0=fu0=fx2 and u¯1=fu1=fx1.

For more details, see Baydin, Pearlmutter, Radul, and Siskind [1] or the Wikipedia article on automatic differentiation [2].

Automatic Differentiation in Optimization Toolbox

Automatic differentiation (AD) applies to the solve and prob2struct functions under the following conditions:

When AD AppliesAll Constraint Functions SupportedOne or More Constraints Not Supported
Objective Function SupportedAD used for objective and constraintsAD used for objective only
Objective Function Not SupportedAD used for constraints onlyAD not used

When these conditions are not satisfied, solve estimates gradients by finite differences, and prob2struct does not create gradients in its generated function files.

Note

To use automatic derivatives in a problem converted by prob2struct, pass options specifying these derivatives.

options = optimoptions('fmincon','SpecifyObjectiveGradient',true,...
    'SpecifyConstraintGradient',true);
problem.options = options;

Currently, AD works only for first derivatives; it does not apply to second or higher derivatives. So, for example, if you want to use an analytic Hessian to speed your optimization, you cannot use solve directly, and must instead use the approach described in Supply Derivatives in Problem-Based Workflow.

References

[1] Baydin, Atilim Gunes, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. "Automatic Differentiation in Machine Learning: A Survey." The Journal of Machine Learning Research, 18(153), 2018, pp. 1–43. Available at https://arxiv.org/abs/1502.05767.

[2] Automatic differentiation. Wikipedia. Available at https://en.wikipedia.org/wiki/Automatic_differentiation.

See Also

|

Related Topics

External Websites