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

Question

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?

Answer 1

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.

Checking only the vertices will not suffice to check if there an optimum is attained. You also have to check the extreme rays to make sure there that the optimum is attained. If you already know the (bounded) optimal objective then you will find an optimal solution at one of the vertices.

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.