# What happens if we remove the non-negativity constraints in a linear programming problem?

As we know, a standard way to represent linear programs is

$$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$

with the associated dual

$$\begin{array}{ll} \text{minimize} & b^T y\\ \text{subject to} & A^T y \geq c\\ & y \geq 0\end{array}$$

We know that in such a case, either both problem have an optimum (at the same point) or one is unfeasible and the other unbounded. Now suppose in these definitions, I remove the non-negativity constraints on $x$ and $y$. I then have two questions.

Firstly, in such a case, can an optimum be achieved with an unbounded feasible set? If so, does that mean the dual will have the same optimum?

Secondly, what would be a way to check if an optimum is attained if the feasible set is unbounded? Will checking at the vertices only suffice in this case?

If you remove the non-negativity constraint on $x$ then the constraints of the dual program become $A^T y = c$. Similarly, if you drop the non-negativity constraint on $y$ your primal constraints become $A x = b$.
For these primal dual pairs of LPs strong duality still holds. That means that if your primal LP has a bounded objective value which is achieved by a solution $x^*$ then there exists a dual feasible solution $y^*$ such that both objective values coincide.
On a side note: You can always transform a problem without non-negativity constraints to one with such constraints by replacing every variable $x$ which needs not be non-negative by two variables $x^+$ and $x^-$, both of which must be non-negative. In every constraint of the LP $x$ is replaced by $(x^+ - x^-)$. The idea behind this replacement is that $x^+$ is the positive part of $x$ and $x^-$ is the negative part.