|
|
|
|
|
Nonlinear ProgrammingIn 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. 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 -
-
Methods for solving the problem 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. Several methods are available for solving nonconvex problems. One approach is to use 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 A simple problem can be defined by the constraints - x1 ≥ 0
- x2 ≥ 0
- x12 + x22 ≥ 1
- x12 + x22 ≤ 2
with an objective function to be maximized - f(x) = x1 + x2
where x = (x1, x2) Another simple problem can be defined by the constraints - x12 − x22 + x32 ≤ 2
- x12 + x22 + x32 ≤ 10
with an objective function to be maximized - f(x) = x1x2 + x2x3
where x = (x1, x2, x3) Related topics References Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0387987932. Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0471786101. External links
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|