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. We will also describe how the Dikin ellipsoid can be used to estimate certain representation theoretic quantities known as Littlewood-Richardson coefficients.
Prof. Hariharan Narayanan graduated from the dual degree programme in electrical engineering at IIT Bombay in 2003 and did his M.S. and Ph.D. in computer science from Uni. of Chicago. After postdoctoral stints at MIT and Princeton Uni., he joined Uni. of Washington at Seattle where he is currently an assistant professor. His research interests are in statistics / machine learning, convex optimization and algebraic combinatorics.