Linear and Nonlinear Functions

Functions of the Variables

The objective (target cell) in a Solver problem is a calculated value that depends on the decision variable (changing) cells; the job of the Solver is to find some combination of values for the decision variables which maximizes or minimizes the objective function. During the optimization process, only the decision variable cells are changed; all other "input" cells are held constant. If you analyze the chain of formulas which calculates the objective function value, you will find that parts of those formulas (those which refer to non-decision variable cells) are unchanging in value and could be replaced by a numeric constant for the purposes of the optimization.

If you follow our suggestion and use only constant values on the right hand sides of constraints, then the same observation applies to the left hand sides of the constraints: Parts of the constraint formulas (those which refer to non-decision variable cells) are unchanging in value, and only the parts dependent on the decision variables "count" during the optimization.

When we talk about "functions" of the decision variables, we are focusing on the way the objective (target cell), or the left hand sides of the constraints change when the Solver changes the decision variables. Portions of formulas which don't depend on the decision variables always contribute the same, constant value to the calculation of the objective and constraints.

Linear Functions

The mathematical form of the relationship between the objective function and constraint cells and the decision variables has important implications for the difficulty of the problem, the Solver "engine" that can be used, and the speed of solution. The simplest and most common case is where the objective function is a linear function of the variables. As the name implies, a linear function has a graph which is a straight line. This means that the objective can be written as a sum of terms, where each term consists of one decision variable multiplied by a (positive or negative) constant. Algebraically, we can write:

max (or min) a1 * x1 + a2 * x2 + ... + an * xn

where the ais, which are called the coefficients, stand for constant values and the xis stand for the decision variables. Remember that the ais need only be constant in the optimization problem, i.e. not dependent on any of the decision variables. As an example, suppose that the objective function is B1/B2*C1 +(D1*2+E1)*C2, where only C1 and C2 are decision variables, and the other cells contain constants (or formulas that don't depend on any of the decision variables). This would still be a linear function, where a1 = B1/B2 and a2 = (D1*2+E1) are the coefficients, and x1 = C1 and x2 = C2 are the variables.

Note that the SUMPRODUCT function in Excel and 1-2-3, and the DOTPRODUCT function included with our enhanced solvers compute exactly the algebraic expression shown above. If we were to place the formula B1/B2 in cell A1, and the formula (D1*2+E1) in cell A2, then we could write the example objective function as:

SUMPRODUCT(A1:A2,C1:C2)

This is simple and clear, and is also in proper form for fast problem setup in the enhanced solvers. If the decision variable cells which should participate in the expression are not all contiguous on the spreadsheet, the DOTPRODUCT function can be used instead of SUMPRODUCT.

Nonlinear Functions

A nonlinear function, as its name implies, is any function of the decision variables which is not linear, i.e. which cannot be written in the algebraic form shown above. Examples would be 1/C1, LOG(C1), C1^2 or C1*C2 where both C1 and C2 are decision variables. If the objective function or any of the constraints are nonlinear functions of the variables, then the problem cannot be solved with linear optimization methods.

The nonlinear GRG solver included with the standard spreadsheet Solvers can optimize problems where the objective function and/or the constraints are nonlinear, as long as they are "smooth" or continuous functions of the variables. When graphed, such a function appears as a curved line with no "breaks" or discontinuities (see the discussion of discontinuous and non-smooth functions). More exactly (in mathematical terms), the functions must be twice continuously differentiable.

Conceptually, a nonlinear solver deals with a smooth, curved function by breaking it up into many tiny intervals over which it behaves linearly. (Imagine a curved line broken up into many tiny segments, each of which is approximately a straight line.) The solver does this by computing (approximate) partial derivatives of the problem functions at each iteration, using the latest trial values of the decision variables. This involves recalculating the spreadsheet many times (once for each decision variable) on each solver iteration.

In contrast, a linear function has constant partial derivatives -- the coefficients referred to above -- which can be computed once at the start of the solution process. The need to repeatedly re-evaluate the derivatives of nonlinear functions is the major reason why a nonlinear solver takes so much more time than a linear solver for a given number of decision variables and constraints.

Quadratic Functions

The last two examples above, =C1^2 or =C1*C2, are simple instances of quadratic functions of the variables. A more complex example would be:

2*C1^2+3*C2^2+4*C1*C2+5*C1

A quadratic function is a sum of terms, where each term is a (positive or negative) constant (again called a coefficient) multiplied by a single variable or the product of two variables. The QUADPRODUCT function, included with our enhanced solvers for Microsoft Excel, computes values of exactly this form. If we put the constant 5 in A1, 0 in B1, 2 in A2, 4 in B2, 0 in A3 and 3 in B3, then we could write the above example as:

QUADPRODUCT(C1:C2,A1:B1,A2:B3)

Common uses for quadratic functions are to compute the mean squared error in a curve-fitting application, or the variance or standard deviation of security returns in a portfolio optimization application. Frontline's Quadratic Solver includes special methods for efficiently solving QP problems.

What If You Aren't Sure?

What if you have already created a complex spreadsheet model without using functions like SUMPRODUCT or DOTPRODUCT, and you aren't sure whether your objective function and constraints are linear or nonlinear functions of the variables? A quick way to find out is to try solving the model with the Assume Linear Model box checked in the Solver Options dialog. Although this test is not totally foolproof, it will in most cases return an error message if the problem contains nonlinear functions of the variables. (Our enhanced solvers include a more sophisticated test for linearity than the standard spreadsheet Solvers.)

There is a small chance that a model with discontinuous functions will "fool" the Solver's test for linearity. This usually means that the functions are actually linear over the range of values for the decision variables that the Solver uses in its test. For example, if B1 is a linear function of the decision variables, the formula IF(A1>10,B1,2*B1) will be linear both below and above the critical value of A1=10. If you aren't sure whether you have included any discontinuous functions in formulas which depend on the decision variables, it is a good idea to use your spreadshet program's Edit Find operation to check your model for the common functions listed above.

Assuming that your attempt to solve with the Assume Linear Model box checked yields no error messages, the next step is to look closely at the formulas in your spreadsheet and to try rewriting them using SUMPRODUCT or DOTPRODUCT. Your effort will be rewarded in most cases by a better understanding of your model, as well as a problem suitable for fast problem setup in the enhanced solvers.