Information about 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 is nonlinear.
If the objective function is concave (maximization problem), or convex (minimization problem) and the constraint set is convex, then 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 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 or lower than 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 solution cannot be more than a certain percentage better than a solution that has been found. 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.
The Karush-Kuhn-Tucker (KKT) conditions provide the necessary conditions for a solution to be optimal.
A simple problem can be defined by the constraints
Another simple problem can be defined by the constraints
Mathematical formulation of the problem
The problem can be stated simply as:
to maximize some variable such as product throughput
to minimize a cost function
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 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 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 or lower than 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 solution cannot be more than a certain percentage better than a solution that has been found. 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.
The Karush-Kuhn-Tucker (KKT) conditions provide the necessary conditions for a solution to be optimal.
Examples
2-dimensional example
)
The intersection of the line with the constrained space represents the solution
- x1 ≥ 0
- x2 ≥ 0
- x12 + x22 ≥ 1
- x12 + x22 ≤ 2
- f(x) = x1 + x2
3-dimensional example
)
The intersection of the top surface with the constrained space in the center represents the solution
- x12 − x22 + x32 ≤ 2
- x12 + x22 + x32 ≤ 10
- f(x) = x1x2 + x2x3
See also
- optimization
- curve fitting
- least squares minimization
References
- 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.
- Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2.
- Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.
- Jalaluddin Abdullah, Optimization by the Fixed-Point Method, Version 1.97, Optimization Onlinehttp://www.optimization-online.org/DB_HTML/2007/09/1775.html, and Vuze/Azureus (under Science and Technology)http://www.vuze.com/details/N4SRIDNBRGI3DMUHZX2FP2U2MAKJLUL2.html, August 2007. Note: 1. The book is free. 2. To obtain from Vuze you need a bittorrent client, preferably Azureus.
External links
- Nonlinear programming FAQ
- Mathematical Programming Glossary
- Nonlinear Programming Survey OR/MS Today
Mathematics (colloquially, maths or math) is the body of knowledge centered on such concepts as quantity, structure, space, and change, and also the academic discipline that studies them. Benjamin Peirce called it "the science that draws necessary conclusions".
..... Click the link for more information.
..... Click the link for more information.
equation is a mathematical statement, in symbols, that two things are the same (or equivalent). Equations are written with an equal sign, as in
The equation above is an example of an equality: a proposition which states that two constants are equal.
..... Click the link for more information.
- .
The equation above is an example of an equality: a proposition which states that two constants are equal.
..... Click the link for more information.
inequality is a statement about the relative size or order of two objects. (See also: equality)
..... Click the link for more information.
- The notation means that a is less than b and
- The notation means that a is greater than b.
..... Click the link for more information.
function expresses dependence between two quantities, one of which is given (the independent variable, argument of the function, or its "input") and the other produced (the dependent variable, value of the function, or "output").
..... Click the link for more information.
..... Click the link for more information.
Euclidean space. Most of this article is devoted to developing the modern language necessary for the conceptual leap to higher dimensions.
An essential property of a Euclidean space is its flatness. Other spaces exist in geometry that are not Euclidean.
..... Click the link for more information.
An essential property of a Euclidean space is its flatness. Other spaces exist in geometry that are not Euclidean.
..... Click the link for more information.
In geometry polytope means, first, the generalization to any dimension of polygon in two dimensions, polyhedron in three dimensions, and polychoron in four dimensions. Beyond that, the term is used for a variety of related mathematical concepts.
..... Click the link for more information.
..... Click the link for more information.
In mathematics, linear programming (LP) problems involve the optimization of a linear objective function, subject to linear equality and inequality constraints.
Put very informally, LP is about trying to get the best outcome (e.g.
..... Click the link for more information.
Put very informally, LP is about trying to get the best outcome (e.g.
..... Click the link for more information.
concave, if for any two points x and y in its domain C and any t in [0,1], we have
Also, f(x) is concave on [a, b] if and only if the function −f(x
..... Click the link for more information.
Also, f(x) is concave on [a, b] if and only if the function −f(x
..... Click the link for more information.
convex, or concave up, if for any two points x and y in its domain C and any t in [0,1], we have
In other words, a function is convex if and only if its epigraph (the set of points lying on or above the graph) is
..... Click the link for more information.
In other words, a function is convex if and only if its epigraph (the set of points lying on or above the graph) is
..... Click the link for more information.
convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object. For example, a solid cube is convex, but anything that is hollow or has a dent in it, for example, a crescent shape, is not convex.
..... Click the link for more information.
..... Click the link for more information.
Convex optimization is a subfield of mathematical optimization. Given a real vector space together with a convex, real-valued function
defined on a convex subset of , the problem is to find the point in for which the number is smallest, i.e.
..... Click the link for more information.
defined on a convex subset of , the problem is to find the point in for which the number is smallest, i.e.
..... Click the link for more information.
Branch and bound (BB) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are
..... Click the link for more information.
..... Click the link for more information.
In mathematics, the Karush-Kuhn-Tucker conditions (also known as the Kuhn-Tucker or the KKT conditions) are necessary for a solution in nonlinear programming to be optimal. It is a generalization of the method of Lagrange multipliers.
..... Click the link for more information.
..... Click the link for more information.
dimension (Latin, "measured out") is a parameter or measurement required to define the characteristics of an object—i.e., length, width, and height or size and shape.
..... Click the link for more information.
..... Click the link for more information.
dimension (Latin, "measured out") is a parameter or measurement required to define the characteristics of an object—i.e., length, width, and height or size and shape.
..... Click the link for more information.
..... Click the link for more information.
In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set.
..... Click the link for more information.
..... Click the link for more information.
Curve fitting is finding a curve which matches a series of data points and possibly other constraints. This section is an introduction to both interpolation (where an exact fit to constraints is expected) and regression analysis. Both are sometimes used for extrapolation.
..... Click the link for more information.
..... Click the link for more information.
In regression analysis, least squares, also known as ordinary least squares analysis, is a method for linear regression that determines the values of unknown quantities in a statistical model by minimizing the sum of the residuals (the difference between the predicted and
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
