Strong Duality Theorem: Conditions and Implications

1. The Strong Duality Theorem

The Strong Duality Theorem closes the gap left by weak duality. It makes a definitive statement about the relationship between the optimal values of the primal and dual problems.

Let's begin with a concise statement of the theorem from the video we've used previously.

As the video states, the theorem connects the existence of a finite optimal solution in the primal to the existence of one in the dual.

Theorem (Strong Duality): If a linear program has a finite optimal solution, then so does its dual, and their optimal objective values are equal.

Let's denote the optimal value of the primal as $z^{\ast }$ and the optimal value of the dual as $v^{\ast }$. The theorem states:

This simple equation is incredibly powerful. It confirms that the process of finding the tightest upper bound on the primal (which is what the dual problem does) is not just an approximation—it leads to the exact optimal value. There is no duality gap.

2. Conditions and Implications: The Full Picture

The Strong Duality Theorem does more than just equate optimal values. It provides a complete characterization of the possible relationships between a primal LP and its dual. There are only four possibilities.

The following text provides an excellent and comprehensive discussion of these properties, culminating in a table that summarizes all possible scenarios.

Let's summarize the key relationships from that reading. For any primal-dual pair of LPs, exactly one of the following must be true:

1. Both have finite optimal solutions. In this case, their optimal values are equal. This is the primary statement of the Strong Duality Theorem.
2. The primal is unbounded, and the dual is infeasible. We saw this was a direct consequence of the Weak Duality theorem: if the dual had a feasible solution, it would provide an upper bound on the primal, contradicting its unboundedness.
3. The dual is unbounded, and the primal is infeasible. This is the symmetric case to the one above.
4. Both the primal and the dual are infeasible. As shown in Table 4.2 from the reading, this scenario is also possible.

This gives us a complete classification. Notice that it is impossible, for example, for the primal to be unbounded and the dual to also be unbounded, or for the primal to be unbounded while the dual has a finite optimal solution.

3. Outline of the Proof

Since you are interested in the theoretical underpinnings, let's explore how the Strong Duality Theorem is proven. The proof in the previous reading relies on properties of the simplex method. Here, we will look at a more fundamental proof that uses a result called Farkas' Lemma.

Farkas' Lemma deals with the question of when a system of linear equations has a non-negative solution. It states that for a matrix $A$ and a vector $b$, exactly one of two specific systems of equations/inequalities has a solution. This "either/or" structure makes it a perfect tool for proofs by contradiction in linear programming.

The following reading states Farkas' Lemma and then uses it to prove the Strong Duality Theorem by systematically analyzing the case where both primal and dual are feasible.

Let's break down the logic of that proof by contradiction:

1. Assumption: Assume both the primal and dual problems are feasible. By weak duality, we know they are both bounded. Let $\gamma$ be the optimal value of the dual (minimization) problem.
2. Contradictory Hypothesis: Suppose the optimal primal value is strictly less than $\gamma$. This is equivalent to saying there is no feasible primal solution $\mathbf{x}$ whose value ${\mathbf{c}}^T\mathbf{x}$ is greater than or equal to $\gamma$.
3. Applying Farkas' Lemma: This "no solution exists" statement can be written as a system of linear inequalities with no solution. Farkas' Lemma tells us that if this system has no solution, a corresponding alternative system must have a solution.
4. Constructing a Contradiction: The proof then shows that the solution to this alternative system can be used to construct a new feasible solution for the dual problem.
5. The Punchline: The objective value of this new dual solution is shown to be strictly less than $\gamma$. This contradicts our initial assumption that $\gamma$ was the optimal (minimum) value of the dual.
6. Conclusion: Therefore, our hypothesis must be false. The optimal primal value cannot be less than $\gamma$. Since Weak Duality already tells us it cannot be greater, the primal and dual optimal values must be equal.

This is a beautiful line of reasoning that establishes the equality at the heart of linear programming, without relying on any specific algorithm.

Conclusion

In this lesson, we have moved from weak to strong duality, establishing the central theorem of linear programming.

Key Takeaways:

• Strong Duality Theorem: If an LP has a finite optimal solution, so does its dual, and their values are identical. There is no duality gap.
• Complete Classification: The relationship between a primal and dual LP falls into one of four categories: (1) both optimal, (2) primal unbounded/dual infeasible, (3) dual unbounded/primal infeasible, or (4) both infeasible.
• Proof: The theorem can be proven fundamentally using Farkas' Lemma to show that a duality gap would lead to a logical contradiction.
• Complementary Slackness: A direct consequence of strong duality ($z^{\ast }=v^{\ast }$) is a set of conditions known as complementary slackness. These conditions provide a precise relationship between the optimal primal variables (${\mathbf{x}}^{\ast }$) and optimal dual constraints, and between optimal dual variables (${\mathbf{y}}^{\ast }$) and optimal primal constraints. They give a powerful method for verifying optimality.

Preview of the next lesson:

We have now assembled all the necessary machinery from the world of linear programming. In the next module, we will return to game theory. You will see how to formulate a player's problem of finding their best mixed strategy in a zero-sum game as a linear program. We will then construct the dual of this LP and discover that it is precisely the other player's problem. The Strong Duality Theorem will then allow us to prove the Minimax Theorem directly and elegantly.