Polyhedra, faces, and extreme points

A polyhedron is an intersection of finitely many closed affine halfspaces, possibly with equalities expressed as two inequalities. It is convex and closed, but it need not be bounded, full dimensional, or nonempty. A bounded polyhedron is a polytope. An inequality can be redundant without changing the region: adding a weaker resource limit increases the written model size without introducing a new geometric boundary. Dimension is measured inside the affine hull, so a line segment in the plane is a one-dimensional polytope rather than a defective polygon.

For a nonempty polyhedron $P$, a supporting objective with finite attained maximum $\alpha$ exposes the face $F=\{x\in P:c^Tx=\alpha\}$. The defining property of a face is that if an interior point of a segment between two feasible points lies in the face, both endpoints lie there too. A vertex is a face containing one point. An edge is a one-dimensional face, which may be unbounded for a general polyhedron. A supporting objective level hyperplane parallel to an edge can therefore have many optimal solutions; uniqueness is an additional property, not a consequence of linearity.

At a feasible point, call a row active when its inequality holds with equality. The point is extreme precisely when the active row normals span the ambient space. If the normals fail to span, choose a nonzero direction orthogonal to them. Inactive inequalities have positive slack; because there are finitely many, sufficiently small steps in both signs of that direction remain feasible. The original point is then the midpoint of two distinct feasible points and is not extreme. This argument uses all written inequalities, including equalities represented by opposite rows.

Conversely, suppose the active normals span and the point is a strict convex combination of feasible points. Each active inequality must be tight at both endpoints, because a weighted average of two quantities at most its bound can equal that bound only when both equal it. The endpoint difference is orthogonal to every active normal and is therefore zero. This proves the rank criterion, rather than merely inferring a corner from a picture. More than the necessary number of constraints may be tight; the extra constraints indicate degeneracy, not a higher-dimensional vertex.

A nonempty polytope is the convex hull of its finitely many vertices, so a linear objective reaches a maximum at at least one vertex. The same conclusion holds for a nonempty pointed polyhedron, meaning one containing no line, whenever the objective is bounded above. Unboundedness of the set alone does not imply an unbounded objective. On the nonnegative quadrant, maximizing the negative first coordinate has finite value zero and infinitely many optimizers. Conversely, maximizing the first coordinate has an improving ray and no finite optimum.

Without pointedness, a finite optimum need not occur at a vertex because there may be none. On the whole horizontal line, the constant zero objective is optimized everywhere. Recession directions make the distinction algebraic: if $Ad\le0$, then adding any nonnegative multiple of $d$ to a feasible point stays feasible. If also $c^Td>0$, the maximization objective is unbounded. This provides a short positive certificate. Finding no obvious ray by inspection is not a proof of boundedness; a dual feasible vector will later provide that proof systematically.