Nonlinear programming Guide, Meaning , Facts, Information and Description

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.

Table of contents

1 Mathematical formulation of the problem 2 Methods for solving the problem 3 Examples 3.1 2-dimensional example 3.2 3-dimensional example 3.3 Least squares minimization 4 Solver Software

Mathematical formulation of the problem

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.

Methods for solving the problem

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 solved 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 algorithm 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₃)

Least squares minimization

In an important class of applications, the function to be minimized is a sum of squares,

Typically, f_i(x) is a residuum, i.e., the difference between some experimental value and a theoretical model, the latter being parametrized by x (where x may be a vector, containing several real parameters).

See the articles Least squares, Gauss-Newton algorithm, Levenberg-Marquardt algorithm.

Solver Software

AMPL - Free to students (GUI available) http://www.ampl.com/

This is an Article on Nonlinear programming. Page Contains Information, Facts Details or Explanation Guide About Nonlinear programming

	Web www.E-paranoids.com