en>Quondum: /* Uses */ removing trailing blank line

2014-01-25T03:26:16Z

Uses: removing trailing blank line

New page

{{mergefrom|Candidate solution|date=August 2013}}
[[File:IP polytope with LP relaxation.png|350px|thumb|A problem with five linear constraints (in blue, including the non-negativity constraints). In the absence of integer constraints the feasible set is the entire region bounded by blue, but with [[integer constraint]]s it is the set of red dots.]]
[[File:3dpoly.svg|thumb|right|A closed feasible region of a [[linear programming]] problem with three variables is a convex [[polyhedron]].]]

In [[mathematical optimization]], a '''feasible region''', '''feasible set''', '''search space''', or '''solution space''' is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's [[Constraint (mathematics)|constraints]], potentially including [[Inequality (mathematics)|inequalities]], [[Equality (mathematics)|equalities]], and [[integer]] constraints. This is the initial set of [[candidate solution]]s to the problem, before the set of candidates has been narrowed down.

For example, consider the problem

:'''Minimize''' <math> x_1^2+x_2^4 </math>

with respect to the variables <math>x_1</math> and <math>x_2,</math>

subject to

:<math> 1 \le x_1 \le 10 </math>

and

:<math> 5 \le x_2 \le 12. \, </math>

Here the feasible set is the set of pairs (''x''1, ''x''2) in which the value of ''x''1 is at least 1 and at most 10 and the value of ''x''2 is at least 5 and at most 12. Note that the feasible set of the problem is separate from the [[objective function]], which states the criterion to be optimized and which in the above example is <math> x_1^2+x_2^4. </math>

In many problems, the feasible set reflects a constraint that one or more variables must be non-negative. In pure [[integer programming]] problems, the feasible set is the set of integers (or some subset thereof). In [[linear programming]] problems, the feasible set is a [[Convex set|convex]] [[polytope]]: a region in [[Dimension (mathematics and physics)|multidimensional space]] whose boundaries are formed by [[hyperplanes]] and whose corners are [[vertex (geometry)|vertices]].

[[Constraint satisfaction]] is the process of finding a point in the feasible region.

==Convex feasible set==
{{See also|Convex optimization}}
[[File:Linear Programming Feasible Region.svg|frame|In a linear programming problem, a series of linear constraints produces a convex feasible region of possible values for those variables. In the two-variable case this region is in the shape of a convex [[simple polygon]].]]

A [[convex set|convex]] feasible set is one in which a line segment connecting any two feasible points goes through only other feasible points, and not through any points outside the feasible set. Convex feasible sets arise in many types of problems, including linear programming problems, and they are of particular interest because, if the problem has a [[convex function|convex objective function]] that is to be maximized, it will generally be easier to solve in the presence of a convex feasible set and any [[local optimum]] will also be a [[global optimum]].

==No feasible set==

If the constraints of an optimization problem are mutually contradictory, there are no points that satisfy all the constraints and thus the feasible region is the [[null set]]. In this case the problem has no solution and is said to be ''infeasible''.

==Bounded and unbounded feasible sets==

[[Image:Bounded unbounded.svg|right|thumb|A bounded feasible set (top) and an unbounded feasible set (bottom). The set at the bottom continues forever towards the right.]]

Feasible sets may be [[Bounded set|bounded or unbounded]]. For example, the feasible set defined by the constraint set {''x'' ≥ 0, ''y'' ≥ 0} is unbounded because in some directions there is no limit on how far one can go and still be in the feasible region. In contrast, the feasible set formed by the constraint set {''x'' ≥ 0, ''y'' ≥ 0, ''x'' + 2''y'' ≤ 4} is bounded because the extent of movement in any direction is limited by the constraints.

In linear programming problems with ''n'' variables, a [[Necessary and sufficient conditions|necessary but not sufficient condition]] for the feasible set to be bounded is that the number of constraints be at least ''n'' + 1 (as illustrated by the above example).

If the feasible set is unbounded, there may or may not be an optimum, depending on the specifics of the objective function. For example, if the feasible region is defined by the constraint set {''x'' ≥ 0, ''y'' ≥ 0}, then the problem of maximizing ''x'' + ''y'' has no optimum since any candidate solution can be improved upon by increasing ''x'' or ''y''; yet if the problem is to ''minimize'' ''x'' + ''y'', then there is an optimum (specifically at (''x'', ''y'') = (0, 0)).

[[Category:Decision theory]]
[[Category:Mathematical optimization]]

Axis–angle representation - Revision history

en>Quondum: /* Uses */ removing trailing blank line