Abstract: Interior point methods are algorithms that optimize convex functions over high dimensional convex sets. From one point of view, an interior point method first equips a convex set with a Riemannian metric and then performs a steepest descent to minimize the objective on the resulting Riemannian manifold. We will describe a randomized variant of an interior point method known as ``the affine scaling algorithm" introduced by I.I.Dikin. This variant corresponds to a natural random walk on the same manifold on which affine scaling would perform steepest descent. We discuss applications to sampling and optimization and prove polynomial bounds on the mixing time of the associated Markov Chain. This talk includes work done in collaboration with Ravi Kannan and Alexander Rakhlin.
