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%20Pangal's gravatar image

Igor Pangal
147210
accept rate: 0%


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.

link

answered 10 Mar '12, 14:22

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

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)

  1. NP-hard problems => duality not zero in general
  2. strong duality theorem for your problem (e.g., LP) => duality gap always zero
  3. polytime solvable problems need not have a zero duality gap (as @Matthew remarked)
link

answered 10 Mar '12, 05:43

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

edited 10 Mar '12, 14:33

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

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.

link

answered 10 Mar '12, 14:17

Rune%20Sandvik's gravatar image

Rune Sandvik
1012
accept rate: 0%

edited 10 Mar '12, 14:43

Interestingly I was working on this for another report. I have used Matthew's response and expanded it a little.

alt text alt text alt text

link

answered 11 Mar '12, 06:57

Mark's gravatar image

Mark ♦
3.6k22550
accept rate: 9%

edited 11 Mar '12, 07:00

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 09 Mar '12, 18:34

Seen: 2,189 times

Last updated: 11 Mar '12, 07:00

OR-Exchange! Your site for questions, answers, and announcements about operations research.