Polyhedra
Half-spacesDefinitionA half-space is a set defined by a single affine inequality. Precisely, a half-space in ![]() where A half-space separates the whole space in two halves. The complement of the half-space is the open half-space GeometryA half-space separates the whole space in two halves. The complement of the half-space is the open half-space
Example: A half-space in Link with linear functionsHyperplanes correspond to level sets of linear functions. Half-spaces represent sub-level sets of linear functions: the half-space above describes the set of points such that the linear function PolyhedraDefinitionA polyhedra is a set described finitely many affine inequalities. Precisely, a polyhedron is a set of the form ![]() where A polyhedron can be expressed as the intersection of (finitely many) half-spaces: ![]() GeometryA polyhedron is a convex set, with boundary made up of ‘‘flat’’ boundaries (the technical term is facet). Each facet corresponds to one of the hyperplanes defined by Note that not every set with flat boundaries can be represented as a polyhedron: the set has to be convex. Matrix notationIt is often convenient to describe a half-space in matrix notation: ![]() where ![]() Here, we adopted the component-wise inequality convention: the notation Example: A polyhedron in Equality constraints are allowedSets defined by affine inequalities and equalities are also polyhedra. Indeed, consider the set ![]() where The set above can be expressed as an ‘‘inequalities-only’’ polyhedron: ![]() which can be put in the standard form for polyhedra, with augmented matrices and right-hand side vector. Example: The probability simplex. |