\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Real Halfspaces
Real Balls
Affine Set Dimensions
Topological Interiors
Needed by:
Linear Optimization Problems
Real Convex Sets and Halfspaces
Real Polyhedra Vertices
Sheet PDF
Graph PDF

Real Polyhedra


A polyhedron (or real polyhedron, or convex polyhedron) is a set $P \subset \R ^n$ for which there exists $A \in \R ^{m \times n}$ and $b \in \R ^{m}$ satisfying

\[ P = \Set{x \in \R ^n}{Ax \leq b}. \]

In other words, a polyhedron is an intersection of finitely many halfspaces. If $A$ and $b$ are rational, then $P$ is called a rational polyhedron.

A polyhedron $P$ is a polytope (a real polytope) if it is bounded. In other words, there exists $x_0 \in P$ and $M > 0$ such that

\[ P \subset B_M(x_0) = \Set{x }{\norm{x - x_0} < M} \]

Here $B_M(x_0)$ denotes the open ball of radius $M$, as usual.

As usual, the dimension of a polyhedron $P$ is the dimension of the affine hull of $P$, which we denote by $\dim P$. $P$ is called full-dimensional if $\dim P = n$. An equivalent condition for $P$ to be full-dimensional is that there exist an interior point of $P$ (as a subset of $\R ^n$)


Caution: some authors have a more relaxed notion of polyhedra, which does not require the polyhedra be convex.

Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view