6.854 Notes #12

David Karger

1 Last Time

2 Duality

Checking feasibility of a given solution is easy. Motivating question: How to certify optimality of a given solution?

Want: Find a lower bound on \(v^*:=\min \set{c^Tx \mid Ax=b, x \ge 0}\).

Important observation (and a sanity check): The dual of the dual LP gives the primal LP.

A simple corollary of weak duality and the above observation: If \(P\) is the primal LP and \(D\) is the dual LP then either

3 Strong Duality

Weak duality described below is just a tip of an iceberg. Strong duality (key theorem of LP): If \(P\) and \(D\) feasible then \(v^*=w^*\).
“Proof” by picture:

Formal proof:

Claim: There exists \(x^*\) such that \(Ax^*=b\).

Claim: We have that \(b^Ty^*=c^Tx^*\).

Claim: It is the case that \(x^* \ge 0\).

(Formalizes the intuition that barriers have to push ball not pull it.)

Interesting corollary (of strong duality): For LPs, finding a solution that is merely feasible is algorithmically equivalent to finding a solution that is optimal.

4 Rules for Taking Duals

Some observations:

5 Insights on Specific Problems via LP Duality

5.1 Shortest Paths Problem

5.2 Maximum Flow Problem

6 Complementary Slackness

Duality leads to another idea: complementary slackness:

6.1 Apply CS to Max-flow Duality

6.2 Minimum Cost Circulation Problem