Nonlinear 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 are nonlinear.^{[1]}
Contents
Applicability
A typical nonconvex problem is that of optimising transportation costs by selection from a set of transportion methods, one or more of which exhibit 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:
 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 the program is called convex and general methods from convex optimization can be used in most cases.
If the objective function is a ratio of a concave and a convex function (in the maximization case) and the constraints are convex, then the problem can be transformed to a convex optimization problem using fractional programming techniques.
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 (KKT) conditions provide necessary conditions for a solution to be optimal. Under convexity, these conditions are also sufficient.
Examples
2dimensional example
A simple problem can be defined by the constraints
 x_{1} ≥ 0
 x_{2} ≥ 0
 x_{1}^{2} + x_{2}^{2} ≥ 1
 x_{1}^{2} + x_{2}^{2} ≤ 2
with an objective function to be maximized
 f(x) = x_{1} + x_{2}
where x = (x_{1}, x_{2}). Solve 2D Problem.
3dimensional example
Another simple problem can be defined by the constraints
 x_{1}^{2} − x_{2}^{2} + x_{3}^{2} ≤ 2
 x_{1}^{2} + x_{2}^{2} + x_{3}^{2} ≤ 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}). Solve 3D Problem.
See also
 Curve fitting
 Least squares minimization
 Linear programming
 nl (format)
 Mathematical optimization
 List of optimization software
References
 ^ Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1886529000.
Further reading
 Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0486432270.
 Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0471786101.
 Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1886529000.
 Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: SpringerVerlag. pp. xiv+490. doi:10.1007/9783540354475. ISBN 354035445X. MR2265882. http://www.springer.com/mathematics/applications/book/9783540354451.
 Luenberger, David G.; Ye, Yinyu (2008). Linear and nonlinear programming. International Series in Operations Research & Management Science. 116 (Third ed.). New York: Springer. pp. xiv+546. ISBN 9780387745022. MR2423726.
 Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0387987932.
 Jan Brinkhuis and Vladimir Tikhomirov, 'Optimization: Insights and Applications', 2005, Princeton University Press
External links
 Nonlinear programming FAQ
 Mathematical Programming Glossary
 Nonlinear Programming Survey OR/MS Today
 Overview of Optimization in Industry
Optimization: Algorithms, methods, and heuristics Unconstrained nonlinear: Methods calling ... ... and gradients... and HessiansConstrained nonlinear GeneralDifferentiableAugmented Lagrangian methods · Sequential quadratic programming · Successive linear programmingConvex minimization GeneralBasisexchangeCombinatorial ParadigmsApproximation algorithm · Dynamic programming · Greedy algorithm · Integer programming (Branch & bound or cut)Graph algorithmsMetaheuristics Categories: Mathematical optimization
 Optimization methods
Wikimedia Foundation. 2010.
Look at other dictionaries:
nonlinear programming — netiesinis programavimas statusas T sritis automatika atitikmenys: angl. nonlinear programming vok. nichtlineare Programmierung, f rus. нелинейное программирование, n pranc. programmation non linéaire, f … Automatikos terminų žodynas
nonlinear programming — Fin a process in which the equations expressing the interactions of variables are not all linear but may, for example, be in proportion to the square of a variable … The ultimate business dictionary
programming — Fin see dynamic programming, linear programming, nonlinear programming … The ultimate business dictionary
Nonlinear conjugate gradient method — In numerical optimization, the nonlinear conjugate gradient method generalizes the conjugate gradient method to nonlinear optimization. For a quadratic function : The minimum of f is obtained when the gradient is 0: . Whereas linear conjugate… … Wikipedia
Nonlinear dimensionality reduction — High dimensional data, meaning data that requires more than two or three dimensions to represent, can be difficult to interpret. One approach to simplification is to assume that the data of interest lies on an embedded non linear manifold within… … Wikipedia
Nonlinear gameplay — See also: Open world A video game with nonlinear gameplay presents players with challenges that can be completed in a number of different sequences. Each player sees only some of the challenges possible, and the same challenges may be played in a … Wikipedia
Nonlinear complementarity problem — In applied mathematics, a nonlinear complementarity problem (NCP) with respect to a mapping ƒ : Rn → Rn, denoted by NCPƒ, is to find a vector x ∈ Rn such that where ƒ(x) is a smooth mapping. References Stephen C.… … Wikipedia
Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… … Wikipedia
mathematical programming — Application of mathematical and computer programming techniques to the construction of deterministic models, principally for business and economics. For models that only require linear algebraic equations, the techniques are called linear… … Universalium
Sequential quadratic programming — (SQP) is one of the most popular and robust algorithms for nonlinear continuous optimization. The method is based on solving a series of subproblems designed to minimize a quadratic model of the objective subject to a linearization of the… … Wikipedia