
The principal abstraction of the linear programming model is
that all functions are linear. This leads to a number of powerful
results that greatly facilitate our ability to find solutions.
The first is that all local optima are global optima; the second
is that if the optimal value of the objective function is finite,
at least one of the extreme points in the set of feasible solutions
will be an optimum. Furthermore, starting at any extreme
point in the feasible region, it is possible to reach an optimal
extreme point in a finite number of steps by moving only to
an adjacent extreme point in an improving direction. The
simplex method embodies these ideas and has proven to be extremely
efficient.
Nevertheless, much of the world is nonlinear so it is natural
to ask if it is possible to achieve the same efficiency with
nonlinear models. In many contexts, the elements of a linear
model are really approximations of more complex relationships.
Economies of scale in manufacturing, for example, lead to decreasing
costs, while biological systems commonly exhibit exponential
growth. In the design of a simple hatch cover, the shearing
stress, bending stress and degree of defection are each polynomial
functions of flange thickness and beam height. Similar relationships
abound in engineering design, economics, and distribution systems,
to name a few.
The appeal of nonlinear programming (NLP) is strong because
of the modeling richness it affords. Unfortunately, NLP solvers
have not yet achieved the same level of performance and reliability
associated with LP solvers. For all but the most structured
problems, the solution obtained from an NLP solver may not be
globally optimal. This argues for caution. Before taking any
action, the decision maker should have a full understanding
of the nonlinearities governing the system under study.
