Linear Programming Duality || @ CMU || Lecture 17b of CS Theory Toolkit

Linear Programming Duality || @ CMU || Lecture 17b of CS Theory Toolkit

by Ryan O'Donnell

Formal & Physical Sciences Mathematics PBUOptimizationPBUHLinear programming
🎙 Ryan O'Donnell 👥 14K 📅 June 1, 2020 ⏱ 22 min 👁 2K 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

LP dualityFarkas lemmaFourier-Motzkin eliminationcertificatesbit complexity

Summary

This lecture, part of the CS Theory Toolkit course at CMU, introduces the concept of duality in linear programming. The instructor begins by explaining how to prove that a system of linear inequalities is unsatisfiable by finding non-negative multipliers (lambdas) that combine the inequalities to yield a contradiction like 0 >= 1. This leads to the statement of Farkas’ lemma, which asserts that such multipliers always exist for unsatisfiable systems. The lecture then presents a proof of Farkas’ lemma using the Fourier-Motzkin elimination algorithm, which systematically eliminates variables from a system of inequalities while preserving satisfiability. The algorithm is shown to generate new inequalities that are non-negative combinations of the original ones, thus providing a certificate of unsatisfiability. The lecture also discusses the bit complexity of solutions and certificates, noting that if a system is feasible, there exists a rational solution with polynomial bit size, and similarly for infeasibility certificates. This is proven by considering the dual linear program, which is the problem of finding the lambdas. The lecture concludes by noting that the Fourier-Motzkin algorithm is highly inefficient (doubly exponential), but it provides theoretical insights, and hints at polynomial-time algorithms for LP to be covered in later lectures.

199 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a clear and rigorous explanation of LP duality and Farkas’ lemma, with a constructive proof via Fourier-Motzkin elimination. The argumentation is solid, building from simple examples to general principles. The value lies in the deep understanding it offers of why duality holds and how certificates work, which is fundamental for theoretical computer science. The instructor also addresses the bit complexity of solutions, an important practical consideration. The presentation is well-paced and includes interactive Q&A, enhancing comprehension.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with a formal proof of Farkas’ lemma. The sources cited are standard textbooks in the field: ‘Understanding and Using Linear Programming’ by Matoušek and Gärtner, and ‘Geometric Algorithms and Combinatorial Optimization’ by Grötschel, Lovász, and Schrijver. These are authoritative references. The title accurately reflects the content, focusing on LP duality. The lecture is part of a graduate course, so the technical level is appropriate for advanced students. No public comments were provided for analysis.

173 words

Title / Content Match

The title accurately reflects the content: the lecture covers linear programming duality, including Farkas' lemma and Fourier-Motzkin elimination.

Quality & Reliability

8/10

Lecture by a recognized expert in theoretical computer science, based on rigorous mathematical proofs and references to standard textbooks. The content is accurate and well-structured, though it is a lecture and not peer-reviewed.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

  • Understanding and Using Linear Programming — Referenced in the description as a resource for the lecture.
  • Geometric Algorithms and Combinatorial Optimization — Referenced in the description as a resource for the lecture.

Contribution & Novelties

This lecture provides a clear and accessible explanation of LP duality and Farkas’ lemma, with a constructive proof via Fourier-Motzkin elimination. It emphasizes the bit complexity of solutions and certificates, which is often overlooked. The lecture is part of a graduate course, so it offers a rigorous treatment suitable for advanced students.

Pour aller plus loin :

88 words

Radar Profile

The radar profile shows high scores in quality and technical level, with slightly lower scores in quantity and reliability, reflecting the lecture's depth and accuracy but limited breadth and lack of peer review.

Reliability 8/10