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 .

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 .

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

subject to

*Dual:*

Minimize

subject to

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 , and the minimum of a function over the empty set is , then when both problems are infeasible we have a duality gap of .

### Like this:

Like Loading...

*Related*

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!

It’s kind of a definitional thing. A more precise term than

maximumwould besupremum. A supremum of a setSof real numbers is the smallest real numberxhaving the property that for all elementsyinS, . IfSis empty, then every real numberxvacuously has the property that “for all elementsyinS, .” Since there is no smallest real numberx, 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.That makes a lot of sense, Prof. Spivey. Thank you for clarifying that out for me.