|
Contact: Dan Fylstra |
Backgrounder |
In their classic - and still popular - 1983 textbook Numerical Methods for Unconstrained Optimization and Nonlinear Equations, optimization researchers Jack E. Dennis and Robert B. Schnabel described the capabilities and limitations of methods for nonlinear optimization and solution of nonlinear equations. In Section 2.1 -- titled "What is Not Possible" -- they wrote:
"Consider the problem of finding the real roots of each of the following nonlinear equations in one unknown:
- f1(x) = x4 - 12x3 +47x2 - 60x,
- f2(x) = x4 - 12x3 +47x2 - 60x + 24,
- f3(x) = x4 - 12x3 +47x2 - 60x + 24.1.
It would be wonderful if we had a general-purpose computer routine that would tell us: 'The roots of f1(x) are x = 0, 3, 4, and 5; the real roots of f2(x) are x = 1 and x = 0.888; f3(x) has no real roots.' It is unlikely that there will ever be such a routine. In general, the questions of existence and uniqueness ... are beyond the capabilities one can expect of algorithms that solve nonlinear problems."
And today - two decades later - practitioners and even researchers in nonlinear optimization generally accept the idea that solving the above problems - and the closely related problem of finding a 'guaranteed' global optimum to a nonlinear optimization problem - is "not possible."
Yet users of the Premium Solver Platform Version 5.0 do, in fact, have "a general-purpose computer routine" - Frontline's new Interval Global Solver - that will routinely solve the above problems (in a fraction of a second) and countless other problems like them. What was once "not possible" is now just one of many features of a popular desktop software product.
Perhaps even more intriguing is how the new Interval Global Solver achieves this result. Section 8.3 of Cliff T. Ragsdale's best-selling 2000 textbook Spreadsheet Modeling and Decision Analysis: A Practical Introduction to Management Science explains that:
"Unfortunately, with NLP problems we cannot determine easily how much worse a given local optimal solution is than the global optimal solution because there is no general way of obtaining bounds on the optimal objective function values for these problems."
But the new Interval Global Solver does have "a general way" - the Moore-Skelboe Interval Branch and Bound algorithm - of obtaining bounds on the globally optimal solution of any smooth nonlinear optimization problem. Moreover, these bounds can be tightened until the globally optimal solution is isolated to any desired level of accuracy. Clearly, the ground rules of nonlinear and global optimization have changed.
Interval Methods Overcome Limitations of Classical Nonlinear Optimization
Dennis and Schnabel's 1983 declaration, and Ragsdale's 2000 explanation are probably valid if optimization algorithms are limited to evaluating a problem's objective and constraints only for real numbers at specific trial points. But the situation changes if the problem functions can be evaluated over intervals. (An interval such as [1, 2] represents all possible real values between 1 and 2 inclusive.) And in the Premium Solver Platform Version 5.0, virtually any Excel formula can be evaluated over intervals.
The ideas of interval arithmetic have a long history. But the field of interval analysis arose in 1979, when Ramon Moore published his classic book Methods and Applications of Interval Analysis. The essential ideas of the Moore-Skelboe Interval Branch and Bound algorithm, and even key ideas for improving performance such as the Interval Newton method, can be traced to this monograph. But the methods attracted little attention until the 1990s, when researchers such as Arnold Neumaier, Eldon Hansen and R. Baker Kearfott published practical algorithms elaborating on these basic ideas, and the first interval solvers appeared in the form of research codes.
First Software Appears Using Interval Methods
The period 1998-2001 saw the first efforts to develop commercial software based on interval methods. DeliSoft, a venture-funded offshoot of the Finnish research center VTT, launched an Interval Solver Excel add-in (for equation solving but not optimization), but the company ceased operations a couple of years later. Pascal Van Hentenryck developed the Numerica modeling language, with a solver using interval-based domain reduction techniques. Numerica was briefly marketed by ILOG Inc. but later discontinued; some of its methods were embedded in the ILOG Solver and can still be used by sophisticated C++ programmers.
In late 1998, Frontline Systems began investing in development of interval methods for global optimization. A key step in making such interval methods easy to use was to develop the Parser and Interpreter now included in the Premium Solver Platform Version 5.0, which can evaluate virtually any Excel formula over intervals, and compute 'interval gradients' using the methods of automatic differentiation. Frontline's developers also pioneered new methods for accelerating search in the Moore-Skelboe Interval Branch and Bound algorithm, using 'generalized intervals' or linear enclosures. Several papers on Frontline's work have been presented at recent conferences and workshops, and are scheduled for future publication.
Premium Solver Platform V5.0 Makes Interval-Based Optimization Easy to Use
Today, the Premium Solver Platform Version 5.0 is making interval-based optimization methods readily available and very easy to use. Solving a problem with the new Interval Global Solver is as simple as selecting it from a Solver engine drop-down list, and clicking the Solve button. The new Solver works with existing Excel models developed for the standard Solver, Premium Solver and Premium Solver Platform. It can find globally optimal solutions of smooth constrained nonlinear optimization problems, and all real solutions of systems of nonlinear equations, subject only to available computing time and possible roundoff error when real arithmetic is used.
Solutions appear on the user's Excel worksheet, and Solver reports are generated as additional worksheets inserted into the user's workbook. One such new report, the Solutions Report, produces exactly the answers listed by Dennis and Schnabel in 1983 when they wrote, "It would be wonderful if we had a general-purpose computer routine that would tell us: 'The roots of f1(x) are x = 0, 3, 4, and 5; the real roots of f2(x) are x =1 and x = 0.888; f3(x) has no real roots.'" Early users of the Premium Solver Platform Version 5.0 know that Dennis and Schnabel were unduly pessimistic when they wrote "It is unlikely that there will ever be such a routine," but they agree that their newfound ability to easily obtain such answers is "wonderful."