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]

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

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₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

with an objective function to be maximized

f(x) = x₁ + x₂

where x = (x₁, x₂). Solve 2-D Problem.

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₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

with an objective function to be maximized

f(x) = x₁x₂ + x₂x₃

where x = (x₁, x₂, x₃). Solve 3-D Problem.

See also

• Curve fitting
• Least squares minimization
• Linear programming
• nl (format)
• Mathematical optimization
• List of optimization software

References

1. ^ Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0. 

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.
• 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: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR2265882. http://www.springer.com/mathematics/applications/book/978-3-540-35445-1. 
• 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 978-0-387-74502-2. MR2423726. 
• Nocedal, Jorge and Wright, Stephen J. (1999). 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

v · d · eOptimization: Algorithms, methods, and heuristics  Unconstrained nonlinear: Methods calling ... ... functions Golden section search · Interpolation methods · Line search · Successive parabolic interpolation ... and gradients Convergence Trust region · Wolfe conditions Quasi–Newton BFGS and L-BFGS · DFP · Symmetric rank-one (SR1) Other methods Gauss–Newton · Gradient · Levenberg–Marquardt · Conjugate gradient ... and Hessians Newton's method  Constrained nonlinear General Barrier methods · Penalty methods Differentiable Augmented Lagrangian methods · Sequential quadratic programming · Successive linear programming  Convex minimization General Interior point method · Reduced gradient (Frank–Wolfe) · Subgradient method · Cutting-plane method Linear and quadratic Interior point Ellipsoid method of Khachiyan · Projective algorithm of Karmarkar · Semidefinite programming Basis-exchange Simplex algorithm of Dantzig · Criss-cross algorithm · Principal pivoting algorithm of Lemke  Combinatorial Paradigms Approximation algorithm · Dynamic programming · Greedy algorithm · Integer programming (Branch & bound or cut) Graph algorithms Minimum spanning tree Bellman–Ford algorithm · Borůvka · Dijkstra · Floyd–Warshall  · Johnson · Kruskal Network flows Dinic · Edmonds–Karp · Ford–Fulkerson · Push-relabel maximum flow  Metaheuristics Evolutionary algorithm · Hill climbing · Local search · Simulated annealing · Tabu search Categories (Algorithms · Methods · Heuristics) · Software