How does $Ax = b$ define a feasible region of half spaces?

Question

When a linear program is formulated like this:

$\begin{align} \text{minimise}\quad &c^Tx\\ \text{subject to}\quad &Ax \ge b \end{align}$

With $c\in \mathbb{R}^{|x|}$, $A \in \mathbb{R}^{n \times |x|}$ (where $n$ is the number of constraints) and $b \in \mathbb{R}$, we can say that the feasible region is the intersection of the half spaces associated with all of the linear inequality constraints.

However, sometimes I see linear programs formulated like this:

$\begin{align} \text{minimise}\quad &c^Tx\\ \text{subject to}\quad &Ax = b \end{align}$

How can we use this formulation to define a feasible region? If $b \in \mathbb{R}$, then the constraints define a set of lines, instead of half spaces. Do we now take $b \subseteq \mathbb{R}$ instead of some single element? Or, is the implication that we can write $x = y \Leftrightarrow x \ge y \land x \le y$, so the lines $Ax = b$ each define the boundary of a half space? If so, then how do we determine on which side of the boundary the feasible region lies?

Answer 1

If you like the first form better, you can write condition $Ax=b$ as $$\begin{bmatrix}A\\ -A\end{bmatrix}x\ge \begin{bmatrix}b\\ -b\end{bmatrix}$$

and work just like you would in the first instance with $2n$ constraints instead of $n$.

Answer 2

First, a common convention in LP theory is to work with positive vectors (each component is positive).

Gae. S. showed that you can go from an equality constraint to an inequality from a practical point of view by making a change of variable. However, there is a theorem in convex optimization (LP are convex problems) based on subgradient telling you that every optimal solution of the problem lies on the boundary of the feasible region for LP problems. Hence the two problems are equivalent in the sense they will always lead to the same solutions, even if one has a way larger feasible region.