The Duality “Gap” in Linear Programming

Wait… what?  Doesn’t the strong duality theorem imply that there is no duality gap in linear programming?  Mostly, yes, although there is a sense in which there actually is a duality gap; it occurs when the primal and dual problems are both infeasible.  To see this, let’s take a closer look at what the strong duality theorem is saying.

Strong Duality Theorem: If x is an optimal solution for the primal problem with objective c, and y is an optimal solution for the dual problem with objective b, then {\bf c^T x} = {\bf y^T b}.

So if the primal and dual problems have optimal solutions, then the optimal objective function values must be equal.  But what if either the primal or the dual doesn’t have an optimal solution?  The weak duality theorem tells us something about this.

Weak Duality Theorem: If x is a feasible solution for a maximizing primal problem with objective c, and y is a feasible solution for its minimizing dual problem with objective b, then {\bf c^T x} \leq {\bf y^T b}.

If the primal problem is unbounded, then a feasible solution to the dual would contradict weak duality.  Thus weak duality says that primal unboundedness implies dual infeasibility.  Similarly, dual unboundedness implies primal infeasibility.

But there’s one more case that we haven’t considered: Is it possible for both the primal and dual problems to be infeasible?  Yes, it is.  Here’s an example.

Primal:

Maximize x_1 +2x_2
subject to
x_1 + x_2 = 1 \\  x_1 + x_2 = 2.

Dual:

Minimize y_1 +2y_2
subject to
y_1 + y_2 = 1 \\  y_1 + y_2 = 2.

The primal and dual are both clearly infeasible.  (In fact, except for maximizing vs. minimizing, they are the same problem!)

The case in which both primal and dual problems are infeasible is the sense in which there is a duality gap.  If we take the view that the maximum of a function over the empty set is -\infty, and the minimum of a function over the empty set is \infty, then when both problems are infeasible we have a duality gap of \infty.

Advertisements
This entry was posted in linear programming, optimization. Bookmark the permalink.

3 Responses to The Duality “Gap” in Linear Programming

  1. Chaitanya Awasthi says:

    Very interesting read, Prof. Spivey. However, can you please elaborate on the fact that the maximum of function over an empty set is -infinity whereas the minimum of a function over an empty set is + infinity? Seems a little counter-intuitive to me. Thanks!

    • mzspivey says:

      It’s kind of a definitional thing. A more precise term than maximum would be supremum. A supremum of a set S of real numbers is the smallest real number x having the property that for all elements y in S, x \geq y. If S is empty, then every real number x vacuously has the property that “for all elements y in S, x \geq y.” Since there is no smallest real number x, if you’re going to give the maximum of an empty set any kind of meaning it would have to be negative infinity. The same idea holds for the minimum of an empty set being positive infinity.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s