Opening Linear Programming and Two-Person Games
Linear Programming and Two-Person Games
- Length
- 54 min
- Level
- Undergraduate
- Recorded
- MIT2019
Chapter 1 of 9: Before the lecture
Strang proves weak duality for linear programs, then turns a zero-sum payoff matrix into a primal-dual pair.
Linear programming minimizes a linear cost subject to linear constraints and , with the optimum at a corner of the feasible set. In session 24 of MIT 18.065, Strang contrasts Dantzig's simplex method, which walks along edges, with Karmarkar's interior point methods. He sets up the dual maximization problem, proves weak duality and states strong duality, using max-flow min-cut on a network as a worked instance. A brief account of complexity covers Spielman's average-case analysis of simplex. Two-person zero-sum games then yield mixed strategies and von Neumann's minimax theorem, with a pointer to Nash's many-player games.
Linear programming minimizes a linear cost subject to linear constraints and , with the optimum at a corner of the feasible set. In session 24 of MIT 18.065, Strang contrasts Dantzig's simplex method, which walks along edges, with Karmarkar's interior point methods. He sets up the dual maximization problem, proves weak duality and states strong duality, using max-flow min-cut on a network as a worked instance. A brief account of complexity covers Spielman's average-case analysis of simplex. Two-person zero-sum games then yield mixed strategies and von Neumann's minimax theorem, with a pointer to Nash's many-player games.
This lecture
Lecture 24 of 34 of Matrix Methods in Data Analysis, Signal Processing, and Machine Learning.
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.
Your comment is kept while you sign up.Sign in
A Beautiful Mind