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. It is the sub-field of Mathematical
optimization that deals with problems that are not linear.
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 non-linear, and they are usually very complicated.
In experimental science, some simple data analysis can be done with linear methods,
but in general these problems, also, are non-linear. 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.
The general non-linear optimization problem The problem can be stated simply as:
to maximize some variable such as product throughout
or to minimize a cost function
where
s.t.
Possible solutions feasible, that is, for an optimal solution
subject to constraints, the objective function is either maximized or minimized.
unbounded, that is, for some subject to constraints, the objective function is either or .
infeasible, that is, there is no solution that is subject to constraints.
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, or convex 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 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 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 provide necessary conditions for a solution to be
optimal. Under convexity, these conditions are also sufficient. If some of the functions
are non-differentiable, subdifferential versions of Karush–Kuhn–Tucker conditions are available.
Examples 2-dimensional example
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 =. Solve 2-D Problem.
3-dimensional example
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 =. Solve 3-D Problem. See also
Curve fitting Least squares minimization
Linear programming nl
Mathematical optimization List of optimization software
Werner Fenchel References
^ Bertsekas, Dimitri P.. Nonlinear Programming. Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0.
^ Ruszczyński, Andrzej. Nonlinear Optimization. Princeton, NJ: Princeton University Press.
pp. xii+454. ISBN 978-0691119151. MR 2199043. Further reading
Avriel, Mordecai. Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
Bazaraa, Mokhtar S. and Shetty, C. M.. Nonlinear programming. Theory and algorithms. John Wiley
& Sons. ISBN 0-471-78610-1. Bertsekas, Dimitri P.. Nonlinear Programming:
2nd Edition. Athena Scientific. ISBN 1-886529-00-0. Bonnans, J. Frédéric; Gilbert, J. Charles;
Lemaréchal, Claude; Sagastizábal, Claudia A.. Numerical optimization: Theoretical and practical
aspects. Universitext. Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5.
ISBN 3-540-35445-X. MR 2265882. Luenberger, David G.; Ye, Yinyu. Linear and
nonlinear programming. International Series in Operations Research & Management Science
116. New York: Springer. pp. xiv+546. ISBN 978-0-387-74502-2. MR 2423726.
Nocedal, Jorge and Wright, Stephen J.. Numerical Optimization. Springer. ISBN 0-387-98793-2.
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