Estimates, Derivatives and Search Options

[Dividing Line Image]

In the standard Microsoft Excel Solver, the Estimates, Derivatives and Search options in the Solver Options dialog affect only the standard GRG solver; they are not used by the Simplex method linear solver. The default choices are suitable for the vast majority of problems; although it generally won't hurt to change these options, you should first consider other alternatives such as improved scaling before attempting to fine-tune these options. In some scientific and engineering applications, the alternates to the default choices may improve the solution process.

The following general background information may be helpful in understanding these options: In linear programming problems, the first partial derivatives of the problem functions (the objective and constraints) are constant; these are the coefficients of the LP model. In nonlinear programming problems, the first derivatives of the problem functions may depend on the current values of the decision variables; hence they must be recomputed at each iteration when the values of the variables change. (For more background, consult the topic Linear and Nonlinear Functions.)

GRG Nonlinear Solver

On each major iteration, most nonlinear solvers must compute values for the first partial derivatives of the objective and constraints. The Derivatives option is concerned with how these partial derivatives are computed.

The GRG (Generalized Reduced Gradient) solution process proceeds by first "reducing" the problem to an unconstrained optimization problem, by solving a set of nonlinear equations for certain variables (the "basic" variables) in terms of others (the "nonbasic" variables). Then a search direction (a vector in N-space, where N is the number of nonbasic variables) is chosen along which an improvement in the objective function will be sought. The Search option is concerned with how this search direction is determined.

Once a search direction is chosen, a one-dimensional "line search" is carried out along that direction, varying a step size in an effort to improve the reduced objective. The initial estimates for values of the variables which are being varied has a significant impact on the effectiveness of the search. The Estimates option is concerned with how these estimates are obtained.

Quadratic Solver

Frontline's Quadratic Solver, a component of our enhanced solvers, must compute first partial derivatives for the objective function at certain points. These computations are also controlled by the setting of the Derivatives option. For quadratic programming problems, the Central choice for Derivatives will usually improve accuracy, at the expense of greater solution time.

Estimates

This option determines the approach used to obtain initial estimates of the basic variable values at the outset of each one-dimensional search. The Tangent choice uses linear extrapolation from the line tangent to the reduced objective function. The Quadratic choice extrapolates the minimum (or maximum) of a quadratic fitted to the function at its current point. If the current reduced objective is well modeled by a quadratic, then the Quadratic option can save time by choosing a better initial point, which requires fewer subsequent steps in each line search. If you have no special information about the behavior of this function, the Tangent choice is "slower but surer." Note: the Quadratic choice here has no bearing on quadratic programming problems.

Derivatives

The first partial derivatives of the problem functions are computed through "finite differencing," which involves perturbing the current values of the decision variables, observing how the problem functions change, and performing a "rise over run" calculation. With Forward differencing (the default choice), the point from the previous iteration (where the problem function values are already known) is used in conjunction with the current point. This reduces the recalculation time required for finite differencing, which can account for up to half of the total solution time. Central differencing relies only on the current point and perturbs the decision variables in opposite directions from that point. Although this involves more recalculation time, it may result in a better choice of search direction when the derivatives are rapidly changing, and hence fewer total iterations. Note: For quadratic programming problems, the Central differencing choice yields essentially exact (rather than approximate) derivative values, which can improve solution accuracy and reduce the total number of iterations; however each iteration may take up to twice as long as with Forward differencing.

Search

It would be far too expensive to determine a search direction using the pure form of Newton's method, by computing the Hessian matrix of second partial derivatives of the problem functions. (This would roughly square the number of spreadsheet recalculations required to solve the problem.) Instead, an direction is chosen through an estimation method. The default choice Newton uses a quasi-Newton (or BFGS) method, which maintains an approximation to the Hessian matrix; this requires more storage (an amount proportional to the square of the number of currently binding constraints) but performs very well in practice. The alternative choice Conjugate uses a conjugate gradient method, which does not require storage for the Hessian matrix and still performs well in most cases. The choice you make here is not crucial, since the GRG solver is capable of switching automatically between the quasi-Newton and conjugate gradient methods depending on the available storage.