Opening Linear Programming Duality
Linear Programming Duality
- Length
- 22 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Certificates of unsatisfiability
Linear programming duality rests on the Farkas lemma: a system of linear inequalities is either satisfiable or has a short certificate of unsatisfiability. O'Donnell, in session 53 of CMU 15-750, A Theorist's Toolkit, starts from such certificates, non-negative multipliers that combine the inequalities into an impossible one. He proves the lemma with Fourier-Motzkin elimination, which removes one variable at a time by pairing its upper and lower bounds. The invariant is that every new inequality is a non-negative combination of the original system. The method blows up doubly exponentially, yet it shows that feasible systems have rational solutions. Bit-complexity bounds then give polynomial-size feasible points and certificates, and the search for a certificate becomes the dual linear program.
Your comment is kept while you sign up.Sign in
Proves the Farkas lemma by Fourier-Motzkin elimination, tracking each derived inequality as a non-negative combination.
Linear programming duality rests on the Farkas lemma: a system of linear inequalities is either satisfiable or has a short certificate of unsatisfiability. O'Donnell, in session 53 of CMU 15-750, A Theorist's Toolkit, starts from such certificates, non-negative multipliers that combine the inequalities into an impossible one. He proves the lemma with Fourier-Motzkin elimination, which removes one variable at a time by pairing its upper and lower bounds. The invariant is that every new inequality is a non-negative combination of the original system. The method blows up doubly exponentially, yet it shows that feasible systems have rational solutions. Bit-complexity bounds then give polynomial-size feasible points and certificates, and the search for a certificate becomes the dual linear program.
This lecture
Lecture 53 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.