Degenerate case of linear programming duality?

Question

Let's say we have a maximization linear program that looks like this: maximize $\vec{c}\vec{x}$, subject to $\matrix{A}\vec{x} \leq 0$, $\vec{x} \geq 0$. If we take the dual, we have "minimize $0\vec{y}$, subject to $\vec{y}\matrix{A}\geq\vec{c}, \vec{y}\geq 0$". I'm particularly bothered by the "minimize $0$" part of the dual program - but does the duality theorem still hold - that is: is it true that if there is a $\vec{y}$ that is feasible for the dual program, then for all $\vec{x}$ that is feasible for the primal program, $\vec{c}\vec{x} \leq 0$?

Thanks!

Answer 1

Yes, the duality theorem holds. "Minimize 0" makes your life much easier, because you know exactly what the optimal value of the dual program is...

Answer 2

Igor is correct, and more can be said about this primal-dual pair of linear programs: because the primal maximization problem is homogeneous (i.e. zero constant terms in the constraints), the common optimal objecive value for both problems is either zero or $+\infty$:

1. If there exists a feasible solution $\vec{x}$ with a positive objective value, i.e. with $A \vec{x} \le 0$ and $\vec{c}\vec{x} > 0$, then this solution can be scaled by any positive constant $\lambda > 0$ (because $A (\lambda \vec{x}) \le 0$), which shows that the problem is unbounded ($\vec{c}(\lambda \vec{x})$ tends to $+\infty$ as $\lambda \to +\infty$).
2. If no feasible solution with negative objective value exists, then $\vec{x}=0$ is an optimal solution, and the optimal objective value is zero.

Using duality theory, one can check that the first case corresponds to an infeasible dual problem (no $\vec{y}\ge 0$ such that $\vec{y} A \ge \vec{c}$), while the second situation happens as soon as the dual problem admits a feasible solution.