Edit filter log

'In [[mathematics]], '''nonlinear programming''' ('''NLP''') is the process of solving a system of [[equation|equalities]] and [[inequalities]], collectively termed constraints, over a set of unknown real variables, along with an objective [[function (mathematics)|function]] to be maximized or minimized, where some of the constraints or the objective function are nonlinear. ==Applicability== A typical nonconvex problem is that of optimizing transportation costs by selection from a set of transportion methods, one or more of which exhibit [[Economy of scale|economies of scale]], with various connectivities and capacity constraints. An example would be petroleum product transport given a selection or combination of pipeline, rail tanker, road tanker, river barge, or coastal tankship. Owing to economic batch size the cost functions may have discontinuities in addition to smooth changes. ==Mathematical formulation of the problem== The problem can be stated simply as: :<math>\max_{x \in X}f(x)</math> to maximize some variable such as product throughput or :<math>\min_{x \in X}f(x)</math> to minimize a cost function where :<math>f: R^n \to R</math> :<math>X \subseteq R^n.</math> ==Methods for solving the problem== If the objective function ''f'' is linear and the constrained [[Euclidean space|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 function|concave]] (maximization problem), or [[Convex function|convex]] (minimization problem) and the constraint set is [[Convex set|convex]], then the program is called convex and 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 convex (minimization problem) or 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 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 possible solution is within a tolerance from the best point found; such points are called ε-optimal. Terminating to ε-optimal points is typically necessary to ensure finite termination. 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. Under differentiability and constraint qualifications, the [[Karush-Kuhn-Tucker conditions|Karush-Kuhn-Tucker (KKT) conditions]] provide necessary conditions for a solution to be optimal. Under convexity, these conditions are also sufficient. ==Examples== ===2-dimensional example=== [[Image:Nonlinear programming jaredwf.png|thumb|right|The intersection of the line with the constrained space represents the solution]] A simple problem can be defined by the constraints :''x''₁ &ge; 0 :''x''₂ &ge; 0 :''x''₁² + ''x''₂² &ge; 1 :''x''₁² + ''x''₂² &le; 2 with an objective function to be maximized :''f''('''x''') = ''x''₁ + ''x''₂ where '''x''' = (''x''₁, ''x''₂). [http://apm.servebbs.com/online/view_pass.php?f=2d.apm Solve 2-D Problem]. ===3-dimensional example=== [[Image:Nonlinear programming 3D.svg|thumb|right|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''₁² &minus; ''x''₂² + ''x''₃² &le; 2 :''x''₁² + ''x''₂² + ''x''₃² &le; 10 with an objective function to be maximized :''f''('''x''') = ''x''₁''x''₂ + ''x''₂''x''₃ where '''x''' = (''x''₁, ''x''₂, ''x''₃). [http://apm.servebbs.com/online/view_pass.php?f=3d.apm Solve 3-D Problem]. ==See also== * [[Curve fitting]] * [[Least squares]] minimization * [[Linear programming]] * [[nl (format)]] * [[Optimization (mathematics)]] * [[List of optimization software]] ==References== {{Unreferenced|date=June 2008}} ==Further reading== * 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. * Bertsekas, Dimitri P. (1999). ''Nonlinear Programming: 2nd Edition.'' Athena Scientific. ISBN 1-886529-00-0. * J. F. Bonnans, [http://www-roc.inria.fr/who/Jean-Charles.Gilbert J. Ch. Gilbert], C. Lemaréchal, C. Sagastizábal (2006), ''[http://www.springer.com/mathematics/applications/book/978-3-540-35445-1 Numerical Optimization - Theoretical and Numerical Aspects]'', 2nd edition, Springer. ISBN 978-3-540-35445-1. * {{cite book|last1=Luenberger|first1=David G.|authorlink1=David G. Luenberger|last2=Ye|first2=Yinyu|authorlink2=Yinyu Ye|title=Linear and nonlinear programming|edition=Third|series=International Series in Operations Research & Management Science|volume=116|publisher=Springer|location=New York|year=2008|pages=xiv+546|isbn=978-0-387-74502-2}} {{MR|2423726}} * Nocedal, Jorge and Wright, Stephen J. (1999). ''Numerical Optimization.'' Springer. ISBN 0-387-98793-2. ==External links== *[http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html Nonlinear programming FAQ] *[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary] *[http://www.lionhrtpub.com/orms/surveys/nlp/nlp.html Nonlinear Programming Survey OR/MS Today] *[http://apmonitor.com/wiki/index.php/Main/Background Overview of Optimization in Industry] ==References== 'Optimization: Insights and Applications', [[Jan Brinkhuis]] and Vladimir Tikhomirov: 2005, Princeton University Press {{DEFAULTSORT:Nonlinear Programming}} [[Category:Software engineering terminology]] [[Category:Mathematical optimization]] [[ca:Programació no lineal]] [[cs:Nelineární programování]] [[es:Programación no lineal]] [[fr:Programmation non-linéaire]] [[hi:अरैखिक प्रोग्रामन]] [[it:Programmazione non-lineare]] [[he:תכנון לא-לינארי]] [[ja:非線形計画法]] [[pl:Programowanie nieliniowe]] [[sl:Nelinearno programiranje]] [[sv:Icke-linjär optimering]] [[uk:Нелінійне програмування]] [[zh:非线性规划]]'