Half-Spaces and Hyperplanes

One linear inequality cuts space in two. Deciding which side a point is on takes arithmetic, not a drawing, which is the only thing that scales past two dimensions.

That sounds small. It is the atom every feasible region is built from: a region is what remains when the allowed sides of many inequalities are intersected, and a question about the region is usually a question about one constraint at a time.

A single linear equation does not name a point. In the plane, $2x+y=6$ is satisfied by infinitely many pairs. It is a line. In three variables the same kind of equation gives a plane. One equation always costs exactly one dimension, so in $n$ variables it leaves a flat of dimension $n-1$.

That flat is a wall through the space, and it has two sides. Writing $\le$ instead of $=$ keeps the wall and adds everything on one side of it.

Deciding which side a point is on needs no picture. Put the point into the left-hand side and compare the number you get with the right-hand side. The arithmetic answers the question in any number of dimensions, which is exactly where drawing stops being possible.

Let $a\in {\mathbb{R}}^n$ be a nonzero vector and $b$ a scalar. The hyperplane determined by them is

It has dimension $n-1$: a point on a line, a line in the plane, a plane in space. The vector $a$ is its normal, and it points across $H$ rather than along it.

$H$ divides the rest of ${\mathbb{R}}^n$ into two closed half-spaces,

each of which contains $H$ itself. Replacing $\le$ by the strict gives an open half-space, which excludes the boundary.

The requirement $a\ne 0$ is part of the definition, not a technicality. If $a=0$ the equation reads $0=b$, which is satisfied by every point when $b=0$ and by none otherwise; neither describes a wall.

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

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

The point $(4,0)$. Evaluate $2(4)+0=8$. Since , 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 $\le$ 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 $3x_1-x_2+4x_3\le 10$ and the point $(1,2,1)$: $3-2+4=5\le 10$, so it is allowed. There is no picture, and none is needed.

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

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

In ${\mathbb{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 ${\mathbb{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.