In mathematics, nonlinear programming is the process of solving an optimization problem defined by 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]} It is the subfield of mathematical optimization that deals with problems that are not linear.
Contents

Applicability 1

Definition 2

Possible types of constraint set 3

Methods for solving the problem 4

Examples 5

2dimensional example 5.1

3dimensional example 5.2

Applications 6

See also 7

References 8

Further reading 9

External links 10
Applicability
A typical nonconvex problem is that of optimising transportation costs by selection from a set of transportation 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.
Modern engineering practice involves much numerical optimization. Except in certain narrow but important cases such as passive electronic circuits, engineering problems are nonlinear, and they are usually very complicated.
In experimental science, some simple data analysis (such as fitting a spectrum with a sum of peaks of known location and shape but unknown magnitude) can be done with linear methods, but in general these problems, also, are nonlinear. Typically, one has a theoretical model of the system under study with variable parameters in it and a model the experiment or experiments, which may also have unknown parameters. One tries to find a best fit numerically. In this case one often wants a measure of the precision of the result, as well as the best fit itself.
Definition
Let n, m, and p be positive integers. Let X be a subset of R^{n}, let f, g_{i}, and h_{j} be realvalued functions on X for each i in {1, …, m} and each j in {1, …, p}.
A nonlinear minimization problem is an optimization problem of the form

\begin{align} \text{minimize } & f(x) \\ \text{subject to } & g_i(x) \leq 0 \text{ for each } i \in \{1, \dotsc, m\} \\ & h_j(x) = 0 \text{ for each } j \in \{1, \dotsc, p\} \\ & x \in X. \end{align}
A nonlinear maximization problem is defined in a similar way.
Possible types of constraint set
There are several possibilities for the nature of the constraint set, also known as the feasible set or feasible region.
An infeasible problem is one for which no set of values for the choice variables satisfies all the constraints. That is, the constraints are mutually contradictory, and no solution exists.
A feasible problem is one for which there exists at least one set of values for the choice variables satisfying all the constraints.
An unbounded problem is a feasible problem for which the objective function can be made to exceed any given finite value. Thus there is no optimal solution, because there is always a feasible solution that gives a better objective function value than does any given proposed solution.
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. If some of the functions are nondifferentiable, subdifferential versions of Karush–Kuhn–Tucker (KKT) conditions are available.^{[2]}
Examples
2dimensional example
The intersection of the line with the constrained space represents the solution. The line is the best achievable
contour line (locus with a given value of the objective function).
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
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_{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.
Applications
Nonlinear optimization methods are used in engineering, for example to construct computational models of oil reservoirs,^{[3]} or for decision making in subsurface oil and gas reservoir projects.^{[4]}
See also
References

^

^

^ History matching production data and uncertainty assessment with an efficient TSVD parameterization algorithm, http://www.sciencedirect.com/science/article/pii/S0920410513003227

^ Closedloop field development under uncertainty using optimization with sample validation. http://dx.doi.org/10.2118/173219PA
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;


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
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.