YoVDO

Aaron Sidford: Introduction to Interior Point Methods for Discrete Optimization, Lecture II

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Interior-Point Methods Courses Discrete Optimization Courses Newton's Method Courses

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 Optimization
Stanford 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