العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolNONLINEAR PROGRAMMING
In mathematics, 'nonlinear programming' ('NLP') is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function is nonlinear.
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 concave (maximization problem), or convex (minimization problem) and the constraint set is convex, then general methods from convex optimization can be used.
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 a lower bound on the overall cost within the subdivision. With subsequent 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 than a certain percentage better than a solution that has been found. This is especially useful for large, difficult problems and problems with uncertain costs or values where the uncertainty can be estimated with an appropriate reliability estimation.
The Karush-Kuhn-Tucker (KKT) conditions provide the necessary conditions for a solution to be optimal.
===2-dimensional example===
A simple problem can be defined by the constraints
:''x''1 ≥ 0
:''x''2 ≥ 0
:''x''12 + ''x''22 ≥ 1
:''x''12 + ''x''22 ≤ 2
with an objective function to be maximized
:''f''('x') = ''x''1 + ''x''2
where 'x' = (''x''1, ''x''2).
===3-dimensional example===
Another simple problem can be defined by the constraints
:''x''12 − ''x''22 + ''x''32 ≤ 2
:''x''12 + ''x''22 + ''x''32 ≤ 10
with an objective function to be maximized
:''f''('x') = ''x''1''x''2 + ''x''2''x''3
where 'x' = (''x''1, ''x''2, ''x''3).
★ optimization
★ curve fitting
★ least squares minimization
★ Avriel, Mordecai (2003). ''Nonlinear Programming: Analysis and Methods.'' Dover Publishing. ISBN 0-486-43227-0.
★ Bazaraa, Mokhtar S. and Shetty, C. M. (1979). ''Nonlinear programming. Theory and algorithms.'' John Wiley & Sons. ISBN 0-471-78610-1.
★ Nocedal, Jorge and Wright, Stephen J. (1999). ''Numerical Optimization.'' Springer. ISBN 0-387-98793-2.
★ Bertsekas, Dimitri P. (1999). ''Nonlinear Programming: 2nd Edition.'' Athena Scientific. ISBN 1-886529-00-0.
★ Jalaluddin Abdullah, ''Optimization by the Fixed-Point Method'', Version 1.97[1], Vuze/Azureus (under Science and Technology)[2], 2007. (note 1. you need a bittorrent client, preferably Azureus, to download the book 2. the book is free)
★ Nonlinear programming FAQ
★ Mathematical Programming Glossary
★ Nonlinear Programming Survey OR/MS Today
| Contents |
| Mathematical formulation of the problem |
| Methods for solving the problem |
| Examples |
| See also |
| References |
| External links |
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 concave (maximization problem), or convex (minimization problem) and the constraint set is convex, then general methods from convex optimization can be used.
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 a lower bound on the overall cost within the subdivision. With subsequent 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 than a certain percentage better than a solution that has been found. This is especially useful for large, difficult problems and problems with uncertain costs or values where the uncertainty can be estimated with an appropriate reliability estimation.
The Karush-Kuhn-Tucker (KKT) conditions provide the necessary conditions for a solution to be optimal.
Examples
===2-dimensional example===
The intersection of the line with the constrained space represents the solution
A simple problem can be defined by the constraints
:''x''1 ≥ 0
:''x''2 ≥ 0
:''x''12 + ''x''22 ≥ 1
:''x''12 + ''x''22 ≤ 2
with an objective function to be maximized
:''f''('x') = ''x''1 + ''x''2
where 'x' = (''x''1, ''x''2).
===3-dimensional example===
The intersection of the top surface with the constrained space in the center represents the solution
Another simple problem can be defined by the constraints
:''x''12 − ''x''22 + ''x''32 ≤ 2
:''x''12 + ''x''22 + ''x''32 ≤ 10
with an objective function to be maximized
:''f''('x') = ''x''1''x''2 + ''x''2''x''3
where 'x' = (''x''1, ''x''2, ''x''3).
See also
★ optimization
★ curve fitting
★ least squares minimization
References
★ Avriel, Mordecai (2003). ''Nonlinear Programming: Analysis and Methods.'' Dover Publishing. ISBN 0-486-43227-0.
★ Bazaraa, Mokhtar S. and Shetty, C. M. (1979). ''Nonlinear programming. Theory and algorithms.'' John Wiley & Sons. ISBN 0-471-78610-1.
★ Nocedal, Jorge and Wright, Stephen J. (1999). ''Numerical Optimization.'' Springer. ISBN 0-387-98793-2.
★ Bertsekas, Dimitri P. (1999). ''Nonlinear Programming: 2nd Edition.'' Athena Scientific. ISBN 1-886529-00-0.
★ Jalaluddin Abdullah, ''Optimization by the Fixed-Point Method'', Version 1.97[1], Vuze/Azureus (under Science and Technology)[2], 2007. (note 1. you need a bittorrent client, preferably Azureus, to download the book 2. the book is free)
External links
★ Nonlinear programming FAQ
★ Mathematical Programming Glossary
★ Nonlinear Programming Survey OR/MS Today
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
