Given the definition $ P = \{ x \mid Ax \preceq b, Cx =d\} $ for a polyhedron, why do we need the $Cx =d$ term

convex-analysisdiscrete geometrypolyhedrapolytopes

$$ P = \{ x \mid Ax \preceq b, Cx =d\} $$ is the notation for a polyhedron provided in Boyd & Vandenberghe's Convex Optimization. The example they give is a five sided polyhedron, with normal vectors provided by the vectors contained in $A$.

In this case, what additional information is encoded in the set of equalities $Cx = d$? Is the intersection of the regions described by $Ax \preceq b$ not enough to describe the region $P$?

enter image description here

Best Answer

To make my comment into an answer:$$P = \{ x | Ax \leq b, Cx =d\}=\{x | \begin{pmatrix} A\\ C \\ -C\end{pmatrix}x\leq\begin{pmatrix}b\\d\\-d \end{pmatrix}\}$$So the $Cx=d$ in your definition is just describing more inequalities. Whether they are redundant or not, depends on the polyhedron.

Related Question