Feasible sets
Feasible Sets
The feasible set is the set of all decisions that satisfy every constraint.
It contains all candidate solutions of the optimization problem.
Basic Definition
If the constraints define a set $S$, then:
\[S=\{x\in\mathbb{R}^n \mid x \text{ satisfies all constraints}\}\]The set $S$ is called the feasible set.
A point $x$ is feasible if:
\[x\in S\]A point is infeasible if:
\[x\notin S\]Constrained Optimization Form
A constrained optimization problem can be written as:
\[\min f(x)\]subject to:
\[x\in S\]or:
\[\max f(x)\]subject to:
\[x\in S\]The objective chooses the best point inside $S$.
Example
Consider:
\[x_1+x_2\le 10\] \[x_1\ge 0\] \[x_2\ge 0\]The feasible set is:
\[S=\{(x_1,x_2)\in\mathbb{R}^2 \mid x_1+x_2\le 10,\ x_1\ge 0,\ x_2\ge 0\}\]This is the triangle in the first quadrant below the line $x_1+x_2=10$.
Feasible Solution
A feasible solution is any point satisfying all constraints.
Example:
\[x=(3,4)\]is feasible for:
\[x_1+x_2\le 10,\qquad x_1,x_2\ge 0\]because:
\[3+4=7\le 10\]and both components are nonnegative.
Infeasible Point
For the same constraints:
\[x=(8,5)\]is infeasible because:
\[8+5=13>10\]So it violates the constraint.
Feasible Region
In graphical linear programming, the feasible set is often called the feasible region.
In two variables, it can be drawn in the plane.
In higher dimensions, it exists geometrically but is hard to draw.
Feasible Set as Intersection
Each constraint defines a set of allowed points.
The feasible set is the intersection of all these sets.
For constraints:
\[g_1(x)\le b_1\] \[g_2(x)\le b_2\] \[g_3(x)=b_3\]the feasible set is:
\[S=\{x\mid g_1(x)\le b_1,\ g_2(x)\le b_2,\ g_3(x)=b_3\}\]A point must satisfy every constraint, not just some of them.
Feasible Set in Linear Programming
For a linear program:
\[Ax\le b\]the feasible set is:
\[S=\{x\in\mathbb{R}^n\mid Ax\le b\}\]For standard form:
\[Ax=b,\qquad x\ge 0\]the feasible set is:
\[S=\{x\in\mathbb{R}^n\mid Ax=b,\ x\ge 0\}\]Empty Feasible Set
A feasible set may be empty.
Example:
\[x_1\ge 5\]and:
\[x_1\le 2\]cannot both be true.
So:
\[S=\emptyset\]If $S$ is empty, the problem is infeasible.
There is no feasible solution and no optimal solution.
Bounded Feasible Set
A feasible set is bounded if it does not extend infinitely far.
In two variables, a bounded feasible region fits inside some large circle.
Example:
\[x_1+x_2\le 10,\qquad x_1,x_2\ge 0\]is bounded.
Unbounded Feasible Set
A feasible set is unbounded if it extends infinitely in at least one direction.
Example:
\[x_1-x_2\le 3,\qquad x_1,x_2\ge 0\]can extend infinitely.
An unbounded feasible set does not automatically mean the objective is unbounded.
The objective may still have a finite optimum.
Feasible Set and Objective
The feasible set tells us what is allowed.
The objective function tells us what is best.
Optimization means:
choose the best point among the feasible points.
Convex Feasible Set
A set $S$ is convex if, whenever $x,y\in S$, every point on the line segment between them is also in $S$.
That means:
\[\alpha x+(1-\alpha)y\in S\]for every:
\[0\le \alpha\le 1\]LP Feasible Sets Are Convex
In linear programming, every linear inequality defines a half-space.
Every half-space is convex.
The intersection of convex sets is convex.
Therefore, feasible sets of linear programs are convex.
Polyhedron
A polyhedron is an intersection of finitely many half-spaces and hyperplanes.
Linear programming feasible sets are polyhedra.
Examples:
\[S=\{x\mid Ax\le b\}\]and:
\[S=\{x\mid Ax=b,\ x\ge 0\}\]are polyhedra.
Vertices
A vertex is a corner point of the feasible region.
In two-variable graphical LP, vertices are usually intersections of boundary lines.
In standard-form LP, vertices correspond to basic feasible solutions.
Why Vertices Matter
For linear programming, if an optimal solution exists, then one can be found at a vertex of the feasible set.
This is the geometric reason behind the simplex method.
Simplex moves from one vertex to another.
Feasible Direction
A vector $d$ is a feasible direction at a feasible point $x$ if, for some positive step size $\theta$:
\[x+\theta d\in S\]That means we can move a little from $x$ in direction $d$ and remain feasible.
This idea is used in the simplex method.
Checking Feasibility
To check whether a point is feasible:
- substitute the point into every constraint
- check each equality
- check each inequality
- check sign restrictions
- if all pass, the point is feasible
Example Check
Constraints:
\[x_1+2x_2\le 10\] \[2x_1+x_2\le 16\] \[x_1,x_2\ge 0\]Point:
\[x=(2,3)\]Check:
\[2+2(3)=8\le 10\] \[2(2)+3=7\le 16\] \[2\ge 0,\qquad 3\ge 0\]So $x=(2,3)$ is feasible.
Common Mistake
A point satisfying the objective is not necessarily feasible.
The objective does not define feasibility.
Only the constraints define feasibility.
Checklist
You understand feasible sets if you can:
- define the feasible set
- distinguish feasible and infeasible points
- check feasibility of a point
- explain feasible set as an intersection of constraints
- recognize empty feasible sets
- distinguish bounded and unbounded feasible sets
- explain convexity
- connect vertices with LP optimal solutions
- write feasible sets in matrix form
See Also
- Constraints
- Objective Functions
- Optimal Solutions and Optimal Values
- Half-Spaces and Hyperplanes
- Feasible Regions
- Polyhedra
- Basic Feasible Solutions
Exam checkpoint
In exam problems, translate the story into variables, objective, constraints, feasible set, and optimal value. Always state whether the problem is a maximization or minimization and what the units are.