Constraint (mathematics)

In mathematics, a constraint is a condition that a solution to an optimization problem must satisfy. There are two types of constraints: equality constraints and inequality constraints. The set of solutions that satisfy all constraints is called the feasible set.

Example

The following is a simple optimization problem:

$\min f({\mathbf {x}})=x_{1}^{2}+x_{2}^{4}$

subject to

$x_{1}\geq 1$

and

$x_{2}=1,\,$

where ${\mathbf {x}}$ denotes the vector (x₁, x₂).

In this example, the first line defines the function to be minimized (called the objective or cost function). The second and third lines define two constraints, the first of which is an inequality constraint and the second is an equality constraint. These two constraints define the feasible set of candidate solutions.

Without the constrains, the solution would be $(0,0)\,$ were $f({\mathbf {x}})$ has the lowest value. But this solution does not satisfy the constraints. The solution of the constrained optimization problem stated above but ${\mathbf {x}}=(1,1)$, which is the point with the greatest value of $f({\mathbf {x}})$ that satisfies the two constraints.

Standard form

In standard form, constraints are written with a constraint function on one side of the equation or inequality and 0 on the other side. In the example above, the constraints can be rewritten in standard form as

$c_{1}({\mathbf {x} })=1-x_{1}\leq 0$

and

$c_{2}({\mathbf {x} })=1-x_{2}=0.$

Equivalently, inequality constraints can be written in standard form with the opposite signs. Thus, the first constraint above can be written as

$c_{1}({\mathbf {x}})=x_{1}-1\geq 0.$

Inequality constraints can be changed to equalities by introducing a slack variable, with the slack variable including the constraint

Terminology

• If a constraint is an equality at a given point, the constraint is said to be binding, as the point cannot be varied in the direction of the constraint.
• If a constraint is an inequality at a given point, the constraint is said to be non-binding, as the point can be varied in the direction of the constraint.
• If a constraint is not satisfied, the point is said to be infeasible.

See also

• Karush–Kuhn–Tucker conditions
• Lagrange multipliers
• Level set
• Linear programming
• Nonlinear programming

External links

• Nonlinear programming FAQ
• Mathematical Programming Glossary