Discontinuous and Non-Smooth Functions

Microsoft Excel provides a very rich formula language, including many functions that are discontinuous or non-smooth. Some models can only be expressed with the aid of these functions; in other cases, you have a degree of choice in how you model the real-world problem, and which functions you use. Even when you have a "full arsenal" of Solver engines available, as you do with Frontline's enhanced Solvers, you will get better results if you try to use the most "Solver-friendly" functions in your model.

Where the graph of a continuous function is an unbroken line or curve, the graph of a discontinuous function contains one or more "breaks." The most common example is the IF function. For example:

IF(A1>10,B1,2*B1)

is discontinuous around A1=10 because its value "jumps" from whatever value B1 has to twice that value. A nonlinear solver relies on (partial) derivative values to guide it towards a feasible and optimal solution; since it is unable to compute the derivatives of a function at points where that function is discontinuous, it has trouble determining how to proceed. In practice, the nonlinear GRG Solver used in Excel can sometimes deal with discontinuities which are "incidental" to the problem, but as a general statement, the nonlinear Solver cannot be expected to find optimal solutions to such problems. However, the Evolutionary Solver included in Frontline's enhanced Solver products can make progress on these problems.

If the graph of the function's derivative also contains no breaks, then the original function is called a smooth function. An example of a continuous function that is not smooth is ABS(C1) -- its graph is an unbroken "V" shape, but the graph of its derivative contains a break, jumping from -1 to +1 at C1=0. The nonlinear GRG Solver also makes use of second derivatives (in multiple dimensions, the Hessian) of the problem functions to make faster progress, and to test whether it has found the optimal solution; it sometimes has trouble with functions such as ABS(C1).

Here is a short list of common discontinuous functions in Excel:

• IF
• CHOOSE
• LOOKUP, HLOOKUP, VLOOKUP
• COUNT

Here is a short list of common non-smooth functions in Excel.

• ABS
• MIN, MAX
• INT, ROUND
• CEILING, FLOOR

Formulas involving relations such as <=, = and >= (on the worksheet, not in the Constraints list box) and logical functions such as AND, OR and NOT are discontinuous at their points of transition from FALSE to TRUE values. Functions such as SUMIF and the database functions are discontinuous if the criterion or conditional argument depends on the decision variables. If you aren't sure about a particular function, try graphing it (by hand or in Microsoft Excel) over the expected range of the variables; this will usually reveal whether the function is discontinuous or non-smooth.

As described above, discontinuous functions cause considerable difficulty, and non-smooth functions cause some difficulty for the nonlinear GRG Solver. If your optimization problem contains discontinuous or non-smooth functions, your simplest course of action is to use the Evolutionary Solver to find a "good" solution. Of course, you'll have to give up any guarantees of finding an optimal solution, and it is likely to take considerably more computing time to find a solution. However, this is not your only alternative. For example, many common uses of IF functions, relations and logical functions can be modeled with 0-1 integer variables and associated constraints. You can then use the nonlinear GRG Solver, or even the Simplex Solver, in combination with the Branch & Bound method, to find the true optimal solution to your problem. These ideas are explored further in the Premium Solver User's Guide.

Copyright © 1999 Frontline Systems Inc.
Last modified: June 24, 2004.