why polyhedron was defined by linear equalities and inequalities?

Question

I am learning convex optimization, and confused by the definition of polyhedron.

it's easy understanding the polyhedron is defined as the solution of a finite number of linear inequalities. But why there is also linear equalities in the definition of convex optimization, section 2.2.4,page 31:

polyhedron is defined as the solution set of a finite number of linear equalities and inequalities: $$ p=\{ x| a_j^T \leq b_j, j=1, ..., m, c_j^T x = d_j, j=1, ..., p\} $$

linear equalities define hyperplane, not polyhedron.

As my understing: linear equalities define hyperplane, inequalities define halfspaces, intersection of finite halfspaces (it's finite linear inequalities) define polyhedron. But why there is a linear equalities constraint in the definition of the convex optimization book. it seems unreasonable.

As illustrated in the book after definition, Affine sets (e.g., subspaces, hyperplanes, lines), rays, line segments, and halfspaces are all polyhedra. So, the equalities and inequalities can't be true same time?

anyone can help?

Answer 1

Linear equations are allowed for convenience; we could define polyhedra using inequalities alone. For example, $$\{(x,y) \in \mathbb R^2 : x \ge 0, y \ge 0, x+y = 1\}$$ is how we'd usually define the line segment with endpoints at $(1,0)$ and $(0,1)$ - which we do consider a polyhedron. But we could define the same set as $$\{(x,y) \in \mathbb R^2 : x \ge 0, y \ge 0, x+y \ge 1, x+y \le 1\}$$ which doesn't have any equations in it.

We do sometimes want to say that something is a polyhedron with nonempty interior: that's a polyhedron $P$ with a point $\mathbf x \in P$ such that for some $r>0$, the ball of radius $r$ around $\mathbf x$ is entirely contained in $P$.

If a polyhedron has nonempty interior, it can't possibly have any linear equations in its definition. But as the example above shows, the reverse is not true: a polyhedron defined using inequalities only might still have empty interior.

Answer 2

Take a you look at the dual linear program of a linear program, how it behaves w.r. to inequalities or equalities in the original problem. Yes, we could write an equivalent linear problem with only inequalities, but why not be expedient.