Alladi Ramakrishnan Hall

Convex Optimization - Random Walks, Localization Lemma and an Isoperimetric Inequality

Muthuvel Murugan

CMI

In this talk, we will present a result by Lovasz and Simonovits
on sampling points uniformly at random random in a convex body. This is
used as a subroutine to solve convex optimization problems. They use a
type of continuous random walk called ball walk to sample points in a
convex body. We will sketch a proof of the convergence of the ball
walk.
We will give a detailed proof of the Lovasz and Simonovits localization
lemma, and a detailed proof an isoperimetric inequality, which is used
in the convergence proof.