Aaron Sidford: Introduction to Interior Point Methods for Discrete Optimization, Lecture II
Offered By: Hausdorff Center for Mathematics via YouTube
Course Description
Overview
Dive into the second lecture of a comprehensive series on interior point methods (IPMs) for discrete optimization. Explore the pivotal role IPMs have played in recent algorithmic advances, leading to improved running times for various continuous and combinatorial optimization problems. Gain a rigorous introduction to IPM theory, survey recent developments, and examine the state-of-the-art in the field. Delve into specific improvements related to discrete optimization, covering topics such as path following methods, minimizers, Newton's method, and modifications. Investigate primal methods, self-concordance, logarithmic barriers, linear programming, and extended reels. Enhance your understanding of how IPMs have contributed to nearly-linear runtimes in broad settings, including maximum flow, bipartite matching, and geometric median problems.
Syllabus
Intro
Overview
Path following methods
Minimizers
Newtons method
Modifications
Primal
Running the game
Selfconcordance
logarithmic barrier
linear pro
selfconcordant functions
extended reels
Taught by
Hausdorff Center for Mathematics
Related Courses
Convex OptimizationStanford University via edX Continuous Algorithms - Sampling and Optimization in High Dimension
Simons Institute via YouTube Interior Point Methods
Simons Institute via YouTube On the Computability of Continuous Maximum Entropy Distributions with Applications
Association for Computing Machinery (ACM) via YouTube Recent Advances in Iterative Solvers for Interior Point Methods
Fields Institute via YouTube