Weak Duality Theorem in LP

1. From Upper Bounds to a Formal Theorem

Let's quickly revisit the core intuition from our last session. For a maximization problem (the primal), we can find an upper bound on its optimal value by taking a non-negative linear combination of its constraints. The dual problem is the search for the best such combination—the one that yields the tightest (smallest) upper bound.

The video below provides a quick, concrete example of this process, which serves as an excellent warm-up for the formal proof to come.

This process of finding bounds isn't just a useful trick; it's a guaranteed property. The Weak Duality Theorem formalizes this guarantee.

2. The Weak Duality Theorem

Let's consider a primal-dual pair in the standard form we've been using:

Primal (P)

Dual (D)

Theorem (Weak Duality): If $\mathbf{x}$ is any feasible solution to the primal program (P) and $\mathbf{y}$ is any feasible solution to the dual program (D), then:

In simple terms, the objective value of any feasible solution to the maximization primal is less than or equal to the objective value of any feasible solution to the minimization dual. This means the entire set of possible primal objective values lies to the left of the entire set of possible dual objective values on the number line.

3. Proof of the Weak Duality Theorem

The proof for this theorem is elegant and relies directly on the definitions of primal and dual feasibility. Given your background, the chain of logic using matrix-vector operations should be straightforward.

First, let's watch a short video that walks through the proof.

Now, let's carefully write out that same proof. Our goal is to show that ${\mathbf{c}}^T\mathbf{x}\le {\mathbf{b}}^T\mathbf{y}$.

1. We start with the primal objective, ${\mathbf{c}}^T\mathbf{x}$.
2. From the dual constraints, we know that ${\mathbf{A}}^T\mathbf{y}\ge \mathbf{c}$. We can also write this as $\mathbf{c}\le {\mathbf{A}}^T\mathbf{y}$. Since $\mathbf{x}$ is a feasible primal solution, we know $\mathbf{x}\ge 0$. Multiplying an inequality by non-negative values preserves the direction of the inequality. Therefore, we can left-multiply by ${\mathbf{x}}^T$ (or right-multiply by $\mathbf{x}$ after transposing) to get: $${\mathbf{c}}^T\mathbf{x}\le ({\mathbf{A}}^T\mathbf{y}{)}^T\mathbf{x}$$
3. Using the property of transposes that $(\mathbf{AB}{)}^T={\mathbf{B}}^T{\mathbf{A}}^T$, we can simplify the right-hand side: $({\mathbf{A}}^T\mathbf{y}{)}^T={\mathbf{y}}^T({\mathbf{A}}^T{)}^T={\mathbf{y}}^T\mathbf{A}$. This gives us: $${\mathbf{c}}^T\mathbf{x}\le {\mathbf{y}}^T\mathbf{Ax}$$
4. Now, we use the primal constraints. We know $\mathbf{Ax}\le \mathbf{b}$. Since $\mathbf{y}$ is a feasible dual solution, we know $\mathbf{y}\ge 0$. We can left-multiply by ${\mathbf{y}}^T$ without flipping the inequality: $${\mathbf{y}}^T(\mathbf{Ax})\le {\mathbf{y}}^T\mathbf{b}$$
5. Combining the steps, we have the full chain: $${\mathbf{c}}^T\mathbf{x}\le {\mathbf{y}}^T\mathbf{Ax}\le {\mathbf{y}}^T\mathbf{b}$$
6. Finally, note that ${\mathbf{y}}^T\mathbf{b}$ is a scalar (a 1x1 matrix), so it is equal to its transpose, $({\mathbf{y}}^T\mathbf{b}{)}^T={\mathbf{b}}^T\mathbf{y}$. This completes the proof: $${\mathbf{c}}^T\mathbf{x}\le {\mathbf{b}}^T\mathbf{y}$$

For a slightly different presentation of the same proof and its surrounding context, you can review the following text.

4. Consequences of Weak Duality

The theorem itself is simple, but it has several powerful corollaries that are immediately useful.

• Corollary 1: If the primal problem is unbounded (i.e., its objective can be made arbitrarily large), then the dual problem must be infeasible (have no solutions). Why? If the dual had even one feasible solution $\mathbf{y}$, its objective value ${\mathbf{b}}^T\mathbf{y}$ would be a finite upper bound on the primal, which contradicts the primal being unbounded.

• Corollary 2: Symmetrically, if the dual problem is unbounded (its objective can be made arbitrarily small), then the primal problem must be infeasible.

• Corollary 3 (Optimality Certificate): If you find a feasible primal solution ${\mathbf{x}}^{\ast }$ and a feasible dual solution ${\mathbf{y}}^{\ast }$ such that their objective values are equal (${\mathbf{c}}^T{\mathbf{x}}^{\ast }={\mathbf{b}}^T{\mathbf{y}}^{\ast }$), then both ${\mathbf{x}}^{\ast }$ and ${\mathbf{y}}^{\ast }$ must be optimal solutions for their respective problems. This is because weak duality guarantees no primal solution can be greater than ${\mathbf{b}}^T{\mathbf{y}}^{\ast }$ and no dual solution can be less than ${\mathbf{c}}^T{\mathbf{x}}^{\ast }$.

This final corollary is extremely important. It gives us a way to "certify" that a solution is optimal without having to compare it to every other possible solution.

The following reading elaborates on these points.

Conclusion

In this lesson, we have formally established the relationship between a primal LP and its dual.

Key Takeaways:

• Weak Duality Theorem: For any feasible primal solution $\mathbf{x}$ and any feasible dual solution $\mathbf{y}$, the inequality ${\mathbf{c}}^T\mathbf{x}\le {\mathbf{b}}^T\mathbf{y}$ holds (for a max primal).
• The proof is a direct consequence of the way the primal and dual problems are constructed.
• This theorem provides an optimality certificate: if the objective values of a feasible primal-dual pair are equal, both solutions must be optimal.

Preview of the next lesson:

Weak duality tells us that the primal optimal value is less than or equal to the dual optimal value. This leaves open the possibility of a "duality gap" between them. The Strong Duality Theorem, which we will cover next, closes this gap. It states that if a linear program has an optimal solution, then so does its dual, and their optimal objective values are equal. This powerful result is the final piece of LP theory we need before we can prove the Minimax Theorem.