Duality of linear programs without non-negativity constraints

Question

It seems that every theory of duality I can find in the theory of linear programs employs the fact that the variables $x_i$ in the program are non-negative. Is there a theory of duality, giving us the complementary slackness property, etc, where the variables of a linear program are not necessarily non-negative, but instead can take on unbounded real values?

Answer 1

Yes, you can find the dual of an LP in which variables have general upper and lower bounds, some of which might be $\pm \infty$. This is discussed in many textbooks on linear programming.

Note that if all of the variables are free (no upper or lower bounds) than either the LP is infeasible, the LP is unbounded or all feasible solutions have the same objective value. The dual of such an LP is of very little interest.

To see this, consider the linear system of equations $Ax=b$. Either

1. There is a unique solution to $Ax=b$, which is obviously optimal (but not very interesting.) In this case, all feasible solutions have the same objective value.

or

2. There are no solutions to $Ax=b$, and the LP is infeasible.

or

3. There are infinitely many solutions to $Ax=b$ which form an affine set (some sort of hyperplane in $R^{n}$. Then either

3.a. The vector $c$ is orthogonal to hyperplane of feasible solutions, in which case every solution to the LP has the same (optimal) objective value.

or

3.b. The vector $c$ is not orthogonal to the hyperplane of feasible solutions, in which case the LP is unbounded.

Answer 2

Let's apply the general dual problem construction to the LP \begin{align} \text{minimize} & \quad \langle c, x \rangle \\ \text{subject to} & \quad Ax = b, \\ & \quad Cx \leq d. \end{align} The Lagrangian is \begin{align} L(x,z,w) &= \langle c, x \rangle + \langle z,Ax - b \rangle + \langle w, Cx - d \rangle \\ &= \langle c + A^T z + C^T w, x \rangle - \langle z,b \rangle - \langle w, d \rangle. \end{align} The dual function is \begin{align} G(z,w) &= \inf_x L(x,z,w) \\ &= \begin{cases} -\langle z,b \rangle - \langle w,d \rangle \quad \text{if } c + A^T z + C^T w = 0, \\ -\infty \quad \text{otherwise.} \end{cases} \end{align} The dual problem is \begin{align} \text{maximize}_{z,w} & \quad - \langle z,b \rangle - \langle w, d \rangle \\ \text{subject to} & \quad c + A^T z + C^T w = 0,\\ & \quad w \geq 0. \end{align} The KKT conditions are: \begin{align} Ax &= b ,\\ Cx & \leq d, \\ c + A^T z + C^T w &= 0, \\ w &\geq 0, \\ w_i(Cx - d)_i &= 0 \quad \text{for all }i. \end{align}