# When is the quality gap non-zero

 2 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 147●2●10 accept rate: 0%

 3 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... ♦ 4.7k●3●10 accept rate: 17%
 2 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 non-optimality. 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 NP-hard in general. Bottomline (edited) NP-hard problems => duality not zero in general strong duality theorem for your problem (e.g., LP) => duality gap always zero polytime solvable problems need not have a zero duality gap (as @Matthew remarked) answered 10 Mar '12, 05:43 Marco Luebbecke ♦ 3.4k●1●6●15 accept rate: 16% 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 wrong-way-'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 non-optimality) that don't have strong duality. For primal and dual in NP, strong duality implies a polynomial certificate for non-optimality, 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 NP-hard. If you have an NP-hard 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 = co-NP, but the converse doesn't hold. Having a zero duality gap for an NPC problem would imply NP = co-NP (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
 0 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 101●2 accept rate: 0%
 0 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 ♦ 3.6k●2●25●50 accept rate: 9%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×17