\documentclass{article} \usepackage{me} \usepackage{amssymb} \usepackage{amsfonts} \setlength{\parindent}{0pt} $\newcommand\vol{{\mbox{vol}}}$

Lecture 14: LP Duality

Last Time

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

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.

Rules for Taking Duals

Some observations:

Complementary Slackness

Duality leads to another idea: complementary slackness:

Insights on Specific Problems via LP Duality

Shortest Paths Problem

Maximum Flow Problem

Minimum Cost Circulation Problem