I am wondering in what cases a nonzero duality gap exists and what causes it to exist? (simply in what cases the optimal value for primal is not equal to the optimal objectives value for the dual) In LP we have the strong duality so the gap is basically zero asked 09 Mar '12, 18:34 Igor Pangal 
One answer is Slater's condition for convex optimization. Slater's constraint qualification requires that there exist a feasible point that is strictly interior to all inequality constraints. If your problem is a convex program that satisfies this requirement, then the duality gap is zero. Bertsekas's nonlinear programming text covers this in detail. answered 10 Mar '12, 14:22 Matthew Salt... ♦ 
You mention already the most important special case: LP duality. The strong duality theorem tells us that the duality gap is zero. This is not the case (e.g.,) for integer programs in general. You can formally still formulate programs that are dual to each other (e.g., the maximum independent/stable set problem and the minimum clique cover problem in an arbitrary graph), but the duality gap will be positive in general. One reason (the complexity theory reason) behind this is: the strong duality theorem of linear programming provides us with a polynomial certificate of optimality or nonoptimality. You just compute the objective of the primal and dual solution and know whether you are optimal or not. If a similar test would be possible (in polynomial time) for integer programs, you would prove or disprove optimality in polytime, contradicting that integer programming is NPhard in general. Bottomline (edited)
answered 10 Mar '12, 05:43 Marco Luebbecke ♦ 1
@Marco: Correct me if I'm wrong, but I think your reasoning is implicitly assuming that P != NP.
(10 Mar '12, 06:15)
Ehsan ♦
@Ehsan, :) ah yes, OF COURSE. This is what I assume, as most others, I guess.
(10 Mar '12, 07:49)
Marco Luebbecke ♦
@Marco: Actually, this is a good assumption. If it turns out otherwise, most of us, specially those working on combinatorial optimization, would be out of jobs.
(10 Mar '12, 07:59)
Ehsan ♦
yes, @Ehsan. It would be very surprising if P=NP. But, even if there was a proof, and even it was constructive, would it lead to a practicable computational procedure to solve hard problems? Maybe, our jobs are safe for some time ;)
(10 Mar '12, 08:12)
Marco Luebbecke ♦
1
I think the complexity argument here is wrongway'round. The fact that solving the primal produces a certificate for the dual is a consequence of strong duality, not a reason for it. There are plenty of problems with polynomial algorithms (hence polynomial certificates of primal nonoptimality) that don't have strong duality. For primal and dual in NP, strong duality implies a polynomial certificate for nonoptimality, but the converse isn't true. (A technical point: "optimality" here means "meets a threshold".)
(10 Mar '12, 14:01)
Matthew Salt... ♦
@Matthew, I did not speak about NP, but NPhard. If you have an NPhard problem, you cannot expect a duality gap of zero  unless P=NP. I did not claim that a polytime algorithm has a zero duality gap as a consequence.
(10 Mar '12, 14:28)
Marco Luebbecke ♦
2
@Marco, P = NP implies NP = coNP, but the converse doesn't hold. Having a zero duality gap for an NPC problem would imply NP = coNP (also considered unlikely), but that wouldn't in turn imply P = NP. But yes, we were making different points. Mine was that even being in P wouldn't guarantee a zero duality gap.
(10 Mar '12, 16:41)
Matthew Salt... ♦
showing 5 of 7
show 2 more comments

In conic optimization finite nonzero duality gap is possible. However, if both the primal and dual of a conic optimization problem is strictly feasible, then the duality gap is zero. answered 10 Mar '12, 14:17 Rune Sandvik 
Interestingly I was working on this for another report. I have used Matthew's response and expanded it a little.
answered 11 Mar '12, 06:57 Mark ♦ 