Abstract
Interior point methods are one of the key approaches to solving linear programming formulations as well as other convex programs. They give rise to algorithms that not only are the fastest ones known from asymptotic analysis point of view but also are often superior in practice.
This series of four lectures will present fundamentals of interior point methods as well as touch on the key ideas and concepts behind some of the recent developments. The topics we plan to cover include: (1) background on linear programming optimality conditions, the central path and its neighborhoods, and Newton's method; (2) complete analysis of a primal-dual path-following algorithm for linear programming and its relationship to a basic primal barrier method; (3) how to perturb central path to speed up convergence of an interior point method; and (4) a variant of interior point method that achieves running times that scales with the intrinsic dimension of the problem (rather than its possibly larger standard representation).
No previous experience with interior point methods is required.
The first session of this mini course will take place on Thursday, August 24 from 9:30 - 10:30 AM; the second session of this mini course will take place on Thursday, August 24 from 11:00 AM - 12:00 PM; the third session of this mini course will take place on Thursday, August 24 from 1:30 - 2:30 PM; and the fourth session of this mini course will take place on Friday, August 25 from 1:30 - 2:30 PM.