# Removing a Non Negativity Constraint in a Linear Programming Problem

Let's say I have a linear programming problem, i.e.

$$\begin{array}{rl} \text{maximize} & c^T x \\ \text{subject to} & {\bf A} x \le b \end{array}$$

without the non-negativity constraint on $$x$$ (i.e. $$x \ge 0$$). However, whenever I read about the linear programming, this constraint was always included. Why is that? To me, the statement above is equivalent to:

$$\begin{array}{rl} \text{maximize} & c^T x \\ \text{subject to} & {\bf A} x \le b \\ \text{and} & x \ge 0 \lor x \le 0 \end{array}$$

which can be considered as two, separate problems: one for $$x \ge 0$$ and one for $$x \le 0$$ (where the solutions can be combined into one). Also, the problem with the constraint $$x \le 0$$ can be transformed into the first one by introducing $$x' = -x$$. This means that I could use linear programming algorithms for solving problems without the non-negativity constraints. Is my reasoning correct?

Keep in mind that $$\mathbf x$$ is a vector here. So it's not true that one of the two options $$\mathbf x\ge \mathbf 0$$ (every component of $$\mathbf x$$ is nonnegative) and $$\mathbf x \le \mathbf 0$$ (every component of $$\mathbf x$$ is nonpositive) is necessarily true. We could have a mix.
Whenever we have a linear program \begin{align} \max\ & \mathbf c^{\mathsf T} \mathbf x \\ \text{s.t. } & A\mathbf x \le \mathbf b \end{align} we can turn it into a program in nonnegative variables by substituting $$\mathbf x = \mathbf x^+ - \mathbf x^-$$, where $$\mathbf x^+ \ge \mathbf 0$$ and $$\mathbf x^- \ge 0$$. (Any real number can be written as the difference of two nonnegative numbers.) So you can use LP algorithms that assume nonnegativity to solve such a program, but you will have to deal with twice as many variables.
Another option when dealing with a program like this one is to take the dual. The dual will have the form \begin{align} \min\ & \mathbf u^{\mathsf T} \mathbf b \\ \text{s.t. } & \mathbf u^{\mathsf T}A = \mathbf c^{\mathsf T} \\ & \mathbf u \ge \mathbf 0 \end{align} and so you have nonegativity constraints there.