Constraint (mathematics)

﻿
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(\bold x) = x_1^2+x_2^4$

subject to $x_1 \ge 1$

and $x_2 = 1, \,$

where $\bold x$ denotes the vector (x1, x2).

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 constraints, the solution would be $(0,0)\,$ where $f(\bold x)$ has the lowest value. But this solution does not satisfy the constraints. The solution of the constrained optimization problem stated above but $\bold x = (1,1)$, which is the point with the smallest value of $f(\bold x)$ that satisfies the two constraints.

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.

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Constraint — is an element factor or a subsystem that works as a bottleneck. It restricts an entity, project, or system (such as a manufacturing or decision making process) from achieving its potential (or higher level of output) with reference to its goal.… …   Wikipedia

• Constraint satisfaction — In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that… …   Wikipedia

• Mathematics of Sudoku — The class of Sudoku puzzles consists of a partially completed row column grid of cells partitioned into N regions each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, ..., N}), so that each …   Wikipedia

• Constraint inference — In constraint satisfaction, constraint inference is a relationship between constraints and their consequences. A set of constraints D entails a constraint C if every solution to D is also a solution to C. In other words, if V is a valuation of… …   Wikipedia

• Constraint Composite Graph — The constraint composite graph is a node weighted undirected graph associated with a given combinatorial optimization problem posed as a weighted constraint satisfaction problem. Developed and introduced by Satish Kumar Thittamaranahalli (T. K.… …   Wikipedia

• Constraint graph — For a graph in electronic design automation, see Constraint graph (layout). In constraint satisfaction research of artificial intelligence and operations research, constraint graphs and hypergraphs are used to represent relations among… …   Wikipedia

• Constraint counting — In mathematics, constraint counting is a crude but often useful way of counting the number of free functions needed to specify a solution to a partial differential equation. Contents 1 Einstein strength 1.1 Linear equations 1.2 General solution… …   Wikipedia

• List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

• Optimization (mathematics) — 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… …   Wikipedia

• List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia