Nonlinear programming: Difference between revisions
imported>Igor Grešovnik (added Mathematical formulation) |
mNo edit summary |
||
| (11 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
In [[mathematics]], '''nonlinear programming''' ('''NLP''') is the process of minimization or maximization of a function of a set of real variables (termed ''objective function''), while simultaneously satisfying a set of [[Equation|equalities]] and [[inequality|inequalities]] ( collectively termed ''constraints''), where some of the constraints or the objective function are [[ | {{subpages}} | ||
In [[mathematics]], '''nonlinear programming''' ('''NLP''') is the process of minimization or maximization of a function of a set of real variables (termed ''objective function''), while simultaneously satisfying a set of [[Equation|equalities]] and [[inequality|inequalities]] ( collectively termed ''constraints''), where some of the constraints or the objective function are [[Linear map|nonlinear]]. | |||
== Mathematical formulation == | == Mathematical formulation == | ||
A '''nonlinear programming problem''' can be stated as: | A '''nonlinear programming problem''' can be stated as: | ||
:<math>\min_{x \in X}f(x)</math> | :<math>\min_{\bold{x} \in X}f(\bold{x})</math> | ||
or | or | ||
:<math>\max_{x \in X}f(x)</math> | :<math>\max_{\bold{x} \in X}f(\bold{x})</math> | ||
where | where | ||
:<math>f: R^n \to R</math> | :<math>f: R^n \to R</math> | ||
:<math>X \subseteq R^n.</math> | :<math>X \subseteq R^n.</math> | ||
In the above equations, the set ''X'' is also called the ''feasible set'' or ''feasible region'' of the problem. The function to be minimized is often called the ''objective function'' or ''cost function''. | |||
The feasible region is often defined in terms of a set of equalities and inequalities termed constraints. In this case, the NLP problem can be stated as | |||
:<math>\min f(\bold{x})</math> | |||
''subject to'': | |||
:<math>c_{i}(\bold{x})\le 0, i \in I</math> | |||
''and'' | |||
:<math>c_{j}(\bold{x})=0, j \in E</math> | |||
In the above problem statement, the second line defines the inequality constraints, and the third line defines the equality constraints. Constraints define the feasible set ''X'', which is the set of points that satisfy all the constraints. ''I'' is the index set of inequality constraints and ''E'' is the index set of inequality constraints. Functions ''c''<sub>''i''</sub>('''x''') and ''c''<sub>''i''</sub>('''x''') are termed ''constraint functions''. | |||
== Methods for solving NLP problems == | |||
If the objective function ''f'' is linear and the constrained [[Euclidean space|space]] is a [[polytope]], the problem is a [[linear programming]] problem, which may be solved using well known linear programming algorithms. Linear programming problems can be solved in a number of steps that is bounded by a polynomial in the input size (see [[computational complexity]]). | |||
If the objective function is [[Convex function|convex]] (in a minimization problem) and the constraint set is a [[Convex set|convex]], then general methods from [[Convex optimization|convex optimization]] can be used. | |||
Several methods are available for solving nonconvex problems. One of the most popular methods for problems with continuously differentiable functions is the [[Sequential quadratic programming]] method (SQP). | |||
== See also == | |||
* [[Optimization (mathematics)|Optimization]] | |||
== External links == | |||
*[http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html Nonlinear programming FAQ] | |||
*[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary][[Category:Suggestion Bot Tag]] | |||
Latest revision as of 11:01, 26 September 2024
In mathematics, nonlinear programming (NLP) is the process of minimization or maximization of a function of a set of real variables (termed objective function), while simultaneously satisfying a set of equalities and inequalities ( collectively termed constraints), where some of the constraints or the objective function are nonlinear.
Mathematical formulation
A nonlinear programming problem can be stated as:
or
where
In the above equations, the set X is also called the feasible set or feasible region of the problem. The function to be minimized is often called the objective function or cost function.
The feasible region is often defined in terms of a set of equalities and inequalities termed constraints. In this case, the NLP problem can be stated as
subject to:
and
In the above problem statement, the second line defines the inequality constraints, and the third line defines the equality constraints. Constraints define the feasible set X, which is the set of points that satisfy all the constraints. I is the index set of inequality constraints and E is the index set of inequality constraints. Functions ci(x) and ci(x) are termed constraint functions.
Methods for solving NLP problems
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 algorithms. Linear programming problems can be solved in a number of steps that is bounded by a polynomial in the input size (see computational complexity).
If the objective function is convex (in a minimization problem) and the constraint set is a convex, then general methods from convex optimization can be used.
Several methods are available for solving nonconvex problems. One of the most popular methods for problems with continuously differentiable functions is the Sequential quadratic programming method (SQP).