Half Spaces and hyperplanes
Half-Spaces and Hyperplanes
Linear inequalities define half-spaces.
Linear equalities define hyperplanes.
Together, they form the geometry of linear programming.
Hyperplane
A hyperplane is the set of points satisfying:
\[a^Tx=b\]where:
\[a\ne 0\]In two dimensions, a hyperplane is a line.
In three dimensions, a hyperplane is a plane.
In $n$ dimensions, it is called a hyperplane.
Half-Space
A half-space is one side of a hyperplane.
The inequality:
\[a^Tx\le b\]defines one half-space.
The inequality:
\[a^Tx\ge b\]defines the opposite half-space.
The hyperplane:
\[a^Tx=b\]is the boundary between them.
Example in Two Variables
Consider:
\[x_1+2x_2\le 10\]The boundary line is:
\[x_1+2x_2=10\]This line splits the plane into two half-planes.
One side satisfies:
\[x_1+2x_2\le 10\]The other side satisfies:
\[x_1+2x_2\ge 10\]Plotting a Half-Plane
To plot:
\[x_1+2x_2\le 10\]first draw the boundary line:
\[x_1+2x_2=10\]Find two points:
If $x_1=0$:
\[x_2=5\]so one point is $(0,5)$.
If $x_2=0$:
\[x_1=10\]so another point is $(10,0)$.
Then draw the line through $(0,5)$ and $(10,0)$.
Trial Point Method
After drawing the boundary line, choose a trial point not on the line.
The easiest trial point is usually:
\[(0,0)\]Substitute it into the inequality:
\[0+2(0)\le 10\] \[0\le 10\]This is true.
Therefore, the half-plane containing $(0,0)$ is the feasible side.
When the Trial Point Fails
For:
\[x_1+2x_2\ge 10\]using $(0,0)$ gives:
\[0\ge 10\]which is false.
So the feasible side is the side opposite $(0,0)$.
Nonnegativity Constraints
The constraints:
\[x_1\ge 0\]and:
\[x_2\ge 0\]restrict the solution to the first quadrant.
In two-variable LP, this is very common because variables usually represent quantities.
Examples:
- production amounts
- investment amounts
- transported goods
- hectares of land
- hours of machine use
Feasible Region
The feasible region is the intersection of all half-spaces defined by the constraints.
Example:
\[x_1+2x_2\le 10\] \[2x_1+x_2\le 16\] \[-x_1+x_2\le 3\] \[x_1,x_2\ge 0\]The feasible region is the set of points satisfying all five inequalities.
Boundary Lines
Each inequality has an associated equality.
| Inequality | Boundary |
|---|---|
| $x_1+2x_2\le 10$ | $x_1+2x_2=10$ |
| $2x_1+x_2\le 16$ | $2x_1+x_2=16$ |
| $-x_1+x_2\le 3$ | $-x_1+x_2=3$ |
| $x_1\ge 0$ | $x_1=0$ |
| $x_2\ge 0$ | $x_2=0$ |
The feasible region is formed by choosing the correct side of each boundary.
Closed Half-Space
An inequality with $\le$ or $\ge$ includes the boundary.
Example:
\[a^Tx\le b\]includes all points satisfying:
\[a^Tx=b\]So it is a closed half-space.
Strict Half-Space
An inequality with $<$ or $>$ does not include the boundary.
Example:
\[a^Tx<b\]does not include the hyperplane:
\[a^Tx=b\]Most standard LP problems use non-strict inequalities:
\[\le, \ge\]Polyhedron
A polyhedron is an intersection of finitely many half-spaces and hyperplanes.
A linear programming feasible region is a polyhedron.
For example:
\[P = \{x\in\mathbb{R}^n \mid Ax\le b\}\]is a polyhedron.
In standard form:
\[P = \{x\in\mathbb{R}^n \mid Ax=b,\ x\ge 0\}\]is also a polyhedron.
Convexity
Every half-space is convex.
The intersection of convex sets is convex.
Therefore, every LP feasible region is convex.
This means:
If $x$ and $y$ are feasible, then:
\[\alpha x+(1-\alpha)y\]is feasible for every:
\[0\le \alpha\le 1\]Vertices
A vertex is a corner point of the feasible region.
In two dimensions, vertices are usually intersections of boundary lines.
In standard-form LP, vertices correspond to basic feasible solutions.
Edges
An edge is a boundary segment between vertices.
Simplex moves from one vertex to an adjacent vertex along an edge.
Bounded Feasible Region
A feasible region is bounded if it fits inside some large ball.
In two dimensions, this means it is contained inside a sufficiently large circle.
A bounded feasible region looks like a closed polygon.
Unbounded Feasible Region
A feasible region is unbounded if it extends infinitely in at least one direction.
An LP with an unbounded feasible region may still have an optimal solution.
But if the objective improves forever along an unbounded direction, then the LP has no finite optimum.
Infeasible Region
If the half-spaces have no common intersection, the feasible region is empty.
Then the problem is infeasible.
Example:
\[x_1\ge 2\]and:
\[x_1\le 1\]cannot both be true.
So the feasible region is empty.
Objective Hyperplanes
For an objective:
\[f(x)=c^Tx\]the sets:
\[c^Tx=k\]are hyperplanes.
In graphical solution, we slide these hyperplanes across the feasible region.
For maximization, we move in the direction of $c$.
For minimization, we move in the direction of $-c$.
OR Interpretation
Half-spaces represent constraints.
Examples:
\[\text{resource use} \le \text{available resource}\] \[\text{production} \ge \text{minimum demand}\] \[\text{investment} \le \text{budget limit}\]The feasible region is the set of all decisions satisfying every constraint.
Common Procedure for Graphical LP
- Convert each inequality into an equality.
- Draw each boundary line.
- Use a trial point to choose the correct half-plane.
- Intersect all half-planes.
- Identify the feasible region.
- Use objective contour lines to find the optimum.
Checklist
You understand half-spaces and hyperplanes if you can:
- identify the boundary hyperplane of an inequality
- plot a half-plane in two variables
- use the trial point method
- explain nonnegativity constraints geometrically
- define a feasible region as an intersection
- distinguish bounded, unbounded, and empty feasible regions
- explain why LP feasible regions are convex
- connect vertices to candidate optimal solutions
See Also
- Geometry of Linear Equations
- Feasible Regions
- Plotting Linear Inequalities
- Objective Contour Lines
- Polyhedra
- Vertices
- Graphical Method
Exam checkpoint
Use this topic only as much as needed to support LP algebra: matrices, rank, bases, linear systems, half-spaces, and hyperplanes. Connect every computation back to $Ax=b$, basis matrices, and feasible regions.