Half-Spaces and Hyperplanes

A single linear equation describes a flat boundary that divides space in two, and a single linear inequality describes one of the two sides together with that boundary. These are the pieces every feasible region is assembled from: the region is what survives when all the allowed sides are intersected.

Definition

For a nonzero vector $a \in R^{n}$ and a scalar $b$ , the hyperplane $H = {x \in R^{n} : a^{T} x = b}$ is the solution set of one linear equation. It divides $R^{n}$ into two closed half-spaces, ${x : a^{T} x \leq b}$ and ${x : a^{T} x \geq b}$ , each containing $H$ itself.

Formal statement

$H = {x \in R^{n} : a^{T} x = b}$ with $a \neq 0$ ; the closed half-spaces bounded by $H$ are ${x : a^{T} x \leq b}$ and ${x : a^{T} x \geq b}$ .

Assumptions and scope

The normal vector must be nonzero. If $a = 0$ the equation $a^{T} x = b$ is either satisfied by every point, when $b = 0$ , or by none, when $b \neq 0$ ; in neither case is a boundary described, so $a \neq 0$ is part of the definition rather than a technicality.
A closed half-space contains its boundary hyperplane. The strict inequality $a^{T} x < b$ describes an open half-space, which excludes the boundary; linear programs are written with closed half-spaces, which is why an optimum can sit exactly on a constraint.
Scaling a constraint does not move it, but negating it swaps the side. Multiplying $a$ and $b$ by the same positive number describes the same half-space; multiplying by a negative number describes the other one, which is the mechanism behind rewriting $a^{T} x \geq b$ as $- a^{T} x \leq - b$ .
The sign of $a^{T} x - b$ decides the side, and its magnitude does not. A point far from the boundary and a point just across it are on the same side; distance is a separate question from membership.

Forms this is expressed in

The same content in several forms. Each makes something visible that the others leave implicit, so moving between them is part of understanding the topic rather than a presentation choice.

geometric

One inequality keeps a line and everything on one side of it

One inequality drawn in the plane. The equation $a^{T} x = b$ is a line, and the inequality keeps that line together with everything on one side of it.

The shaded side is not decided by the direction of the inequality sign but by testing a point: substitute it and see whether the arithmetic holds. The boundary belongs to the region whenever the inequality is weak, which is why an optimum is allowed to sit exactly on a constraint.

What the picture cannot do is generalise. The test is arithmetic and works in any number of variables; the drawing stops at three.

Worked material

Example

Deciding sides by arithmetic

Take the constraint $2 x_{1} + x_{2} \leq 6$ , so $a = (2, 1)^{T}$ and $b = 6$ . Its bounding hyperplane is the line $2 x_{1} + x_{2} = 6$ .

The point $(1, 1)$ . Evaluate $2 (1) + 1 = 3$ . Since $3 \leq 6$ , the point satisfies the constraint and lies in the half-space.

The point $(4, 0)$ . Evaluate $2 (4) + 0 = 8$ . Since $8 > 6$ , the point violates the constraint.

The point $(2, 2)$ . Evaluate $2 (2) + 2 = 6$ , exactly $b$ . The point lies on the hyperplane. Because the inequality is $\leq$ rather than $<$ , it satisfies the constraint. A fact that matters later, because optima in linear programming sit on constraint boundaries.

Nothing in this procedure mentions the number of variables. For $3 x_{1} - x_{2} + 4 x_{3} \leq 10$ and the point $(1, 2, 1)$ : $3 - 2 + 4 = 5 \leq 10$ , so it is allowed. There is no picture, and none is needed.

Contrast

Hyperplanes in two dimensions and in higher dimensions

Two-variable problems are drawn on paper, so "constraint" and "line" come to feel like the same word. They are not.

In $R^{2}$ . $x_{1} + x_{2} = 4$ is a line, and $x_{1} + x_{2} \leq 4$ is everything on one side of it. Dimension $n - 1 = 1$ .

In $R^{3}$ . $x_{1} + x_{2} + x_{3} = 4$ is a plane, not a line. The half-space it bounds is a solid slab of space. Dimension $n - 1 = 2$ .

In $R^{50}$ . The same kind of equation gives a 49-dimensional flat that cannot be pictured at all. The arithmetic test is unchanged.

The habit to avoid is calling every constraint "the line" and expecting to reason by sketching. Real programs have more variables than a page has dimensions, and the competence that survives the move is the evaluation, not the drawing.

Common errors

Common misconception

A linear constraint is a line, so a hyperplane is always one-dimensional and a feasible region is always a flat shape drawn on paper.

Related units

Connected

The Feasible Region of a Linear Program (part of)
Feasible Sets (related)

Learn this topic

Half-Spaces and Hyperplanes

Used in

Foundations for Operational Research

Sources

Introduction to Linear Algebra (2016)
Introduction to Linear Optimization (1997)

Half-Spaces and Hyperplanes

Assumptions and scope

Forms this is expressed in

Worked material

Deciding sides by arithmetic

Hyperplanes in two dimensions and in higher dimensions

Common errors

Related units

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history