Nonlinear programming

From Citizendium, the Citizens' Compendium
Jump to: navigation, search
This article is developing and not approved.
Main Article
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
This editable Main Article is under development and not meant to be cited; by editing it you can help to improve it towards a future approved, citable version. These unapproved articles are subject to a disclaimer.

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:



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:


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).

See also

External links