Return to Index
Operations Research Models and Methods
 
Computation Section
Subunit Functions
 - Differentiate

This page describes the add-in features related to differentiation. Most of the background for this section can be found in Operations Research Models and Methods (Jensen, P.A. and Bard, J.F., John Wiley and Sons, 2003, Chapter 9. Nonlinear Programming Models).

We use the quadratic example below to illustrate because it is easy to check the results analytically.

The figure shows the form for the example. The cubic terms considered on the previous page are excluded. The derivatives are evaluated for the point entered in column B (i.e. (1, 1, 1)).

To select the operations to perform, choose Differentiate from the menu. The figure shows the dialog filled in for the example. The add-in uses standard discrete difference approximations to compute first and second derivatives. A field is provided for the step size. For functions with continuous first and second derivatives, a small step value may be entered. For functions with small irregularities it might be useful to enter a larger step value.

 

For the example, we have chosen the complete analysis. The figure shows the results.

The vector of first partial derivatives of the function is called the Gradient. Normally it is shown as a row vector, but for convenience of presentation, we show it on the table in a column. The matrix of second derivatives is the Hessian matrix. For the quadratic function the Hessian is the same as the Q matrix and does not depend on the decision vector. The derivatives have been evaluated for the point shown in the solution column (B).

The add-in diagonalizes the Hessian matrix using a linear transformation of the variables. This makes it possible to characterize the shape of the function at the point evaluated.An analysis of the function based on the diagonalized matrix is placed to the right of the results. We show the analysis of the example in the figure. A stationary point is a point where all first derivatives are zero. Clearly the current point is not a stationary point.

The diagonalized matrix has all nonnegative values on the main diagonal, indicating that the matrix is positive definite. This implies that the function is convex at the evaluation point. For the quadratic function, the function is everywhere convex.

Row 19 indicates that 27 function evaluations were required for the analysis. This is an important measure of the efficiency of the numerical process.

The table below shows the analysis at three different points. The second order analysis is hidden since it does not change for the quadratic function. The first point is the lower bound. Since the gradient is negative, and none of the variables may be decreased, the solution must be a local maximum. The second point is the stationary point found by setting the gradient to zero. As expected the gradient is nearly 0. The analysis uses the Hessian to determine that the function is convex at this point. It is a strong local minimum point. Since the function is everywhere convex, the point is a global minimum. The analysis can only tell about the function near the point evaluated. The third point is at upper bound. Since the derivative with respect to the second variable is negative, this is not a local minimum.

Application

Differentiation is useful for optimization studies where the goal is to find a point that maximizes or minimizes a nonlinear function. It is used extensively in the Optimize feature of this add-in. For an interior stationary point, the gradient is zero. For a non-stationary point, the gradient indicates a direction of improvement. At the boundaries the optimality conditions for the gradient are more complex, but sometimes indicate whether the solution is or is not a local optimum. The Hessian matrix helps determine whether a stationary point is a local maximum or minimum point.

In a more general context where the Excel model is complex, the analyst may simply be interested in finding the sensitivity of a particular solution value to changes in some of the model parameters. By setting the step size to larger values, perhaps whole units, the gradient and Hessian with respect to the parameters provides information about this sensitivity and how the parameter values might be changed in a what-if analysis.

 

  
Return to Top

tree roots

Operations Research Models and Methods
Internet
by Paul A. Jensen
Copyright 2004 - All rights reserved