Nonlinear programming

In mathematics, nonlinear programming (NLP) is the process of solving a system of equalities and inequalities over a set of unknown real variables, along with an objective function to be maximized or minimized. The problem can be stated simply as:

  to maximize some variable such as product throughput

or

  to minimize a cost function

where

If the objective function f is linear and the constrained space is a polytope, the problem is a linear programming problem, which may be solved using well known linear programming solutions.

If the objective function is convex in all cost functions (when looking from the "bottom"), the linear programming solutions are also applicable.

Real world problems tend to be "nonconvex", however. Such problems, especially in transportation and manufacturing, often exhibit "economies of scale" and linear programming solutions are not algorithmically stable - they tend to drive to extreme high or low volume solutions. An example of a nonconvex problem is the cost of shipping liquid goods (such as finished petroleum products) by various methods: tanker truck, railcar, or pipeline. Each method will have unique cost curves, some with very high startup costs and relatively flat (but non-convex) cost curves, others with low startup costs but high marginal costs or "stairstep" cost functions. It is the task of operations research to determine the method(s) of transport given specific transport requirements. While this sounds simple, the problem is made much more complex when such factors as make vs. buy, equipment ownership, rental, or leasing, and alternative sources and product substitutions are considered.

Several methods are available for solving such nonconvex problems, including special formulations of linear programming problems. Another method involves the use of branch and bound techniques, where the program is divided into subclasses to be soved with linear approximations that form an lower bound on the overal cost within the subdivision. With subsquent divisions, at some point an actual solution will be obtained whose cost is equal to or lower than the best lower bound obtained for any of the approximate solutions. This solution is optimal, although possibly not unique. The agorithm may also be stopped early, with the assurance that the best solution cannot be more that a certain percentage better than a solution that has been found. This is especially useful for large, difficult problems and problems with uncertain costs.

Examples

2-dimensional example

A simple problem can be defined by the constraints

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

with an objective function to be maximized

f(x) = x₁ + x₂

where x = (x₁, x₂)

3-dimensional example

Another simple problem can be defined by the constraints

x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

with an objective function to be maximized

f(x) = x₁x₂ + x₂x₃

where x = (x₁, x₂, x₃)