# When does strong duality fail in linear programming?

When does strong duality fail in linear programming? I have considered the case when both primal and dual solutions are infeasible, but then there are no optimal solutions at all.

• Can I ask why you deleted this question? For future reference, we normally prefer that you avoid deleting your question after you've received an answer -- that might be considered impolite to people who take the time to answer. Part of our mission is to build up an archive of high-quality questions and answers that might help others in the future. Deleting your question prevents others from benefiting from the answer; people writing an answer might be hoping that others would also be able to benefit. I realize this might not be obvious at first glance!
– D.W.
Commented Apr 3, 2017 at 16:56

The strong duality theorem of linear programming states that (quoted from "Algorithms" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, 2006) "If a linear program has a bounded optimum, then so does its dual, and the two optimum values coincide." Hence, it never fails.

There is a very good exercise - 5.23 - in Boyd's book on Convex Optimization (the solution might also help).

They prove that strong duality holds for the following LP and its dual provided at least one of the problems is feasible. In other words, the only possible exception to strong duality occurs when $p^*= \infty$ and $d^* = − \infty$.

LP:

$\min c^Tx$

st $Ax=b$

DUAL:

$max −b^Tz$

st $A^T z + c = 0$ and $z \succeq0$