Select Seminar Series
All seminars- Home
-   ›  
- Studying at the Faculty
-   ›  
- Seminars   ›  
- Upcoming Seminars
Upcoming Seminars
Linear Programming is the backbone of algorithm design and combinatorial optimization.
The fastest known algorithms for solving linear programs, both in theory and practice, are
based on Interior-Point Methods: The core idea behind IPMs is to iteratively use Newton
approximation to reduce a linear program to a sequence of ~\sqrt{n} linear systems. Whether
this number of iterations can be improved is one of the major open problems in convex optimization.
A long line of work has shown that \sqrt{n} is indeed optimal for the special class of *self-concordant*
Barrier IPMs [Nestrov-Nemirovski94], but for general IPMs very little is known.
We propose a purely information-theoretic query model for studying the rate of convergence of IPMs,
via linear-system queries: Each iteration of the algorithm can adaptively specify an arbitrary diagonal
matrix H (an ellipsoid) and a vector v, and the oracle returns the least-squares minimizer of the linear
system \arg\min_x || Ax - v||_H. We show this model captures all known (deterministic) IPMs. Our main
result is an \Omega(\sqrt{n}) lower bound on the iterations of any deterministic algorithm in this model,
albeit for an (exponentially) ill-conditioned LP. In this talk I will describe this progress, assuming no prior
knowledge on IPMs.
Based on Joint work with Shunhua Jiang, Rasmus Kyng and Ming Ding.