Nonlinear programming

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:

$\min _{{\mathbf {x}}\in X}f({\mathbf {x}})$

or

$\max _{{\mathbf {x}}\in X}f({\mathbf {x}})$

where

$f:R^{n}\to R$

$X\subseteq R^{n}.$

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

$\min f({\mathbf {x}})$

subject to:

$c_{i}({\mathbf {x}})\leq 0,i\in I$

and

$c_{j}({\mathbf {x}})=0,j\in E$

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_i(x) and c_i(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).

See also

• Optimization

External links

• Nonlinear programming FAQ
• Mathematical Programming Glossary