Innovative Education
Reversing Tradition
Nonlinear optimization deserves more emphasis
By Thomas A. Grossman
Virtually all ORMS degree programs and survey textbooks teach linear optimization before nonlinear optimization. This traditional order is so well established that it sometimes seems that nature herself decreed it. We argue that this order is often inappropriate. The choice of order depends on the audience being taught. There are two main audiences for ORMS courses: 1. students in technical programs whose focus is the underlying technology of ORMS, and 2. students in business programs whose focus is the use of ORMS.
The traditional approach is to focus on linear optimization and teach nonlinear optimization as an unpleasant generalization of the linear case. The traditional order — linear optimization before nonlinear optimization — is indeed the right way to teach from a technical perspective. However, this order is flawed from an end user's perspective.
We propose to reverse the traditional order for business students and other end-user modelers. We teach linear optimization as an advanced special case of general-purpose nonlinear optimization. From the end user's perspective, nonlinear optimization is conceptually simpler and easier to understand, and hence should be taught before linear optimization.
When it comes to solving a specific model, nonlinear optimization works more often than linear, but gives weak results. The special case of linear optimization requires extra effort to make work, but provides strong results that can justify the effort.
Honoring Tradition
Our traditional approach is not unwise. Let's review the manifold advantages of linear over nonlinear optimization. Linear optimization has attractive properties:
- easier mathematics,
- nice algorithm termination,
- global optimality guaranteed or your money back,
- superior software (speed, scale, reliability, choice),
- the elegance of shadow prices and reduced costs.
- messier mathematics,
- it is not clear when to terminate the algorithm,
- global optimality is tricky at best,
- software selection is limited,
- an unsatisfactory, inelegant aesthetic.
And teach it first we do. ORMS master's programs seem to require a course in linear optimization, but may or may not require a course in nonlinear optimization. ORMS professionals seem to learn linear optimization first and nonlinear optimization second, if they learn it at all.
All survey ORMS textbooks have one or more lengthy chapters on linear optimization. This is typically followed by one grudging chapter on nonlinear optimization.
There is broad agreement that linear optimization comes first, and nonlinear optimization comes second. Nonlinear optimization follows linear optimization as night follows day. This must surely be the natural order of things.
An Unnatural (?) Proposition
Alas, we disagree with this cozy consensus. We are resolved that:
Nonlinear optimization is conceptually prerequisite to linear optimization, for business students and other end-user modelers.This is a significant departure from current practice. This is completely opposite of the way most ORMS professionals learned optimization.
Conceptualizing Optimization
Let us think about conceptual explanations of optimization. What does an optimization algorithm do? It is important for end-user modelers to have some intuition of how optimization software works.
A true understanding of optimization can be acquired only through study of optimization algorithms and associated mathematical theory. Because business students will never study these technical issues, they can acquire only a conceptual understanding. Their understanding is necessarily at the level of analogies and intuition. Our job as teachers is to help students arrive at their own mental models of how optimization works. We don't necessarily have to teach them our own more sophisticated mental models.
We need to ask an important question. How can we best give students an intuitive sense of optimization? We believe that student intuition is best acquired by examining the general case of nonlinear optimization and then considering the special case of linear optimization.
Nonlinear Optimization Concepts
We can explain the concepts of nonlinear optimization by sketching a simple graph with objective on the y-axis and decision variable on the x-axis. Students have seen thousands of simple graphs of y vs. x and are able to understand the basic picture easily. Figure 1 shows a general case where we call the decision variable price and the objective profit.
Figure 1: Sketch for fundamental concepts of nonlinear optimization
Everyone has hiked up a slope to reach the top of a hill. (ORMS professionals would call this a gradient search.) Important concepts such as optimality, step size and search direction are easy to understand by use of the graph and simple analogies to hill-climbing. The essential economic concept of diminishing marginal returns near the optimum (also known as the first order necessary conditions) is clear.
The concept of a constraint is easily communicated by analogy with a cliff barring further progress. The concept of feasibility is easily introduced as obedience to constraints. The possibility of fog preventing the sight of an even higher peak leads naturally to the concept of multiple local optima.
It is easy for students to get a sense of the mechanics of nonlinear search. Given a model — ideally a model of their own creation — they can easily perform a search by hand (or they can automate this search with the Data Table tool in Excel) and create a simple graph of the objective function vs. a decision variable. This gives them a solid connection between our theoretical sketch and their actual model.
From this conceptual foundation, it is straightforward to introduce a second decision variable or dimension. The two-dimensional case can be sketched with the x- and y-axes being decision variables and the z-axis the objective function. We make an analogy with climbing a real hill on a foggy day, where you can see the ground at your feet but nothing more. Students can do a two-dimensional search in their own model by hand, or they can automate it using a two-way data table. Excel has excellent graphing capabilities for students to draw the "hill" of their model to visualize what an objective function is.
The general case of nonlinear optimization admits a simple, intuitive conceptualization of optimization as hill-climbing and an optimization algorithm as a clever way to navigate to the top of a hill.<
Traditional Explanation of Concepts
Contrast this to the traditional conceptualization of linear optimization. The case with one decision variable seems never to appear in textbooks. Instead, a more complex graphical explanation is used. You can find this picture in almost any survey ORMS textbook; I won't repeat it here. The x-axis is decision variable 1, the y-axis is decision variable 2, and the constraints are graphed as lines.
This graph is an efficient way to represent a complex set of concepts. However, it is an ineffective vehicle for solidly establishing the many individual concepts of linear optimization. Efficiency is great when working with the minority of technically astute students in a typical business school classroom, but when working with regular folk, effectiveness is more important.
This graph is complex and hard to understand. Because it introduces a new structure with two independent variables (decisions on the x- and y-axis) but no dependent variable, it does not leverage students' prior exposure to graphs, which are usually shown with dependent and independent variables.
The graph is not framed in terms of the objective function, which students can likely understand. Instead, the concepts are framed in terms of the simplex, which is the intersection of the constraints. This means that students must understand the meaning of the constraints in terms of this graph.
Given that many students cannot graph a straight line given its equation (try this with your business students), the connection between the constraint in the model and the line on the graph is a conceptual leap that many students struggle to make. Worse, when a model is formulated in a spreadsheet rather than in algebra, the equation of the line is implicit rather than explicit. The connection between the constraint line on the graph and a pair of cells in a spreadsheet is tenuous at best.
Worse yet, to use the simplex requires comfort with the intersection of the constraint lines. Given that many of the students who are able to graph a line given its equation can't compute the intersection of two lines (try this with your business students if you doubt it), we face an additional hurdle to real understanding.
The objective is represented not as a slope, but rather as an isoquant, a line of constant objective function value. Isoquants are a subtle and difficult concept. They must be used with caution.
Many people encounter isoquants in the form of topographic maps used for land-use planning or hiking. A line on the map represents a constant elevation. I once observed a gifted instructor named Wallace Mann teach the basics of topographic maps in the Outdoor Skills course at Stanford. He provided a three-dimensional physical model of the terrain and the corresponding isoquant map. Even with an observable physical model, the students struggled to relate the isoquants to the overlying function. And these were undergraduates at an elite private university. Isoquants are a difficult concept requiring thought and reflection. They cannot be introduced on the fly.
Optimization is explained by laying a straight-edge parallel to the isoquants and sliding it perpendicular to the isoquants until the optimum solution is achieved at the edge of the feasible region.
Whew! This is a tough explanation to understand. It requires a series of conceptual leaps to get to the key optimization insights. Having used this graph for years, I am skeptical how much the bulk of the class really takes away from this explanation. Although the students might be able to regurgitate the mechanics on an exam or homework, it is unlikely that they genuinely understand the important concepts those mechanics are meant to teach. Those students with prior exposure to isoquants, who know how an equation relates to a graph, and with good visualization skills probably learn a lot. The bulk of the class probably takes away very little of value.
Linear optimization is a big conceptual leap! In general, our job as instructors is to decompose big leaps into a series of small steps. We can do this by treating linear optimization as a special case of (conceptually simple) non-linear optimization.
Special Case
When teaching linear optimization, we can build on student intuition developed in our prior exploration of nonlinear optimization.
The one-dimensional nonlinear optimization graph is easily adapted to the special case of linearity by making the objective function a line (Figure 2). The objective function heads off towards infinity. The role of a constraint — here, a price value that cannot be exceeded — is instantly clear. It is apparent to students with a moment's reflection that the optimum is always at a constraint. This easily establishes one of the key ideas for interpreting linear optimization results: the search for insight starts at the binding constraints.
Figure 2: Sketch for fundamental concepts of linear optimization
The transition to two dimensions is much easier than in the traditional explanation because we have built a solid conceptual foundation. Rather than require students to make an intellectual leap, they can take a series of small steps. The one-dimensional graph is a stepping-stone to a two-dimensional graph. The one-dimensional hill (with a straight slope) simply becomes a plane. Students have already seen this one- to two-dimensional transition for nonlinear optimization, so this story is easy for them to understand.
The spreadsheet graphing capabilities can be used to create a graph showing the planar objective function. The key concept of linear optimization — the optimum is driven by the constraints — is immediately clear. It is not necessary to introduce the concept of isoquants. (If tradition requires the use of isoquants, the graph simplifies the definition of isoquants.) But it is unlikely that the benefit offsets the cost.)
Benefits of Nonlinear Optimization
Nonlinear optimization has four benefits to the business school management science course. First, nonlinear optimization is useful by itself, because students can use it without the added complexity of linearity. Second, nonlinear optimization is a great vehicle for delivering fundamental optimization concepts. Third, nonlinear optimization is a useful stepping-stone to the more powerful (and more difficult) techniques of linear optimization. Fourth, nonlinear optimization provides strong integration opportunities with other business school courses.
Nonlinear optimization is a useful addition to the students' analytical toolkit. We teach students a set of analytical tools (explore a model, perform sensitivity analysis, ask what-if questions, etc.). Optimization is one additional tool that should sometimes be applied after they have done a basic analysis. Nonlinear programming is particularly valuable because it can be applied to more models than linear. (Like linear optimization, there are models the GRG algorithm in the Excel Solver cannot handle.) The results must be interpreted carefully, because there are no guarantees of optimality or convergence. However, the nonlinear optimization solution cannot but help to improve a user's understanding of a descriptive model. To reduce any tendency to take Solver output as gospel truth, it is essential to teach a general analytical approach (outside the scope of this paper) that provides many alternative decision variable values prior to optimization.
Nonlinear optimization is a great vehicle for delivering fundamental optimization concepts. We believe that understanding these fundamental concepts is essential to extracting insight from optimization. There is a tendency to rush these basic concepts, which are trivial to us but sophisticated to students. With the natural hill-climbing analogy, students easily internalize the basic concepts of optimization.
Nonlinear optimization is a stepping-stone to linear optimization. As discussed in the previous section, the explanation of nonlinear optimization is relatively simple. This explanation can be extended to the special situation of linear constraints and objective function. The result is probably better student understanding with less effort by the instructor.
Nonlinear optimization is an excellent vehicle for integration with other business school courses, including finance, marketing and microeconomics. Portfolio theory in finance is based on a nonlinear optimization that minimizes (quadratic) variance subject to a linear budget constraint. This is a powerful connection to a vital business school course, and can help students master challenging finance concepts while also learning important ORMS concepts.
Next to finance, marketing is probably the most important business school course. Pricing is an important marketing decision. Given a demand curve, pricing can be thought of as a nonlinear optimization. As revenue management concepts from the travel and hospitality industry continue to migrate to the mainstream of management, simple pricing optimizations can position the ORMS course at the cutting edge of marketing.
Microeconomics is essentially a series of high-level nonlinear optimization models. Our ability to solidly establish the concepts of nonlinear optimization is a valuable connection to this course. We can complement the economics class by delivering key economic concepts such as diminishing marginal returns, the optimality of zero marginal returns, and the computation of a firm's demand curve.
Turn Tradition on Its Head
Fundamental pedagogical decisions need to be adapted for each set of students. We should order material to build students' skills. The traditional order of linear optimization before nonlinear optimization is appropriate for technical students. For business students, we should reverse the traditional order. For them, nonlinear optimization is conceptually natural, and linear optimization is a tricky special case.
We should teach nonlinear optimization to business students because:
- Nonlinear optimization is an excellent vehicle for students to grasp fundamental optimization concepts.
- Nonlinear optimization provides conceptual linkages to other business school courses.
- Nonlinear optimization provides content linkages to other business school courses.
- Nonlinear optimization is a general-purpose tool, whereas linear optimization is fragile and special-purpose. Business students are generalists, who need general-purpose tools; efficiency is less important to them.
- Nonlinear optimization is easier for beginner modelers like business students. Advanced modeling skills such as linear formulation are necessary to harness the power of linear optimization.
- Nonlinear optimization provides a valuable stepping stone that simplifies the more difficult concepts of linear optimization.
Thomas Grossman (grossman@ucalgary.ca) of the University of Calgary is president of INFORM-ED (http://education.forum.informs.org/). His consulting experience includes designing, building and deploying revenue optimization systems, supply chain management, and development of in-house analytical groups. His current research includes spreadsheet analytics and call center management.
OR/MS Today copyright © 2001 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Street, Suite 220, Marietta, GA 30060, USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2001 by Lionheart Publishing, Inc. All rights reserved.